Each year on March 14, we celebrate Pi Day at Uber Amsterdam. This year, we were planning to celebrate Pi Day on Friday and to look at a couple of algorithms using PyAlgoViz. Due to COVID-19, the in-person celebration of Pi-Day got canceled, and instead we did a video call with the whole Amsterdam Tech Team at Uber Amsterdam. We did do a few live runs on one estimation, and the results can be found below.
In 2006, Akira Haraguchi recited 100,000 digits of Pi from memory, taking him 16 hours. How many can you recite?
In this article, I will show different ways of calculating Pi, with visualizations.
The first algorithm predates computers and is based on a thousand of years old insight that the ratio of the diameter and circumference of a circle appear to be constant, namely C=2πr. Old estimations derived a value for Pi of 3, or 256/81 (= 3.1604…), and that was fine for a long time.
In 1850, William Shanks took 15 years to estimate Pi to 707 digits. Turns out he made an error at digit 527. Makes all the time “wasted” on video gaming seem like nothing.
Archimedes was the first person to turn the estimation into an iterative process, where each step introduced a better approximation than the one before. The algorithm introduced by Archimedes was an innovative example of iterative computation, introduced by Greek Mathematicians around 2200 years ago now. Since then, people have found many other ways to calculate Pi, of course.
A simplified visualization of Archimedes’s estimation approach that I came up with myself is given at PyAlgoViz, a site dedicated to visualizations of a wide variety of Computer Science algorithms. The estimation runs in N steps, each time doubling the number of triangles inscribed in the circle. For each triangle we can calculate the length of the short edge, this involves calculating a square root, still not easy to do 2,200 years ago without a computer, of course.
The picture above shows step 2, using 8 rectangles, leading to an estimate for Pi of 3.12144515226. The more triangles we add, the closer we get. At step 6, with only 128 triangles, the resulting estimate is 3.14127725093. Pretty close already. After 28 steps, we come to 15 digits accuracy, which is enough for planetary navigation.
With more recent advances in Mathematics, the iterative Archimedes approach can be turned into an alternating series as follows:
The series rather slowly approaches Pi, so we need a lot of operations to come to a good estimate. But, known optimization techniques are available.
An incremental visualization of how much closer each step gets to approximating Pi is given on PyAlgoViz. Try it out yourself and use the scrollbar on the top right to “step through time” to see exactly how the approximation works:
In Carl Sagan’s novel “Contact”, when listing Pi in base 11, a circle could be seen inside the digits for Pi. This was a message from Aliens. Somehow this part of the narrative never made it to the movie version.
The animation I created above shows how with each step, the estimation of Pi gets closer and closer, while at the same time emphasizing the alternating aspect of the series.
To show how the error is reduced by each step over time, I also created a graph version that summarizes the iterations over time:
Monte Carlo Simulation
Earlier, I mentioned the ratio between circumference and radius being fixed. The same is true for the surface area of a circle and the square it fits inside. This is the premise of the Monte Carlo Simulation approach to estimating Pi.
The algorithm is also known as “throwing darts to calculate Pi”. I automated the algorithm in PyAlgoViz, by picking random points inside the square, color them, and then count them. In the above picture, we threw 5,000 darts at the board, had 3,942 darts land inside the circle, and 1,058 outside of it. This produces an estimate of Pi of 4 * 3,942 / 5,000 = 3.1536. Of course, the better you randomize the throws and the more darts you throw, the closer you should get to a correct estimate.
Monte Carlo at Uber Amsterdam
The result of the first real live experiment I was planning to do with my colleagues at Uber Amsterdam was to use a large piece of cardboard and having my colleagues throw darts at the board in a random fashion.
To avoid any target biases, the squares and circles would be drawn on the back and from time to time I would rotate the board as well. Basically, I was planning to follow the recipe given in the instructive video by Physics Girl shown above.
Due to a company-wide work from home policy due to Covid-19, we never got to trying out this experiment ourselves in real life. We will try this experiment ourselves later this year and definitely around Pi-Day 2021.
Similar to the Monte Carlo simulation, Buffon’s idea for calculating Pi is also based on chance. The algorithm goes as follows:
- Measure L = The length of a needle used in this experiment
- Draw parallel lines on a table at distance 2*L
- Count N = The number of randomly thrown needles
- Count T = The number of needles touching any of the lines
With that, you can calculate Pi = N / T. The reason for this is based on the circle described by the needles overlapping with the lines being a function of Pi. A great explanation is given in this video by Numberphile.
Here are two pictures of the setup we used for Pi-Day, at Uber Amsterdam:
The results we got from the manual experiments led to estimates for Pi of 3.12, 3.12, 3.27, and 4.0. The last one was caused by throwing a bundle of sticks close together in the box, which hampered the randomness, of course.
In summary, our manual experiments of calculating Pi using Buffon’s needles with nicely randomized needle placement yielded 100/31, 200/62, and 200/61. This makes for (3.12 + 3.12 + 3.27) / 3 = 3.17. Not bad at all!
If you try the visualization at PyAlgoViz, you will notice that you need a lot of needles to come close to a good estimate of Pi. In fact, you need a good randomizer and more needles than PyAlgoViz can support to get a reasonable answer.
At position 17,387,594,880 of Pi you will find the sequence 0123456789.
Pi is a magical number and can be found in the world in surprising ways. Somehow, some humans found it important to memorize Pi to hundreds of thousands of digits or to calculate Pi to trillions of digits. The usefulness of so many digits can be debated.
The NASA Jet Propulsion Labs’s highest accuracy calculations, used for getting us to the moon and Mars, use only 15 digits, i.e., 3.141592653589793. BTW, this is the same accuracy you get when you run “print(math.pi)” in Python. So, Python can actually get you reliably to Mars. In fact, to calculate circumferences of the entire universe correctly, you would still only need 39 or 40 decimal places.
March 14 is Pi Day, but it is also the birthday of famous people such as Albert Einstein, Johann Strauss, Michael Caine, Stephen Curry, Nicolas Anelka, Billy Crystal, and Quincy Jones.
My own birthdate, not in American but in European notation, occurs at position 95,062,032 of Pi. Where does yours?
Happy Pi Day, everyone.