Find PI digits using the Monte Carlo method

Question

I tried many algorithms for finding π using Monte Carlo. One solution (in Python) is the following:

def calc_PI(): n_points = 1000000 hits = 0 for i in range(1, n_points): x, y = uniform(0.0, 1.0), uniform(0.0, 1.0) if (x**2 + y**2) <= 1.0: hits += 1 print "Calc2: PI result", 4.0 * float(hits) / n_points 

The sad part is that even with 1,000,000,000 accuracy is VERY bad ( 3.141 ... ).

Is this the maximum accuracy this method can offer? The reason I choose Monte Carlo was that it is very easy to break it up in parallel parts. Is there another algorithm for π that is easily broken into pieces and computed?

Answer 1

This is a classic example of Monte Carlo. But if you are trying to split the calculation of pi into parallel parts, why not just use an infinite series and let each core take a range and then summarize the results along the way?

http://mathworld.wolfram.com/PiFormulas.html

Answer 2

Your fractional error passes sqrt(N)/N = 1/sqrt(N) , so this is a very inefficient way to get an accurate estimate. This limit is set by the statistical nature of the measurement and cannot be beaten.

You can get floor(log_10(N))/2-1 digits of good accuracy for N throws. Maybe -2 just be safe ...

Even so, it is assumed that you are using a real RNG or good enough PRNG.

Answer 3

Use the quasi random number generator ( http://www.nag.co.uk/IndustryArticles/introduction_to_quasi_random_numbers.pdf ) instead of the standard pseudo-RNG. Quasi-random numbers cover the area of ​​integration (what you do is integrate with MC) more evenly than pseudo-random numbers, which provides better convergence.