How to compute digits of pi ?

Symbolic Computation software such as Maple or Mathematica can compute 10,000 digits of pi in a blink, and another 20,000-1,000,000 digits overnight (range depends on hardware platform).

It is possible to retrieve 1.25+ million digits of pi via anonymous ftp from the site wuarchive.wustl.edu, in the files pi.doc.Z and pi.dat.Z which reside in subdirectory doc/misc/pi. New York's Chudnovsky brothers have computed 2 billion digits of pi on a homebrew computer.

This computations were made by Yasumasa Kanada, at the University of Tokyo.

There are essentially 3 different methods to calculate pi to many decimals.

1. One of the oldest is to use the power series expansion of atan(x) = x - x^3/3 + x^5/5 - ... together with formulas like pi = 16*atan(1/5) - 4*atan(1/239). This gives about 1.4 decimals per term.

2. A second is to use formulas coming from Arithmetic-Geometric mean computations. A beautiful compendium of such formulas is given in the book pi and the AGM, (see references). They have the advantage of converging quadratically, i.e. you double the number of decimals per iteration. For instance, to obtain 1 000 000 decimals, around 20 iterations are sufficient. The disadvantage is that you need FFT type multiplication to get a reasonable speed, and this is not so easy to program.

3. A third one comes from the theory of complex multiplication of elliptic curves, and was discovered by S. Ramanujan. This gives a number of beautiful formulas, but the most useful was missed by Ramanujan and discovered by the Chudnovsky's. It is the following (slightly modified for ease of programming):

   Set k_1 = 545140134; k_2 = 13591409; k_3 = 640320; k_4 = 100100025; k_5 = 327843840; k_6 = 53360;

   Then pi = (k_6 sqrt(k_3))/(S), where

   S = sum_(n = 0)^oo (-1)^n ((6n)!(k_2 + nk_1))/(n!^3(3n)!(8k_4k_5)^n)

   The great advantages of this formula are that

   1) It converges linearly, but very fast (more than 14 decimal digits per term).

   2) The way it is written, all operations to compute S can be programmed very simply. This is why the constant 8k_4k_5 appearing in the denominator has been written this way instead of 262537412640768000. This is how the Chudnovsky's have computed several billion decimals.

An interesting new method was recently proposed by David Bailey, Peter Borwein and Simon Plouffe. It can compute the Nth hexadecimal digit of Pi efficiently without the previous N-1 digits. The method is based on the formula:

pi = sum_(i = 0)^oo (1 16^i) ((4 8i + 1) - (2 8i + 4) - (1 8i + 5) - (1 8i + 6))

in O(N) time and O(log N) space. (See references.)

The following 160 character C program, written by Dik T. Winter at CWI, computes pi to 800 decimal digits.

 int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;
     for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,
     f[b]=d%--g,d/=g--,--b;d*=b);}

References

P. B. Borwein, and D. H. Bailey. Ramanujan, Modular Equations, and Approximations to pi American Mathematical Monthly, vol. 96, no. 3 (March 1989), p. 201-220.

D. H. Bailey, P. B. Borwein, and S. Plouffe. A New Formula for Picking off Pieces of Pi, Science News, v 148, p 279 (Oct 28, 1995). also at New Formula for Picking off Pieces of Pi

J.M. Borwein and P.B. Borwein. The arithmetic-geometric mean and fast computation of elementary functions. SIAM Review, Vol. 26, 1984, pp. 351-366.

J.M. Borwein and P.B. Borwein. More quadratically converging algorithms for pi . Mathematics of Computation, Vol. 46, 1986, pp. 247-253.

Shlomo Breuer and Gideon Zwas Mathematical-educational aspects of the computation of pi Int. J. Math. Educ. Sci. Technol., Vol. 15, No. 2, 1984, pp. 231-244.

David Chudnovsky and Gregory Chudnovsky. The computation of classical constants. Columbia University, Proc. Natl. Acad. Sci. USA, Vol. 86, 1989.

Classical Constants and Functions: Computations and Continued Fraction Expansions D.V.Chudnovsky, G.V.Chudnovsky, H.Cohn, M.B.Nathanson, eds. Number Theory, New York Seminar 1989-1990.

Y. Kanada and Y. Tamura. Calculation of pi to 10,013,395 decimal places based on the Gauss-Legendre algorithm and Gauss arctangent relation. Computer Centre, University of Tokyo, 1983.

Morris Newman and Daniel Shanks. On a sequence arising in series for pi . Mathematics of computation, Vol. 42, No. 165, Jan 1984, pp. 199-217.

E. Salamin. Computation of pi using arithmetic-geometric mean. Mathematics of Computation, Vol. 30, 1976, pp. 565-570

David Singmaster. The legal values of pi . The Mathematical Intelligencer, Vol. 7, No. 2, 1985.

Stan Wagon. Is pi normal? The Mathematical Intelligencer, Vol. 7, No. 3, 1985.

A history of pi . P. Beckman. Golem Press, CO, 1971 (fourth edition 1977)

pi and the AGM - a study in analytic number theory and computational complexity. J.M. Borwein and P.B. Borwein. Wiley, New York, 1987.

Extraordinary Pi	Many extraordinary facts about you know what. Then visit here to find an extraordinary collection of pi web links.
PI	Pi to 50 000 decimal places. This site claims to have 6.4 billion digits of pi, but I wasn't game to check it out. Or what about a relatively mundane 500,000,000 digits.
The PI Trivia Game	Here are 25 (given to you 5 at a time) fun pi-related questions, picked randomly from Eve's exciting pi question database! Get ready for the thrill of your lifetime, the ultimate challenge, The Pi Trivia Game!
A Common Book of Pi	Pi has been the subject of a great deal of mathematical (and popular) folklore. It's been worshipped, maligned, and misunderstood. Overestimated, underestimated, and legislated. Of interest to scholars, crackpots, and everyday people. Here is a website devoted to it all.
The Quest for the Holy Value	Yes, its pi again. Technically, it has been proven by Knuth that you can estimate pi using the factors of pairs of large random integers. So, if lots of folks submit two large random integers, eventually the value of pi can be pegged down to an accuracy of 1 (or even 2!) decimal places. At the time of writing, the estimated value of pi is about 3.4, so many more visitors are needed.

Back to The Information Cave home page

Last modified Sat Aug 31 17:16:31 2002.