In this exercise you will use a C++ program to redo, in a fraction of a second, the years of work of some of the worlds most famous mathematicians: calculate the value of π. You will then compare your result to one from a world class π calculating program, also written in C++.
This may seem like a silly trick, but it just one example of how much computers are doing every day to make our lives easier. It also shows the difference between a simple solution to a problem and a good solution. Much of Computer Science is concerned with this difference.
π, usually expressed as 3.14, should be a simple number. It is merely the ratio of the circumference of a circle to its diameter. Instead it is a complicated number that has long interested the smartest people on earth. Knowing the value to 7—10 places is enough for the most rigorous engineer. Knowing it to 20 places would satisfy most astrophysicists. And yet the brightest minds try to learn more from its infinitely unique digits. Perhaps answers to the mysteries of the universe are in there.
For a long time the only way to measure π was with geometry. This was a tedious and error prone process. Entire civilisations gave up and made do with a good guess: 3 or 3 1/8 (3.125).
One of our lab instructors who thinks he remembers Euclidean geometry tried this method. The best result after two hours of hard work was 3.124—he did not have a big enough compass, long enough ruler or large enough paper to do better.
Click to Enlarge
Later, the development of decimal notation, advanced algebra and calculus allowed people to discover much faster and precise ways to calculate π. One very famous and simple formula is the Machin formula, shown here. Many faster formulas exist.
|Famous π Calculations|
|Archimedes||3rd Century BCE||3.1419||Greek Empire||96 sided polygons - possibly killed by Roman soldiers while calculating a more precise value.|
|Ptolemy||2nd Century CE||3.1417||Roman Empire||?|
|Zu Chongzhi & Zu Gengzhi||5th Century CE||3.1415929 (355/113)||Chinese Empire||24,576 sided polygons|
|Madhava of Sangamagrama||15th Century CE||13 places||India||Madhava series|
|al-Kashi||15th Century CE||16 places||Iran||805 million sided polygons|
|Ludolf van Ceulen||1610 CE||35 places||Germany||32 billion sided polygons|
|William Shanks||1873 CE||707 places||England||Machin's formula|
|D. F. Ferguson, Levi Smith, and John Wrench||1949 CE||1,120 places||USA||Mechanical calculator, Machin's formula plus a second one to double check (1 or 2 digits per day)|
|Reitwiesner, Neumann, and Metropolis||1949 CE||2,037 places||USA||ENIAC (1 or two digits per minute)|
|Takahashi, D., and Kanada, Dr. Y.||1995 CE||4,294,960,000 places||Japan||Gauss-Legendre (SUPER_PI uses their code but is limited to 33 million digits)|
|Takahashi, Dr. D.||2009 CE||2,576,980,377,524 places||Japan||Gauss-Legendre (SUPER_PI uses their code but is limited to 33 million digits)|
William Shanks took 15 years to calculate his value for π, and it took 72 more years before D. F. Ferguson proved there was an error at the 527th digit using a mechanical calculator. Ferguson and his colleagues were the last people to calculate new digits of π without a programmable computer. The computer has made easy work of hard mathematics, but, as you will see in the exercise, technique still counts.
cp /net/data/ftp/pub/class/110/ftp/cpp/pi/sol/* ./
makeand run it by typing
Blatner, D. (1997). The joy of [pi]. New York: Walker and Co.
Chris Hills. (2005). Calculate pi to one million decimal places. Retrieved 6/23, 2009, from http://www.codeproject.com/KB/recipes/CRHpi.aspx
Smith, H. J. (2009). Computing pi. Retrieved 6/23, 2009, from http://www.geocities.com/hjsmithh/Pi/index.html (page expired).
Takahashi, D., & Kanada, Dr. Y. (1995). Super pi (Ver1.1e ed.). University of Tokyo: Retrieved from ftp://pi.super-computing.org/windows/super_pi.zip