Formula for Pi

Date: 28 Jun 1995 09:39:43 -0400
From: Bryan K Cantwell
Subject: Formula for PI

I would like to know the formula for Pi that was used to calculate out to 
the bazillionth digit for the memory contests. Preferably, in a short 
program routine for my pc (486).

Thanks BKC
coyote@onramp.net

Date: 28 Jun 1995 10:06:06 -0400
From: Dr. Ken
Subject: Re: Formula for PI

Hello there!

I found this information in the FAQ for the newsgroup sci.math.  It's a good
resource.  Here you go:

_________________________________________________________

4Q: Where I can get pi up to a few hundred thousand digits of pi? 
    Does anyone have an algorithm to compute pi to those zillion 
    decimal places?

A:  MAPLE or MATHEMATICA can give you 10,000 digits of Pi in a blink,
    and they can compute another 20,000-1,000,000 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.

    How is pi calculated to many decimals ?

    There are essentially 3 different methods.

     1) One of the oldest is to use the power series expansion of atan(x)
     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 of Borwein and Borwein: Pi and the AGM, Canadian Math. Soc. Series,
     John Wiley and Sons, New York, 1987. 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 k1=545140134;k2=13591409;k3=640320;k4=100100025;k5=327843840;k6=53360;

     Then in AmsTeX notation

     $\pi=\frac{k6\sqrt(k3)}{S}$, where

     $$S=\sum_{n=0}^\infty (-1)^n\frac{(6n)!(k2+nk1)}{n!^3(3n)!(8k4k5)^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 8k4k5 appearing in the 
     denominator has been written this way instead of 262537412640768000.

     This is how the Chudnovsky's have computed several billion decimals.

     Question: how can I get a C program which computes pi?

     Answer: if you are too lazy to use the hints above, you can use the
     following 160 character C program (reportedly by Dik T. Winter) which
     computes pi to 800 decimal digits. If you want more, it is easy to modify,
     but you have to understand how it works first.

     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 :

    (This is a short version for a more comprehensive list contact
    Juhana Kouhia at jk87377@cc.tut.fi)

    J. M. Borwein, 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.

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

    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

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

    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

    D. Shanks and J.W. Wrench, Jr.
    Calculation of pi to 100,000 decimals
    Mathematics of Computation, Vol. 16, 1962, pp. 76-99

    Daniel Shanks
    Dihedral quartic approximations and series for pi
    J. Number Theory, Vol. 14, 1982, pp.397-423

    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

    J.W. Wrench, Jr.
    The evolution of extended decimal approximations to pi
    The Mathematics Teacher, Vol. 53, 1960, pp. 644-650
____________________________________________________

-K