Pi to x Million Decimal Places

Date: 1 Aug 1995 18:14:05 -0400
From: John Wallbank
Subject: Pi Calculation

Please explain _how_ Pi is calculated to X million decimal places?

Date: 3 Aug 1995 14:05:53 -0400
From: Dr. Ken
Subject: Re: Pi Calculation

Hello there!

Here's something I pulled off the FAQ file for the newsgroup sci.math.  If
you want to see what else they've got, you can either use the WWW URL 
ftp://ftp.belnet.be/pub/usenet-faqs/usenet-by-hierarchy/
                 news/answers/sci-math-faq/

or you can ftp directly to ftp.belnet.be and find it in the same directory.

What I got is
ftp://ftp.belnet.be/pub/usenet-faqs/usenet-by-hierarchy/
                 news/answers/sci-math-faq/specialnumbers/computePi

Also, there's a really nice article in a _New Yorker_ from a few years back
about the Chudnovsky brothers.  I'm not sure when it was, though.  Maybe '91?

 Here it is!

Date: Tue, 25 Apr 1995 17:42:10 GMT
From: Alex Lopez-Ortiz
Subject: sci.math FAQ: How to compute Pi?
Newsgroups: sci.math,sci.answers,news.answers

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.

   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 since it only involves
       multiplication/division by single precision numbers. 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.


   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.

   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.

   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.
     _________________________________________________________________

-K