Friday, 7 January 2011

Maths Problems 3C: Estimating pi by sampling

In response to my first post about pi, my friend Chris Timbey pointed out that he's previously written a computer program which will estimate pi by determining if a random point in a square is also in a quadrant drawn within that square.  The diagram below shows how this would work.

Not only is pi the ratio of a circle's circumference to its diameter (C = pi x d), but the area of a circle is pi r2, so we have another way of approximating the value of pi.
The cartesian equation (using x and y) for a circle is x2 + y2 = 1. By taking random values of x and y and determining if the value of x2 + y2 is greater than or less than 1, we can calculate the ratio of the area of the quadrant to the area of the square.

This is where a computer comes in very handy.  The basic program works thus:
1.  Obtain random values of x and y between 0 and 1.
2.  Square x and y, and sum the two values.
3.  If the sum of x2 + y2 is less than 1, then count this as 'within the quadrant', otherwise count it as outside the quadrant.
4.  Repeat the first three steps a large number of times.
5.  Calculate the proportion of counts 'within the quadrant' to the total number of counts (both inside and outside the quadrant).
6.  Multiply this proportion by 4, since there are four quadrants in a circle.

For example:
Random value of x = 0.252
Random value of y=0.881
x2 + y= 0.840 so this is within the quadrant.

This takes a large number of iterations to produce an accurate result.

Here are my results; iterations on the left, value of pi on the right:
100  -  3.08
200  -  3.12
1000 - 3.212
5500 - 3.167272 (recurring)
10,000 - 3.13040, also 3.1736, 3.1312  (repeating the experiment with 10,000 new random pairs).
15,000 - 3.13040 (11739/15000)
Beyond this, my spreadsheet starts grinding to a slow and painful halt, but at least by 10,000 iterations it's mostly hitting pi to one decimal place.  This will always be an approximation, since it's based on a fraction (no matter how precise), and pi, being an irrational number, doesn't much like being expressed as a fraction!

Next time - approximation of pi based on a regular polygon with thousands of sides.

No comments:

Post a Comment