The computation of to decimal digits using Borweins' quartically convergent algorithm
Author:
David H. Bailey
Journal:
Math. Comp. 50 (1988), 283296
MSC:
Primary 11Y60; Secondary 1104, 11K16, 6504
MathSciNet review:
917836
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In a recent work [6], Borwein and Borwein derived a class of algorithms based on the theory of elliptic integrals that yield very rapidly convergent approximations to elementary constants. The author has implemented Borweins' quartically convergent algorithm for , using a prime modulus transform multiprecision technique, to compute over 29,360,000 digits of the decimal expansion of . The result was checked by using a different algorithm, also due to the Borweins, that converges quadratically to . These computations were performed as a system test of the Cray2 operated by the Numerical Aerodynamical Simulation (NAS) Program at NASA Ames Research Center. The calculations were made possible by the very large memory of the Cray2. Until recently, the largest computation of the decimal expansion of was due to Kanada and Tamura [12] of the University of Tokyo. In 1983 they computed approximately 16 million digits on a Hitachi S810 computer. Late in 1985 Gosper [9] reported computing 17 million digits using a Symbolics workstation. Since the computation described in this paper was performed, Kanada has reported extending the computation of to over 134 million digits (January 1987). This paper describes the algorithms and techniques used in the author's computation, both for converging to and for performing the required multiprecision arithmetic. The results of statistical analyses of the computed decimal expansion are also included.
 [1]
D. H. Bailey, "A highperformance fast Fourier transform algorithm for the Cray2," J. Supercomputing, v. 1, 1987, pp. 4360.
 [2]
Petr
Beckmann, A history of 𝜋 (pi), 2nd ed., The Golem
Press, Boulder, Colo., 1971. MR 0449960
(56 #8261)
 [3]
Allan
Borodin and Ian
Munro, The computational complexity of algebraic and numeric
problems, American Elsevier Publishing Co., Inc., New
YorkLondonAmsterdam, 1975. Elsevier Computer Science Library; Theory of
Computation Series, No. 1. MR 0468309
(57 #8145)
 [4]
J.
M. Borwein and P.
B. Borwein, The arithmeticgeometric mean and fast computation of
elementary functions, SIAM Rev. 26 (1984),
no. 3, 351–366. MR 750454
(86d:65029), http://dx.doi.org/10.1137/1026073
 [5]
J.
M. Borwein and P.
B. Borwein, More quadratically converging
algorithms for 𝜋, Math. Comp.
46 (1986), no. 173, 247–253. MR 815846
(87e:65014), http://dx.doi.org/10.1090/S00255718198608158466
 [6]
J. M. Borwein & P. B. Borwein, Pi and the AGMA Study in Analytic Number Theory and Computational Complexity, Wiley, New York, 1987.
 [7]
Richard
P. Brent, Fast multipleprecision evaluation of elementary
functions, J. Assoc. Comput. Mach. 23 (1976),
no. 2, 242–251. MR 0395314
(52 #16111)
 [8]
E. O. Brigham, The Fast Fourier Transform, PrenticeHall, Englewood Cliffs, N. J., 1974.
 [9]
W. Gosper, private communication.
 [10]
Emil
Grosswald, Topics from the theory of numbers, The Macmillan
Co., New York; CollierMacmillan Ltd., London, 1966. MR 0228408
(37 #3989)
 [11]
G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, London, 1984.
 [12]
Y. Kanada & Y. Tamura, Calculation of to 10,013,395 Decimal Places Based on the GaussLegendre Algorithm and Gauss Arctangent Relation, Computer Centre, University of Tokyo, 1983.
 [13]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [14]
Eugene
Salamin, Computation of 𝜋 using
arithmeticgeometric mean, Math. Comp.
30 (1976), no. 135, 565–570. MR 0404124
(53 #7928), http://dx.doi.org/10.1090/S00255718197604041249
 [15]
Daniel
Shanks and John
W. Wrench Jr., Calculation of 𝜋 to 100,000
decimals, Math. Comp. 16 (1962), 76–99. MR 0136051
(24 #B2090), http://dx.doi.org/10.1090/S00255718196201360519
 [16]
P. Swarztrauber, "FFT algorithms for vector computers," Parallel Comput., v. 1, 1984, pp. 4564.
 [1]
 D. H. Bailey, "A highperformance fast Fourier transform algorithm for the Cray2," J. Supercomputing, v. 1, 1987, pp. 4360.
 [2]
 P. Beckmann, A History of Pi, Golem Press, Boulder, CO, 1971. MR 0449960 (56:8261)
 [3]
 A. Borodin & I. Munro, The Computational Complexity of Algebraic and Numeric Problems, American Elsevier, New York, 1975. MR 0468309 (57:8145)
 [4]
 J. M. Borwein & P. B. Borwein, "The arithmeticgeometric mean and fast computation of elementary functions," SIAM Rev., v. 26, 1984, pp. 351366. MR 750454 (86d:65029)
 [5]
 J. M. Borwein & P. B. Borwein, "More quadratically converging algorithms for ," Math. Comp., v. 46, 1986, pp. 247253. MR 815846 (87e:65014)
 [6]
 J. M. Borwein & P. B. Borwein, Pi and the AGMA Study in Analytic Number Theory and Computational Complexity, Wiley, New York, 1987.
 [7]
 R. P. Brent, "Fast multipleprecision evaluation of elementary functions," J. Assoc. Comput. Mach., v. 23, 1976, pp. 242251. MR 0395314 (52:16111)
 [8]
 E. O. Brigham, The Fast Fourier Transform, PrenticeHall, Englewood Cliffs, N. J., 1974.
 [9]
 W. Gosper, private communication.
 [10]
 Emil Grosswald, Topics from the Theory of Numbers, Macmillan, New York, 1966. MR 0228408 (37:3989)
 [11]
 G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, London, 1984.
 [12]
 Y. Kanada & Y. Tamura, Calculation of to 10,013,395 Decimal Places Based on the GaussLegendre Algorithm and Gauss Arctangent Relation, Computer Centre, University of Tokyo, 1983.
 [13]
 D. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, AddisonWesley, Reading, Mass., 1981. MR 633878 (83i:68003)
 [14]
 E. Salamin, "Computation of using arithmeticgeometric mean," Math. Comp., v. 30, 1976, pp. 565570. MR 0404124 (53:7928)
 [15]
 D. Shanks & J. W. Wrench, Jr., "Calculation of to 100,000 decimals," Math. Comp., v. 16, 1962, pp. 7699. MR 0136051 (24:B2090)
 [16]
 P. Swarztrauber, "FFT algorithms for vector computers," Parallel Comput., v. 1, 1984, pp. 4564.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11Y60,
1104,
11K16,
6504
Retrieve articles in all journals
with MSC:
11Y60,
1104,
11K16,
6504
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198809178363
PII:
S 00255718(1988)09178363
Article copyright:
© Copyright 1988
American Mathematical Society
