The computation of $\pi$ to $29,360,000$ decimal digits using Borweins’ quartically convergent algorithm
HTML articles powered by AMS MathViewer
 by David H. Bailey PDF
 Math. Comp. 50 (1988), 283296 Request permission
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.References

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, Elsevier Computer Science Library: Theory of Computation Series, No. 1, American Elsevier Publishing Co., Inc., New YorkLondonAmsterdam, 1975. 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 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 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 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 Company, New York; Collier Macmillan 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 Series in Computer Science and Information Processing, AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
 Eugene Salamin, Computation of $\pi$ using arithmeticgeometric mean, Math. Comp. 30 (1976), no. 135, 565–570. MR 404124, DOI 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 10.1090/S00255718196201360519 P. Swarztrauber, "FFT algorithms for vector computers," Parallel Comput., v. 1, 1984, pp. 4564.
Additional Information
 © Copyright 1988 American Mathematical Society
 Journal: Math. Comp. 50 (1988), 283296
 MSC: Primary 11Y60; Secondary 1104, 11K16, 6504
 DOI: https://doi.org/10.1090/S00255718198809178363
 MathSciNet review: 917836