Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

The computation of $ \pi$ to $ 29,360,000$ decimal digits using Borweins' quartically convergent algorithm


Author: David H. Bailey
Journal: Math. Comp. 50 (1988), 283-296
MSC: Primary 11Y60; Secondary 11-04, 11K16, 65-04
DOI: https://doi.org/10.1090/S0025-5718-1988-0917836-3
MathSciNet review: 917836
Full-text PDF

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 multi-precision 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 Cray-2 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 Cray-2.

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 S-810 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 multi-precision arithmetic. The results of statistical analyses of the computed decimal expansion are also included.


References [Enhancements On Off] (What's this?)

  • [1] D. H. Bailey, "A high-performance fast Fourier transform algorithm for the Cray-2," J. Supercomputing, v. 1, 1987, pp. 43-60.
  • [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 arithmetic-geometric mean and fast computation of elementary functions," SIAM Rev., v. 26, 1984, pp. 351-366. MR 750454 (86d:65029)
  • [5] J. M. Borwein & P. B. Borwein, "More quadratically converging algorithms for $ \pi $," Math. Comp., v. 46, 1986, pp. 247-253. MR 815846 (87e:65014)
  • [6] J. M. Borwein & P. B. Borwein, Pi and the AGM--A Study in Analytic Number Theory and Computational Complexity, Wiley, New York, 1987.
  • [7] R. P. Brent, "Fast multiple-precision evaluation of elementary functions," J. Assoc. Comput. Mach., v. 23, 1976, pp. 242-251. MR 0395314 (52:16111)
  • [8] E. O. Brigham, The Fast Fourier Transform, Prentice-Hall, 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 $ \pi $ to 10,013,395 Decimal Places Based on the Gauss-Legendre Algorithm and Gauss Arctangent Relation, Computer Centre, University of Tokyo, 1983.
  • [13] D. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [14] E. Salamin, "Computation of $ \pi $ using arithmetic-geometric mean," Math. Comp., v. 30, 1976, pp. 565-570. MR 0404124 (53:7928)
  • [15] D. Shanks & J. W. Wrench, Jr., "Calculation of $ \pi $ to 100,000 decimals," Math. Comp., v. 16, 1962, pp. 76-99. MR 0136051 (24:B2090)
  • [16] P. Swarztrauber, "FFT algorithms for vector computers," Parallel Comput., v. 1, 1984, pp. 45-64.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y60, 11-04, 11K16, 65-04

Retrieve articles in all journals with MSC: 11Y60, 11-04, 11K16, 65-04


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1988-0917836-3
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society