Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!news-out.cwix.com!newsfeed.cwix.com!torn!watserv3.uwaterloo.ca!undergrad.math.uwaterloo.ca!neumann.uwaterloo.ca!alopez-o
From:
[email protected] (Alex Lopez-Ortiz)
Newsgroups: sci.math,news.answers,sci.answers
Subject: sci.math FAQ: Digits or Pi
Followup-To: sci.math
Date: 17 Feb 2000 22:51:58 GMT
Organization: University of Waterloo
Lines: 136
Approved:
[email protected]
Expires: Sun, 1 Mar 1998 09:55:55
Message-ID: <
[email protected]>
Reply-To:
[email protected]
NNTP-Posting-Host: daisy.uwaterloo.ca
Summary: Part 4 of 31, New version
Originator:
[email protected]
Originator:
[email protected]
Xref: senator-bedfellow.mit.edu sci.math:347384 news.answers:177504 sci.answers:11212
Archive-name: sci-math-faq/pi
Last-modified: February 20, 1998
Version: 7.5
_________________________________________________________________
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.
The current record is held by Yasumasa Kanada and Daisuke Takahashi
from the University of Tokyo with 51 billion digits of pi
(51,539,600,000 decimal digits to be precise).
Nick Johnson-Hill has an interesting page of pi trivia at:
http://www.users.globalnet.co.uk/ nickjh/Pi.htm
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
http://www.cecm.sfu.ca/~pborwein
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.
--
Alex Lopez-Ortiz
[email protected]
http://www.cs.unb.ca/~alopez-o Assistant Professor
Faculty of Computer Science University of New Brunswick
