p  and its computation through the ages

(Click here for a for a Postscript version of this page and here for a pdf version)

The value of p has engaged the attention of many mathematicians and calculators from the time of Archimedes to the present day, and has been computed from so many different formulae, that a complete account of its calculation would almost amount to a history of mathematics.

- James Glaisher (1848-1928)

The history of pi is a quaint little mirror of the history of man.

- Petr Beckmann

1  Computing the constant p

Understanding the nature of the constant p, as well as trying to estimate its value to more and more decimal places has engaged a phenomenal energy from mathematicians from all periods of history and from most civilizations. In this small overview, we have tried to collect as many as possible major calculations of the most famous mathematical constant, including the methods used and references whenever there are available.

1.1  Milestones of p's computation

• Ancient civilizations like Egyptians [14], Babylonians, China ([28], [51]), India [35],... were interested in evaluating, for example, area or perimeter of circular fields. Of course in this early history, p was not yet a constant and was only implicit in all available documents.

  Perhaps the most famous is the Rhind Papyrus which states the rule used to compute the area of a circle: take away 1/9 of the diameter and take the square of the remainder therefore implicitly p = (16/9)².

• Archimedes of Syracuse (287-212 B.C.). He developed a method based on inscribed and circumscribed polygons which will be of practical use until the mid seventeenth. It's the first known algorithm to compute p to, in principle, any required accuracy. By mean of regular polygons with 96 sides [21], in his treatise Measurement of a Circle, he showed that: the ratio of the circumference of any circle to its diameter is less than 3+1/7 but greater than 3+10/71.
• Zu Chongzhi from China (430-501). He established that 3.1415926 < p < 3.1415927 using polygons [28].
• Al-Kashi from Samarkand (1380-1429). By mean of Archimedes' polygons, he computed, in 1424, 2p to nine sexagesimal places and his estimation (about 14 correct decimals) will remain unsurpassed for nearly 200 years [1].
• Ludolph van Ceulen (1540-1610). Still using polygons, he made various computations and finally found 35 decimal places before his death in 1610, [9]. On his tombstone (today lost [22]), the following approximation was engraved: when the diameter is 1, then the circumference of the circle is greater than
  

  314159265358979323846264338327950288 100000000000000000000000000000000000

  but smaller than
  

  314159265358979323846264338327950289 100000000000000000000000000000000000 .

• Isaac Newton (1643-1727) and James Gregory (1638-1675) introduced respectively the series expansion of the function arcsin (1669) and the function arctan (1671) and opened the era of analytical methods to compute p. After a 15 digits computation Newton wrote: I am ashamed to tell you to how many figures I carried these computations, having no other business at the time [5].
• John Machin (1680-1751). In 1706 [24], the Truly Ingenious Mr. John Machin reached 100 decimal places with a fast converging arctan formula which now bares his name. The same year, William Jones (1675-1749) uses the symbol p to represent the ratio of the perimeter of a circle to its diameter.
• Johann Heinrich Lambert (1728-1777). p is irrational (1761, [29]).
• Adrien Marie Legendre (1752-1833). p² is irrational (1794, [30]).
• William Shanks (1812-1882). He spent a considerable part of his life to compute various approximations of p including a final 707 digits estimation ([41], [42]); this performance remains probably the most impressive of this nature. It was not until 1946 that an unfortunate mistake was discovered at the 528th place [15].
• Carl Louis Ferdinand von Lindemann (1852-1939). p is transcendental (1882, [32]).
• François Genuys, Daniel Shanks with John Wrench and Jean Guilloud with Martine Bouyer respectively reached 10,000 (1958, [18]), 100,000 (1961, [43]) and 1,000,000 (1973, [20]) digits by using arctan formulae and classical series expansion computation.
• Richard Brent and Eugene Salamin. They published in 1976, two important articles ([8], [39]) describing a new iterative and quadratic algorithm to determine p. This opened the era of fast algorithms, that is algorithms with complexity nearly proportional to the number of computed decimal places.

  Other methods of this nature and with higher order of convergence were later developed by Peter and Jonathan Borwein [6].

