Forever Learning

Forever learning and helping machines do the same.

Estimating Pi

with 4 comments

[I’ve tweeted about this before, but I feel the need to explain.]

I want to share with you my favorite algorithm. It may not be pretty, efficient or even practical, but I love it for it’s misleading simplicity and hidden complexity. It is a Probabilistic (Randomized) Algorithm that combines statistics and Euclidean geometry by using the Pythagorean theorem and the Law of Large Numbers to estimate Pi. I first learned about this algorithm when I was at Utrecht University studying Computing Science.

Don’t worry, this is not some complicated computer-gizmo-thing that only super-nerds can translate. I’ll take you through it nice and slow. You will need to recall some basic arithmetic you learned in high-school.

To estimate Pi, we rely on the following truths.

  1. The surface area of a circle is equal to πr² (Pi times the radius of the circle squared, definition of Pi).
  2. We can make a square in which the circle fits with sides that are of length 2r (easy, just try it).
  3. The surface of that square (that just encompasses the circle) is (2r)² (the width of the square squared).
  4. The ratio between the surface of the circle and the surface of the square is πr² / (2r)²; which equals π / 4.
  5. This ratio reflects the percentage of the square that is occupied by the circle (something close to 78,5%).
  6. The odds that a random point in the square is also in the circle is equal to the ratio of the two surface areas (statistics).
  7. Any point in the square is also in the circle when it is less than r distant from the center of the circle.
  8. The distance between two points squared is a² + b² (Pythagorean theorem).
  9. If you select enough random points in the square, the ratio between those points that are also in the circle and those that are not in the circle will approximate the ratio between the two surface areas (law of large numbers).

Estimating Pi

Based on all this, all we have to do is the following.

  1. Pick a a bunch of random points in the square (say N number of points where N is a pretty big number).
  2. Determine how many of those points are in the circle using the Pythagorean theorem (say C of them are in the circle).
  3. Calculate the ratio between C and N and multiply by 4.
  4. Presto! You have now estimated Pi.

Written down in Perl and compressed to fit into a single tweet this [1] can be expressed as:

perl -e 'for(;$i<999999;++$i){rand()**2+rand()**2>1?0:++$c}print 4*$c/$i." is (probably) pretty damn close to Pi!\n"'

Which probably looks daunting, but does nothing more than what I’ve just described.

  • for (;$i<999999:++$i) just means “do the following 999999 times”.
  • rand() is a random number between 0 and 1.
  • N**2 is N squared.
  • something ? this : that translates to “if something is true, do this, else, do that”.
  • 0 does nothing.
  • ++$c adds one to the variable C.
  • print does exactly what you expect.
  • \n prints a new line (solid return).

When executed, the Perl script outputs something like the following.

3.14152714152714 is (probably) pretty damn close to Pi!

Which is obviously wrong, but still pretty close to the actual number. Also note, that since we select random points the estimated number will be different every time we execute the code. To increase the accuracy of the number, simply use more random points. As the professor who explained this to an astonished class commented:

For maximum accuracy, you should simply select enough points so that the odds of a technical computational error are higher then the odds of an estimation error.

Isn’t computing science cool!?

[1] As my friend Daan pointed out before my original tweet was not quite optimal; hence the different code in this post.

Advertisements

Written by Lukas Vermeer

May 6, 2010 at 19:29

4 Responses

Subscribe to comments with RSS.

  1. Nice algorithm 🙂 Although I expected it to converge a bit faster

    Bert-Jan

    May 8, 2010 at 08:29

    • This kind of algorithm indeed does not converge as rapidly as most limit functions do; which is perhaps what you were expecting. This has to do with the fact that our ‘random walk’ does not necessarily take a step in the right direction every time.

      Wikipedia explains in relation to coin flips.

      “Though the proportion of heads (and tails) approaches half, almost surely the absolute (nominal) difference in the number of heads and tails will become large as the number of flips becomes large. That is, the probability that the absolute difference is a small number approaches zero as number of flips becomes large. Also, almost surely the ratio of the absolute difference to number of flips will approach zero. Intuitively, expected absolute difference grows, but at a slower rate than the number of flips, as the number of flips grows.” [wikipedia: LLN]

      lukasvermeer

      May 8, 2010 at 09:44

  2. […] a previous post I’ve explained how we can estimate the number Pi using Monte Carlo Methods (basically […]

    More Pi « Corporate Ninja

    November 6, 2010 at 11:58

  3. […] few weeks ago, I showed a colleague* my little visual demo of my favorite algorithm for estimating the number Pi. His immediate response was so obvious I am almost ashamed it did not occur to me before he […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: