The computation of to 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

MathSciNet review:
917836

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

**[1]**D. H. Bailey, "A high-performance fast Fourier transform algorithm for the Cray-2,"*J. Supercomputing*, v. 1, 1987, pp. 43-60.**[2]**Petr Beckmann,*A history of 𝜋 (pi)*, 2nd ed., The Golem Press, Boulder, Colo., 1971. MR**0449960****[3]**Allan Borodin and Ian Munro,*The computational complexity of algebraic and numeric problems*, American Elsevier Publishing Co., Inc., New York-London-Amsterdam, 1975. Elsevier Computer Science Library; Theory of Computation Series, No. 1. MR**0468309****[4]**J. M. Borwein and P. B. Borwein,*The arithmetic-geometric mean and fast computation of elementary functions*, SIAM Rev.**26**(1984), no. 3, 351–366. MR**750454**, 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**, 10.1090/S0025-5718-1986-0815846-6**[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]**Richard P. Brent,*Fast multiple-precision evaluation of elementary functions*, J. Assoc. Comput. Mach.**23**(1976), no. 2, 242–251. MR**0395314****[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*, The Macmillan Co., New York; Collier-Macmillan Ltd., London, 1966. MR**0228408****[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 Gauss-Legendre Algorithm and Gauss Arctangent Relation*, Computer Centre, University of Tokyo, 1983.**[13]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[14]**Eugene Salamin,*Computation of 𝜋 using arithmetic-geometric mean*, Math. Comp.**30**(1976), no. 135, 565–570. MR**0404124**, 10.1090/S0025-5718-1976-0404124-9**[15]**Daniel Shanks and John W. Wrench Jr.,*Calculation of 𝜋 to 100,000 decimals*, Math. Comp.**16**(1962), 76–99. MR**0136051**, 10.1090/S0025-5718-1962-0136051-9**[16]**P. Swarztrauber, "FFT algorithms for vector computers,"*Parallel Comput.*, v. 1, 1984, pp. 45-64.

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:
http://dx.doi.org/10.1090/S0025-5718-1988-0917836-3

Article copyright:
© Copyright 1988
American Mathematical Society