• David Chudnovsky and Gregory Chudnovsky. Introduction of new very fast series (consecutive to Ramanujan's work, [36], [11]) to establish various record on a home made supercomputer m-zero! The first billion digits was achieved by them in 1989 (see [34]).
• Yasumada Kanada. Since 1980 he is one of the major actor in the race to compute p to huge number of digits. Most of his calculations are made on supercomputers and are based on modern high order iterative algorithms (see [47], [25], [26], [46],...)

Other enumerations of p's computations can also be found in: [2], [3], [5], [13], [40], [53], ... in which we got many valuable informations.

The two following sections are enumerating the main computations respectively before and during computer era. The Method column usually refers to the last section; for example arctan(M) means that the arctangent relation (M) or Machin's formula was used.

2  History of p calculations before computer era

3  History of p calculations during computer era

4  List of the main used methods

In this section are expressed the main identities used to compute p just after the geometric period which was based on the computation of the perimeter (or area) of regular polygons with many sides.

4.1  Machin like formulae

There are numerous formulae to compute p by mean of arctan functions (see [3], [23], [31], [45], [48],...).

p 6 = arctan æ è  1 Ö3 ö ø (Sh)  p 4 = 4arctan æ è  1 5 ö ø -arctan æ è  1 239 ö ø , Machin (M)  p 4 = 8arctan æ è  1 10 ö ø -arctan æ è  1 239 ö ø -4arctan æ è  1 515 ö ø ,  Klingenstierna (K)  p 4 = arctan æ è  1 2 ö ø +arctan æ è  1 5 ö ø +arctan æ è  1 8 ö ø ,  Strassnitzky (SD)  p 4 = 12arctan æ è  1 18 ö ø +8arctan æ è  1 57 ö ø -5arctan æ è  1 239 ö ø , Gauss (G)  p 4 = 4arctan æ è  1 5 ö ø -arctan æ è  1 70 ö ø +arctan æ è  1 99 ö ø , Euler (E1) p 4 = 5arctan æ è  1 7 ö ø +2arctan æ è  3 79 ö ø , Euler (E2)  p 4 = arctan æ è  1 2 ö ø +arctan æ è  1 3 ö ø , Euler (E3)  p 4 = 2arctan æ è  1 3 ö ø +arctan æ è  1 7 ö ø , Hutton (H)  p 4 = 3arctan æ è  1 4 ö ø +arctan æ è  1 20 ö ø +arctan æ è  1 1985 ö ø ,  Loney (L)  p 4 = 6arctan æ è  1 8 ö ø +2arctan æ è  1 57 ö ø +arctan æ è  1 239 ö ø , Störmer (S1)  p 4 = 12arctan æ è  1 49 ö ø +32arctan æ è  1 57 ö ø -5arctan æ è  1 239 ö ø +12arctan æ è  1 110443 ö ø    (S2)  p 4 = 44arctan æ è  1 57 ö ø +7arctan æ è  1 239 ö ø -12arctan æ è  1 682 ö ø +24arctan æ è  1 12943 ö ø      (S3)

4.2  Other series

4.2.1  Newton

 

p =  3Ö3 4 +24 ó õ 1/4 0  Ö   x-x2   dx =  3Ö3 4 +24 æ è  1 12 -  1 5.25 -  1 28.27 -  1 72.29 ... ö ø , Newton (N)

4.2.2  Ramanujan like series

The important point is that evaluating such series to huge number of digits requires to develop specific algorithms. Such algorithms are now well known and are based on idea related to binary splitting. To learn more about those consult: [6], [7], [19],...

 

1 p =  2Ö2 9801 ¥ å k=0   (4k)! (k!)444k  (1103+26390k) 994k ,  Ramanujan [36] (Ra)  1 p =12 ¥ å k=0  (-1)k  (6k)! (3k)!(k!)3  (13591409+545140134k) 6403203k+3/2 , Chudnovsky   (CH)

4.3  Iterative algorithms

The main difficulty with the following iterative procedures is to compute to a high accuracy inverses and square roots of a real number. By mean of FFT based methods to compute products of numbers with many decimal places this is now possible in a quite efficient way. To find how to compute those operations you can consult [3], [6], [8], [19],...

4.3.1  Gauss-Legendre (or Brent-Salamin) quadratic

Set x₀=1,y₀=1/Ö2,a₀=1/2 and:

 

ì ï ï í ï ï î xk+1=( xk+yk) /2 yk+1= Ö   xkyk   ak+1=ak-2k+1( xk+12-yk+12)

then ([6], [8], [39]):

p = lim k®¥  ( 2xk2/ak) . (GL2)

4.3.2  Borwein quadratic

Set x₀=Ö2,y₀=0,a₀=2+Ö2 and:

 

ì ï ï ï ï í ï ï ï ï î xk+1= æ è Ö   xk   +1/ Ö   xk   ö ø /2 yk+1= Ö   xk   æ è  1+yk yk+xk ö ø ak+1=akyk+1 æ è  1+xk+1 1+yk+1 ö ø

then ([6]):

p = lim k®¥  ak. (B2)

4.3.3  Borwein quartic

Set y₀=Ö2-1,a₀=6-4Ö2 and:

ì í î

yk+1=( 1-(1-yk4)1/4) /(1+(1-yk4)1/4) ak+1=(1+yk+1)4ak-22k+3yk+1(1+yk+1+yk+12)

then ([6]):

p = lim k®¥  (1/ak ). (B4)

References

[1]

Al-Kashi, Treatise on the Circumference of the Circle, (1424)

[2]

Le Petit Archimède, no. hors série, Le nombre p, (1980)

[3]

J. Arndt and C. Haenel, p- Unleashed, Springer, (2001)

[4]

D.H. Bailey, The Computation of p to 29,360,000 Decimal Digits Using Borweins' Quartically Convergent Algorithm, Mathematics of Computation, (1988), vol. 50, p. 283-296

[5]

L. Berggren, J.M. Borwein and P.B. Borwein, Pi : A Source Book, Springer, (1997)

[6]

J.M. Borwein and P.B. Borwein, Pi and the AGM - A study in Analytic Number Theory and Computational Complexity, A Wiley-Interscience Publication, New York, (1987)

[7]

R.P. Brent, The Complexity of Multiple-Precision Arithmetic, Complexity of Computational Problem Solving, R. S. Andressen and R. P. Brent, Eds, Univ. of Queensland Press, Brisbane, (1976)

[8]

R.P. Brent, Fast multiple-Precision evaluation of elementary functions, J. Assoc. Comput. Mach., (1976), vol. 23, p. 242-251

[9]

L. van Ceulen, Van de Cirkel, daarin geleert wird te finden de naeste proportie des Cirkels diameter tegen synen Omloop, (1596,1616), Delft

[10]

D.V. Chudnovsky and G.V. Chudnovsky, Approximations and complex multiplication according to Ramanujan, in Ramanujan Revisited, Academic Press Inc., Boston, (1988), p. 375-396 & p. 468-472

[11]

D.V. Chudnovsky and G.V. Chudnovsky, The Computation of Classical Constants, Proc. Nat. Acad. Sci. USA, (1989), vol. 86, p. 8178-8182

[12]

Z. Dahse, Der Kreis-Umfang für den Durchmesser 1 auf 200 Decimalstellen berechnet, Journal für die reine und angewandte Mathematik, (1844), vol. 27, p. 198

[13]

J.P. Delahaye, Le fascinant nombre p, Bibliothèque Pour la Science, Belin, (1997)

[14]

H. Engels, Quadrature of the Circle in Ancient Egypt, Historia Mathematica, (1977), vol. 4, p. 137-140

[15]

D. Ferguson, Evaluation of p. Are Shanks' Figures Correct ?, Mathematical Gazette, (1946), vol. 30, p. 89-90

[16]

D. Ferguson, Value of p, Nature, (1946), vol. 17, p.342

[17]

E. Frisby, On the calculation of p, Messenger of Mathematics, (1872), vol. 2, p. 114

[18]

F. Genuys, Dix milles décimales de p, Chiffres, (1958), vol. 1, p. 17-22

[19]

X. Gourdon and P. Sebah, Numbers, Constants and Computation, World Wide Web site at the adress : http://numbers.computation.free.fr/Constants/constants.html, (1999)

[20]

J. Guilloud and M. Bouyer, 1 000 000 de décimales de p, Commissariat à l'Energie Atomique, (1974)

[21]

T.L. Heath, The Works of Archimedes, Cambridge University Press, (1897)

[22]

D. Huylebrouck, Van Ceulen's Tombstone, The Mathematical Intelligencer, (1995), vol. 4, p. 60-61

[23]

C.L. Hwang, More Machin-Type Identities, Math. Gaz., (1997), p. 120-121

[24]

W. Jones, Synopsis palmiorum matheseos, London, (1706), p. 263

[25]

Y. Kanada, Y. Tamura, S. Yoshino and Y. Ushiro, Calculation of p to 10,013,395 decimal places based on the Gauss-Legendre Algorithm and Gauss Arctangent relation, Computer Centre, University of Tokyo, (1983), Tech. Report 84-01

[26]

Y. Kanada, Vectorization of Multiple-Precision Arithmetic Program and 201,326,000 Decimal Digits of p Calculation, Supercomputing, (1988), vol. 2, Science and Applications, p. 117-128

[27]

F. de Lagny, Mémoire sur la quadrature du cercle et sur la mesure de tout arc, tout secteur et tout segment donné, Histoire de l'Académie Royale des sciences, Paris, (1719)

[28]

L.Y. Lam and T.S. Ang, Circle Measurements in Ancient China, Historia Mathematica, (1986), vol. 13, p. 325-340

[29]

J.H. Lambert, Mémoire sur quelques propriétés remarquables des quantités transcendantes circulaires et logarithmiques, Histoire de l'Académie Royale des Sciences et des Belles-Lettres der Berlin, (1761), p. 265-276

[30]

A.M. Legendre, Eléments de géométrie, Didot, Paris, (1794)

[31]

D.H. Lehmer, On Arctangent Relations for p, The American Mathematical Monthly, (1938), vol. 45, p. 657-664

[32]

F. Lindemann, Ueber die Zahl p, Mathematische Annalen, (1882), vol. 20, p. 213-225

[33]

S.C. Nicholson and J. Jeenel, Some comments on a NORC computation of p, MTAC, (1955), vol. 9, p. 162-164

[34]

R. Preston, The Mountains of Pi, The New Yorker, March 2, (1992), p. 36-67

[35]

C.T. Rajagopal and T. V. Vedamurti Aiyar, A Hindu approximation to pi, Scripta Math., (1952), vol. 18, p. 25-30

[36]

S. Ramanujan, Modular equations and approximations to p, Quart. J. Pure Appl. Math., (1914), vol. 45, p. 350-372

[37]

G.W. Reitwiesner, An ENIAC Determination of p and e to more than 2000 Decimal Places, Mathematical Tables and other Aids to Computation, (1950), vol. 4, p. 11-15

[38]

W. Rutherford, Computation of the Ratio of the Diameter of a Circle to its Circumference to 208 places of Figures, Philosophical Transactions of the Royal Society of London, (1841), vol. 131, p. 281-283

[39]

E. Salamin, Computation of p Using Arithmetic-Geometric Mean, Mathematics of Computation, (1976), vol. 30, p. 565-570

[40]

H.C. Schepler, The Chronology of Pi, Mathematics Magazine, (1950)

[41]

W. Shanks, Contributions to Mathematics Comprising Chiefly the Rectification of the Circle to 607 Places of Decimals, G. Bell, London, (1853)

[42]

W. Shanks, On the Extension of the Numerical Value of p, Proceedings of the Royal Society of London, (1873), vol. 21, p. 315-319

[43]

D. Shanks and J.W. Wrench Jr., Calculation of p to 100,000 Decimals, Math. Comput., (1962), vol. 16, p. 76-99

[44]

W. van Roijen Snell (Snellius), Cyclometricus, Leiden, (1621)

[45]

C. Störmer, Sur l'application de la théorie des nombres entiers complexes à la solution en nombres rationnels x_1,x₂,...,x_n,c₁,c₂,...,c_n,k de l'équation c₁arctg x₁+c₂ arctg x₂+...+c_n arctg x_n=kp/4, Archiv for Mathematik og Naturvidenskab, (1896), vol. 19

[46]

D. Takahasi and Y. Kanada, Calculation of Pi to 51.5 Billion Decimal Digits on Distributed Memory and Parallel Processors, Transactions of Information Processing Society of Japan, (1998), vol. 39, n^°7

[47]

Y. Tamura and Y. Kanada, Calculation of p to 4,194,293 Decimals Based on Gauss-Legendre Algorithm, Computer Center, University of Tokyo, Technical Report-83-01

[48]

J. Todd, A Problem on Arc Tangent Relations, Amer. Math. Monthly, (1949), vol. 56, p. 517-528

[49]

H.S. Uhler, Recalculation and extension of the modulus and of the logarithms of 2, 3, 5, 7 and 17, Proc. Nat. Acad. Sci., (1940), vol. 26, p. 205-212

[50]

G. Vega, Thesaurus Logarithmorum Completus, Leipzig, (1794)

[51]

A. Volkov, Calculation of p in ancient China : from Liu Hui to Zu Chongzhi, Historia Sci., vol. 4, (1994), p. 139-157

[52]

J.W. Wrench Jr. and L.B. Smith, Values of the terms of the Gregory series for arccot 5 and arccot 239 to 1150 and 1120 decimal places, respectively, Mathematical Tables and other Aids to Computation, (1950), vol. 4, p. 160-161

[53]

J.W. Wrench Jr., The Evolution of Extended Decimal Approximations to p, The Mathematics Teacher, (1960), vol. 53, p. 644-650