TY - GEN
T1 - The borwein brothers, pi and the AGM
AU - Brent, Richard P.
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2020.
PY - 2020
Y1 - 2020
N2 - We consider some of Jonathan and Peter Borweins’ contributions to the high-precision computation of π and the elementary functions, with particular reference to their book Pi and the AGM (Wiley, 1987). 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 π, and more generally the elementary functions. These algorithms run in “almost linear” time (Formula Presented), 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 π, such as the Gauss–Legendre algorithm. We show that an iteration of the Borwein-Borwein quartic algorithm for π is equivalent to two iterations of the Gauss–Legendre quadratic algorithm for π, in the sense that they produce exactly the same sequence of approximations to π if performed using exact arithmetic.
AB - We consider some of Jonathan and Peter Borweins’ contributions to the high-precision computation of π and the elementary functions, with particular reference to their book Pi and the AGM (Wiley, 1987). 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 π, and more generally the elementary functions. These algorithms run in “almost linear” time (Formula Presented), 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 π, such as the Gauss–Legendre algorithm. We show that an iteration of the Borwein-Borwein quartic algorithm for π is equivalent to two iterations of the Gauss–Legendre quadratic algorithm for π, in the sense that they produce exactly the same sequence of approximations to π if performed using exact arithmetic.
KW - Arithmetic–geometric mean
KW - Borwein-Borwein algorithm
KW - Borwein-Borwein quartic algorithm
KW - Brent-Salamin algorithm
KW - Chudnovsky algorithm
KW - Computation of π
KW - Computational complexity
KW - Elliptic integrals
KW - Equivalence of algorithms for π
KW - Evaluation of elementary functions
KW - Gauss–Legendre algorithm
KW - Linear convergence
KW - Quadratic convergence
KW - Quartic convergence
KW - Ramanujan–Sato algorithms
KW - Sasaki–Kanada algorithm
KW - Theta functions
UR - http://www.scopus.com/inward/record.url?scp=85082990662&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-36568-4_21
DO - 10.1007/978-3-030-36568-4_21
M3 - Conference contribution
SN - 9783030365677
T3 - Springer Proceedings in Mathematics and Statistics
SP - 323
EP - 347
BT - From Analysis to Visualization - A Celebration of the Life and Legacy of Jonathan M. Borwein, 2017
A2 - Bailey, David H.
A2 - Borwein, Naomi Simone
A2 - Brent, Richard P.
A2 - Burachik, Regina S.
A2 - Osborn, Judy-anne Heather
A2 - Sims, Brailey
A2 - Zhu, Qiji J.
PB - Springer
T2 - Jonathan Borwein Commemorative Conference, JBCC 2017
Y2 - 25 September 2017 through 29 September 2017
ER -