×

The Borwein brothers, pi and the AGM. (English) Zbl 1437.11001

Bailey, David H. (ed.) et al., From analysis to visualization. A celebration of the life and legacy of Jonathan M. Borwein, Callaghan, Australia, September 25–29, 2017. Cham: Springer. Springer Proc. Math. Stat. 313, 323-347 (2020).
Summary: We consider some of J. M. Borwein and P. B. Borwein’ contributions to the high-precision computation of \(\pi\) and the elementary functions, with particular reference to their book [Pi and the AGM. A study in analytic number theory and computational complexity. New York, NY: John Wiley (1987; Zbl 0611.10001)]. Here “AGM” is the arithmetic-geometric mean of Gauss and Legendre. Because the AGM converges quadratically, it can be combined with fast multiplication algorithms to give fast algorithms for the \(n\)-bit computation of \(\pi\), and more generally the elementary functions. These algorithms run in “almost linear” time \(O(M(n)\log n)\), where \(M(n)\) is the time for \(n\)-bit multiplication. We outline some of the results and algorithms given in Pi and the AGM, and present some related (but new) results. In particular, we improve the published error bounds for some quadratically and quartically convergent algorithms for \(\pi\), such as the Gauss-Legendre algorithm. We show that an iteration of the Borwein-Borwein quartic algorithm for \(\pi\) is equivalent to two iterations of the Gauss-Legendre quadratic algorithm for \(\pi \), in the sense that they produce exactly the same sequence of approximations to \(\pi\) if performed using exact arithmetic.
For the entire collection see [Zbl 1442.00024].

MSC:

11-03 History of number theory
11Y60 Evaluation of number-theoretic constants
01A70 Biographies, obituaries, personalia, bibliographies
33E05 Elliptic functions and integrals
11Y16 Number-theoretic algorithms; complexity
65B99 Acceleration of convergence in numerical analysis
68Q25 Analysis of algorithms and problem complexity

Biographic References:

Borwein, Jonathan; Borwein, Peter

Citations:

Zbl 0611.10001

Software:

