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:
| nPoints | nPointsInside | π | execution time (seconds) |
|---|---|---|---|
| 10 | 9 | 3.6 | ~ 0.000001 |
| 100 | 81 | 3.24 | ~ 0.000002 |
| 1,000 | 791 | 3.164 | 0.00021 |
| 2,500 | 1,968 | 3.1488 | 0.0005 |
| 5,000 | 3,902 | 3.1216 | 0.001 |
| 10,000 | 7,883 | 3.1532 | 0.002 |
| 100,000 | 78,540 | 3.1416 | 0.02 |
| 500,000 | 392,231 | 3.137848 | 0.11 |
| 1,000,000 | 785,102 | 3.140408 | 0.21 |
| 10,000,000 | 7,853,300 | 3.14132 | 2.2 |
| 100,000,000 | 78,538,983 | 3.14155932 | 20.9 |
I’ve made a playground to help visualize the algorithm. The red points are inside the circle and the blue ones outside.
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%.
2 comments for “Random Pi”