Using Pi’s to calculate Pi

By Richard Loft
03/13/2015 - 12:00am
Saturday March 14th is “Pi Day,” the harmonic convergence of calendric tomfoolery anticipated annually by math enthusiasts everywhere. This year the calendar reproduces the value of pi even more exactly: 3-14-15. For the truly nerdy, the magic moment will come at 9:26:53 AM (in whatever time zone you happen to find yourself) when time itself will recapitulate the digits of pi out to nine places: 3.141592653. Move over Y2K!
 
Anyway, a few of us at NCAR plan to celebrate the joy of mathematics by doing – what else – calculating 1,000,000 digits of pi on our Raspberry Pi cluster! We invite you to watch our progress in this quest on our Raspberry Pi website: http://ucar.github.io/r-pi/events/Pi-Day-Celebration where our cluster will be posting its results starting precisely (if we remember to get up!) at the magic moment of 9:26:53 AM on Saturday.
 
Now, we’re not going for any records: in October of last year Alexander Yee’s y-cruncher code was used to calculate 13,300,000,000,000 decimal places of pi using two sockets of Xeon E5-4650L @ 2.6 GHz. It took 208 days! Well, to beat that mark we’d be still cranking away for Two Pi day, which is 6-28-31. No way!
 
But it is a great chance to show off the power of parallelism! Calculating the digits of pi would seem to be inherently recursive in nature – getting the next digit should depend on knowing the last – and would therefore seem to require a super-fast computer to get there. There are, however, amazing parallel algorithms that allow the calculation to start at any digit of pi! One such algorithm is the Bailey-Borwein-Plouffe algorithm discovered in 1995. This type of algorithm allows one to divide batches of pi digits up among many processors and share the work. This is the algorithm we’ll use for our parallel computation of the first million digits of pi. And we’ll use our $500, 12-processor Raspberry Pi cluster to make the point: there’s strength in numbers. And here is the code that does it.
 
Looking at the history of pi records, it’s worth noting that the million-digit mark was set in 1973 on a CDC 7600 by Jean Guilloud and Martin Bouyer, who ran it out to 1,000,1250 decimal digits in 23.3 hours. NCAR also owned one of these five-million-dollar machines at the time. So we’re reproducing history here!
 
Actually, to match Guilloud and Bouyer, we’re going to calculate the first 831,604 hexadecimal (base 16) digits (0,1,2,3,4,5,6,7,8,9,0,A,B,C,D,E,F). We can stop there because hexadecimal numbers are about 20% more efficient than decimals in representing a number – makes you wish you had eight fingers on each hand doesn’t it? More importantly, hexadecimal numbers are the natural basis for representing the results of the BBP algorithm.
 
Wish us luck!
 
Interesting facts about Pi:
 
In the Third Century BC, Archimedes (of Eureka fame) was the first to develop an algorithm for bounding pi to arbitrary accuracy using polygons.
 
In 1874 William Shanks, an owner of a boarding school in England, took 15 years to calculate 707 digits of pi by hand – but he made a mistake in the 528th digit. This mistake was only discovered in 1946.
 
In 1910, Srinivasa Ramanujan, the great Indian mathematician, discovered the rapidly converging mathematical series that are used by most pi crunchers today. He had almost no formal training in pure mathematics.