The computation of $\pi$ to $29,360,000$ decimal digits using Borweins’ quartically convergent algorithm
Author:
David H. Bailey
Journal:
Math. Comp. 50 (1988), 283296
MSC:
Primary 11Y60; Secondary 1104, 11K16, 6504
DOI:
https://doi.org/10.1090/S00255718198809178363
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 $1/\pi$, using a prime modulus transform multiprecision technique, to compute over 29,360,000 digits of the decimal expansion of $\pi$. The result was checked by using a different algorithm, also due to the Borweins, that converges quadratically to $\pi$. 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 $\pi$ 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 $\pi$ to over 134 million digits (January 1987). This paper describes the algorithms and techniques used in the author’s computation, both for converging to $\pi$ and for performing the required multiprecision arithmetic. The results of statistical analyses of the computed decimal expansion are also included.

D. H. Bailey, "A highperformance fast Fourier transform algorithm for the Cray2," J. Supercomputing, v. 1, 1987, pp. 4360.
 Petr Beckmann, A history of $\pi $ (pi), 2nd ed., The Golem Press, Boulder, Colo., 1971. MR 0449960
 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
 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, DOI https://doi.org/10.1137/1026073
 J. M. Borwein and P. B. Borwein, More quadratically converging algorithms for $\pi $, Math. Comp. 46 (1986), no. 173, 247–253. MR 815846, DOI https://doi.org/10.1090/S00255718198608158466 J. M. Borwein & P. B. Borwein, Pi and the AGM—A Study in Analytic Number Theory and Computational Complexity, Wiley, New York, 1987.
 Richard P. Brent, Fast multipleprecision evaluation of elementary functions, J. Assoc. Comput. Mach. 23 (1976), no. 2, 242–251. MR 395314, DOI https://doi.org/10.1145/321941.321944 E. O. Brigham, The Fast Fourier Transform, PrenticeHall, Englewood Cliffs, N. J., 1974. W. Gosper, private communication.
 Emil Grosswald, Topics from the theory of numbers, The Macmillan Co., New York; CollierMacmillan Ltd., London, 1966. MR 0228408 G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, London, 1984. Y. Kanada & Y. Tamura, Calculation of $\pi$ to 10,013,395 Decimal Places Based on the GaussLegendre Algorithm and Gauss Arctangent Relation, Computer Centre, University of Tokyo, 1983.
 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
 Eugene Salamin, Computation of $\pi $ using arithmeticgeometric mean, Math. Comp. 30 (1976), no. 135, 565–570. MR 404124, DOI https://doi.org/10.1090/S00255718197604041249
 Daniel Shanks and John W. Wrench Jr., Calculation of $\pi $ to 100,000 decimals, Math. Comp. 16 (1962), 76–99. MR 136051, DOI https://doi.org/10.1090/S00255718196201360519 P. Swarztrauber, "FFT algorithms for vector computers," Parallel Comput., v. 1, 1984, pp. 4564.
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
Article copyright:
© Copyright 1988
American Mathematical Society