Thursday, May 17, 2007

I am studying for my exam in Performance Engineering these days, and came across a nice way of estimating Pi in the chapter about Monte Carlo simulations (random number simulations) yesterday. The idea is that you use random numbers to estimate something, in this case the number Pi.

Let's take a look at the figure below. Here we have the unit circle (a circle with radius 1 and center in origo) drawn in a coordinate system. Up to the right, in the first quadrant, I have shaded a square area with sides of length 1.

As you probably should remember from school, the area of a circle is A = Pi * r^2, and this circle therefore has an area of A = Pi * 1^2 = Pi. One fourth of the circle is in the shaded area, and this part of the circle therefore has the area Pi / 4. The shaded area itself has an area of 1 * 1 = 1. Then we define R to be the ratio between the area of the shaded part of the circle and the whole shaded area. This ratio is R = (Pi / 4) / 1 = Pi / 4.

Now, let's imagine throwing darts at the shaded area at random (we do not aim for any specific area). Of all the darts hitting the shaded area, a ratio of them, corresponding to R (since there is equal probability for hitting any part of the square), should hit inside the circle. For instance, if the ratio is 0.7, and 10 darts hit the shaded area, 7 should hit inside the shaded part of the circle.

If we throw a fair amount of darts, we should be able to calculate R using the formula R = DartsInsideGreyCircle / TotalDartsInsideGreyArea. As we have from the paragraph above, R = Pi / 4, which means that Pi = R * 4. We have estimated Pi!

The JavaScript simulation below illustrates this. Click start and watch what happens! If you let it run for a while, the result will actually get quite close to the actual value of Pi.

 Coordinates: (x, y) = (0, 0) Hits inside: 0, hits outside: 0 Ratio: R = HitsInside / (HitsInside + HitsOutside) = 0. Estimated Pi value: π ≈ 4 * R = 0. Speed: 1 /s.
Note: If you are reading this through an RSS feed, you may need to open the blog post in a browser to be able to run it.
posted on Wednesday, May 16, 2007 11:26:07 PM (W. Europe Standard Time, UTC+01:00)      Comments [0]