Random Pi

tl;dr I’m going to show you a little trick that uses random numbers to approximate the value of Pi.

Monte Carlo methods (or Monte Carlo experiments) are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results; typically one runs simulations many times over in order to obtain the distribution of an unknown probabilistic entity. The name comes from the resemblance of the technique to the act of playing and recording results in a real gambling casino.

To approximate the value of Pi we are going to place random points inside a 2 by 2 square and count the number of points that are inside the inscribed circle. The inscribed circle has the radius 1, that makes the area of the circle π * r² = π * 1² = π. If the points are uniformly distributed the proportion of points that are inside the circle will converge to the area of the circle relative to the area of the square (which is 2 x 2 = 4).

In other words nPointsInside / nPoints ~ PI / 4 or PI ~ 4 * nPointsInside / nPoints.

The first thing we need is random numbers. The generate random numbers in we can use the drand48() function from the standard library. drand48() returns a double in the range of 0.0 to 1.0. By doubling and then subtracting one from the results of drand48() we obtain random values between -1.0 and 1.0.

In this image we can see how the square and circle are positioned:

If a point is inside the circle then the distance between the point and the center of the circle (0, 0) will be at most 1.

var nPoints = 100

var nPointsInside = 0

for _ in 1...nPoints {
    var (x, y) = (drand48() * 2 - 1, drand48() * 2 - 1)
    if x * x + y * y <= 1 {
        ++nPointsInside
    }
}

var pi = 4.0 * Double(nPointsInside) / Double(nPoints)

Here are some results for different values of of nPoints:

nPointsnPointsInsideπexecution time (seconds)
1093.6~ 0.000001
100813.24~ 0.000002
1,0007913.1640.00021
2,5001,9683.14880.0005
5,0003,9023.12160.001
10,0007,8833.15320.002
100,00078,5403.14160.02
500,000392,2313.1378480.11
1,000,000785,1023.1404080.21
10,000,0007,853,3003.141322.2
100,000,00078,538,9833.1415593220.9

I’ve made a playground to help visualize the algorithm. The red points are inside the circle and the blue ones outside.

tests

Monte Carlo method applied to approximating the value of π by placing 10, 100, 500, 1000, 2500 and 5000 random points

Monte Carlo method applied to approximating the value of π. After placing 30000 random points, the estimate for π is within 0.07% of the actual value. This happens with an approximate probability of 20%.

Fututre reading

  2 comments for “Random Pi

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe
We send about one email per week with our latest tutorials and updates
Never display this again :)