Re: Monte Carlo approximation of PI

Replies are listed 'Best First'.
Re: Re: Monte Carlo approximation of PI by Anonymous Monk on Apr 04, 2003 at 12:54 UTC
It is probable that imperfections in Perl's rand will result in a consistent slight theoretical bias. It would also take an insane amount of time to have any chance of detecting this fact. Remember that to get the error down to 1 part in n, the number of iterations that you need is proportional to n*n. (The appropriate constant depends on what probability of being outside of your interval you are willing to accept.) A theoretical error on the order of one part in 50 million takes 2,500 trillion steps to find. Assuming that you can invoke the necessary code 100 million times per section (probably rather optimistic on today's hardware), it would take on the order of a year or so to find it. If the error is smaller than that, it would take longer... (I don't have sufficient interest to find out what Perl's rand algorithm is to calculate the order of magnitude of the exact theoretical bias. It will depend on how close together the grid of possible answers are that rand can return.)	[reply]
Re: Monte Carlo approximation of PI by Abigail-II (Bishop) on Apr 04, 2003 at 12:03 UTC
But if you want to factor in the discreteness, with the same argumenation it follows that using `<= 1` will lead to an overestimated pi. Abigail	[reply] [d/l]
Re: Monte Carlo approximation of PI by robartes (Priest) on Apr 04, 2003 at 12:10 UTC
Indeed, well spotted. So to make the algorithm even slower, we might actually have to run it twice, once with `< 1` and once with `<= 1`, and then take the average of the two. Oh well :). CU Robartes-	[reply] [d/l] [select]
Re: Monte Carlo approximation of PI by Abigail-II (Bishop) on Apr 04, 2003 at 14:11 UTC
I just ran a simulation with 16 million uniformely distributed points, and using both `< 1` and `<= 1` give estimates of `3.141020`. Round-off errors probably pay their toll as well, even on my 64bit perl. Abigail	[reply] [d/l] [select]
Re: Re: Monte Carlo approximation of PI by robartes (Priest) on Apr 04, 2003 at 14:16 UTC


The stupid question is the question not asked
	PerlMonks