Magma
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions. Dover, New York (1965). Online version at http://people.math.sfu.ca/ cbm/aands/. Accessed 7 Aug 2018 · Zbl 0171.38503
[2] Andrews, G.E.: Pi and the AGM: a study in analytic number theory and computational complexity. Book review in Bull. (NS) AMS 22, 198-201 (1990)
[3] Askey, R.: Book review: Pi and the AGM. Am. Math. Mon. 95, 895-897 (1988)
[4] Bailey, D.H.: The computation of \(\pi\) to 29,360,000 decimal digits using Borweins’ quartically convergent algorithm. Math. Comput. 50, 283-296 (1988) · Zbl 0641.10002
[5] Bailey, D.H.: A collection of mathematical formulas involving \(\pi \), Feb. 6 (2018). http://www.davidhbailey.com/dhbpapers/pi-formulas.pdf. Aaccessed 7 Aug 2018
[6] Bailey, D.H., Borwein, J.M.: Pi: The Next Generation. Springer, Berlin (2016) · Zbl 1342.01042 · doi:10.1007/978-3-319-32377-0
[7] Baruah, N.D., Berndt, B.C., Chan, H.H.: Ramanujan’s series for \(1/\pi \): a survey. Am. Math. Mon. 116, 567-587 (2009) · Zbl 1229.11162 · doi:10.1080/00029890.2009.11920975
[8] Beeler, M., Gosper, R.W., Schroeppel, R.: HAKMEM, AI Memo 239, MIT AI Lab (1972). (Item 143 by E. Salamin.)
[9] Berndt, B.C.: Book review: Pi and the AGM. Math. Comput. 50, 352-354 (1988) · doi:10.2307/2007942
[10] Borwein, J.M.: The life of pi: from Archimedes to Eniac and beyond, prepared for Berggren Festschrift (2012). https://www.carma.newcastle.edu.au/jon/pi-2012.pdf. Accessed 7 Aug 2018
[11] Borwein, J.M., Lectures and presentations. https://www.carma.newcastle.edu.au/jon/index-talks.shtml. Accessed 7 Aug 2018
[12] Borwein, J.M., Borwein, P.B.: The arithmetic-geometric mean and fast computation of elementary functions. SIAM Rev. 26, 351-365 (1984) · Zbl 0557.65009 · doi:10.1137/1026073
[13] Borwein, J.M., Borwein, P.B.: More quadratically convergent algorithms for \(\pi \). Math. Comput. 46, 247-253 (1986) · Zbl 0589.65016
[14] Borwein, J.M., Borwein, P.B.: Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. Monographies et Études de la Société Mathématique du Canada. Wiley, Toronto (1987) · Zbl 0611.10001
[15] Borwein, J.M., Borwein, P.B., Bailey, D.H.: Ramanujan, modular equations, and approximations to pi or how to compute one billion digits of pi. Am. Math. Mon. 96, 201-219 (1989) · Zbl 0672.10017 · doi:10.1080/00029890.1989.11972169
[16] Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language, J. Symb. Comput. 24, 235-265 (1997) · Zbl 0898.68039
[17] Brent, R.P.: Some efficient algorithms for solving systems of nonlinear equations. SIAM J. Numer. Anal. 10, 327-344 (1973) · Zbl 0258.65051 · doi:10.1137/0710031
[18] Brent, R.P.: Multiple-precision zero-finding methods and the complexity of elementary function evaluation. In: Traub, J.F. (ed.) Analytic Computational Complexity, pp. 151-176. Academic, New York (1975) · Zbl 0342.65031
[19] Brent, R.P.: The complexity of multiple-precision arithmetic. In: Anderssen, R.S., Brent, R.P. (eds.) The Complexity of Computational Problem Solving, pp. 126-165. University of Queensland Press, Brisbane (1976)
[20] Brent, R.P.: Fast multiple-precision evaluation of elementary functions. J. ACM 23, 242-251 (1976) · Zbl 0324.65018 · doi:10.1145/321941.321944
[21] Brent, R.P.: Old and new algorithms for \(\pi \). Notices AMS 60, 7 (2013)
[22] Brent, R.P.: Jonathan Borwein, Pi and the AGM, Keynote Talk at the Jonathan Borwein Commemorative Conference, Newcastle, NSW (2017). http://maths-people.anu.edu.au/ brent/talks.html. Accessed 7 Aug 2018
[23] Brent, R.P., Zimmermann, P.: Modern Computer Arithmetic. Cambridge University Press, Cambridge (2010) · Zbl 1230.68014 · doi:10.1017/CBO9780511921698
[24] Chudnovsky, D.V., Chudnovsky, G.V.: The computation of classical constants. Proc. Nat. Acad. Sci. USA 88(21), 8178-8182 (1989) · Zbl 0683.65008 · doi:10.1073/pnas.86.21.8178
[25] Cox, D.A.: The arithmetic-geometric mean of Gauss. L’Enseignement Mathématique 30, 275-330 (1984) · Zbl 0583.33002
[26] Gauss, C.F.: Unpublished Notebook Entry of May 1809, Reproduced in J. Arndt and C. Haenel, Pi: Algorithmen, Computer, Arithmetik, Chap. 7, p. 99. Springer, Berlin (1998)
[27] Gauss, C.F.: Carl Friedrich Gauss Werke, Bd. 3, Göttingen, 1876, 362-403
[28] Gourdon, X., Sebah, P.: Binary splitting method (2001). http://numbers.computation.free.fr/Constants/Algorithms/splitting.html. Accessed 7 Aug 2018
[29] Guillera, J.: Easy proofs of some Borwein algorithms for \(\pi \). Am. Math. Mon. 115, 850-854 (2008) · Zbl 1178.26003 · doi:10.1080/00029890.2008.11920601
[30] Guillera, J.: New proofs of Borwein-type algorithms for Pi. Integr. Transform. Spec. Funct. 27, 775-782 (2016) · Zbl 1402.11153 · doi:10.1080/10652469.2016.1200573
[31] Harvey, D., van der Hoeven, J., Lecerf, G.: Even faster integer multiplication. J. Complex. 36, 1-30 (2016) · Zbl 1350.68145 · doi:10.1016/j.jco.2016.03.001
[32] Jacobi, C.G.J.: Fundamenta Nova Theoriae Functionum Ellipticarum, Königsberg, 1829. Reprinted in Gesammelte Mathematische Werke 1, 255-263 (1829)
[33] Kanada, Y.: Vectorization of multiple-precision arithmetic program and 201,326,000 decimal digits of pi calculation. In Supercomputing 88. IEEE 117-128 (1988)
[34] Karatsuba, E.A.: Fast evaluations of transcendental functions. Probl. Peredachi Informat. 27, 4 (1991). Also https://en.wikipedia.org/wiki/FEE_method. Accessed 7 Aug 2018 · Zbl 0754.65021
[35] Knopp, K.: The Elementary Functions, §23 in Theory of Functions Parts I and II, pp. 96-98. Dover, New York (1996) l
[36] Legendre, A.M.: Exercices de Calcul Integral, vol. 1, p. 61. Paris (1811)
[37] Liouville, J.: Sur la classification des Transcendantes et sur l’impossibilité d’exprimer les racines des certaines équations en fonction finie explicite des coefficients. Part 1. J. Math. Pure Appl. 2, 56-105 (1837). Also Part 2, ibid 3, 523-547 (1838)
[38] Mahler, K.: On the approximation of \(\pi \). Proc. Kon. Nederlandsche Akad. v. Wetenschappen Ser. A \(56, 30-42 (1953) =\) Indag. Math. 15, 30-42 (1953). Also https://carma.newcastle.edu.au/mahler/docs/119.pdf. Accessed 7 Aug 2018 · Zbl 0053.36105
[39] Ostrowski, A.M.: Solution of Equations and Systems of Equations. Academic Press, New York (1960) · Zbl 0115.11201
[40] Ramanujan, S.: Modular equations and approximations to pi. Quart. J. Math. (Oxford) 45, 350-372 (1914)
[41] Ritt, J.F.: Integration in Finite Terms. Columbia University Press, New York (1948) · Zbl 0031.20603 · doi:10.7312/ritt91596
[42] Salamin, E.: Computation of \(\pi\) using arithmetic-geometric mean. Math. Comput. 30, 565-570 (1976) · Zbl 0345.10003
[43] Sasaki, T., Kanada, Y.: Practically fast multiple-precision evaluation of \(\log (x)\). J. Inf. Process. 5, 247-250 (1982) · Zbl 0501.65008
[44] Smith, D.M.: Efficient multiple-precision evaluation of elementary functions. Math. Comput. 52, 131-134 (1989) · Zbl 0657.65032 · doi:10.1090/S0025-5718-1989-0971406-0
[45] Sturm, J.C.F.: Mémoire sur la résolution des équations numériques. Bulletin des Sciences de Férussac 11, 419-425 (1829)
[46] Watson, G.N.: A Treatise on the Theory of Bessel Functions, 2nd edn. Cambridge (1966) · Zbl 0174.36202
[47] Whittaker, E.T., Watson, G.N.: A Course of Modern Analysis, 3rd edn. Cambridge (1920). Also http://archive.org/details/cu31924001549660. Accessed 7 Aug 2018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.