In mathematics, Borwein's algorithm is an algorithm devised by Jonathan and Peter Borwein to calculate the value of 1/π. They devised several other algorithms. They published the book Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity.[1]
Then pk converges quadratically to π; that is, each iteration approximately doubles the number of correct digits. The algorithm is not self-correcting; each iteration must be performed with the desired number of correct digits for π's final result.
Cubic convergence (1991)edit
Start by setting
Then iterate
Then ak converges cubically to 1/π; that is, each iteration approximately triples the number of correct digits.
Then ak converges quartically against 1/π; that is, each iteration approximately quadruples the number of correct digits. The algorithm is not self-correcting; each iteration must be performed with the desired number of correct digits for π's final result.
One iteration of this algorithm is equivalent to two iterations of the Gauss–Legendre algorithm. A proof of these algorithms can be found here:[4]
Then ak converges quintically to 1/π (that is, each iteration approximately quintuples the number of correct digits), and the following condition holds:
Nonic convergenceedit
Start by setting
Then iterate
Then ak converges nonically to 1/π; that is, each iteration approximately multiplies the number of correct digits by nine.[5]
^Jonathan M. Borwein, Peter B. Borwein, Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity, Wiley, New York, 1987. Many of their results are available in: Jorg Arndt, Christoph Haenel, Pi Unleashed, Springer, Berlin, 2001, ISBN3-540-66572-2
^Arndt, Jörg; Haenel, Christoph (1998). π Unleashed. Springer-Verlag. p. 236. ISBN3-540-66572-2.
^Mak, Ronald (2003). The Java Programmers Guide to Numerical Computation. Pearson Educational. p. 353. ISBN0-13-046041-9.
^Milla, Lorenz (2019), Easy Proof of Three Recursive π-Algorithms, arXiv:1907.04110
^Henrik Vestermark (4 November 2016). "Practical implementation of π Algorithms" (PDF). Retrieved 29 November 2020.
External linksedit
Pi Formulas from Wolfram MathWorld
January 01, 2024
borwein, algorithm, mathematics, algorithm, devised, jonathan, peter, borwein, calculate, value, they, devised, several, other, algorithms, they, published, book, study, analytic, number, theory, computational, complexity, contents, ramanujan, sato, series, cl. In mathematics Borwein s algorithm is an algorithm devised by Jonathan and Peter Borwein to calculate the value of 1 p They devised several other algorithms They published the book Pi and the AGM A Study in Analytic Number Theory and Computational Complexity 1 Contents 1 Ramanujan Sato series 1 1 Class number 2 1989 1 2 Class number 4 1993 2 Iterative algorithms 2 1 Quadratic convergence 1984 2 2 Cubic convergence 1991 2 3 Quartic convergence 1985 2 4 Quintic convergence 2 5 Nonic convergence 3 See also 4 References 5 External linksRamanujan Sato series editThese two are examples of a Ramanujan Sato series The related Chudnovsky algorithm uses a discriminant with class number 1 Class number 2 1989 edit Start by setting citation needed A 212175710912 61 1657145277365 B 13773980892672 61 107578229802750 C 5280 236674 30303 61 3 displaystyle begin aligned A amp 212175710912 sqrt 61 1657145277365 B amp 13773980892672 sqrt 61 107578229802750 C amp left 5280 left 236674 30303 sqrt 61 right right 3 end aligned nbsp Then 1 p 12 n 0 1 n 6 n A n B n 3 3 n C n 1 2 displaystyle frac 1 pi 12 sum n 0 infty frac 1 n 6n A nB n 3 3n C n frac 1 2 nbsp Each additional term of the partial sum yields approximately 25 digits Class number 4 1993 edit Start by setting citation needed A 63365028312971999585426220 28337702140800842046825600 5 384 5 10891728551171178200467436212395209160385656017 4870929086578810225077338534541688721351255040 5 1 2 B 7849910453496627210289749000 3510586678260932028965606400 5 2515968 3110 6260208323789001636993322654444020882161 2799650273060444296577206890718825190235 5 1 2 C 214772995063512240 96049403338648032 5 1296 5 10985234579463550323713318473 4912746253692362754607395912 5 1 2 displaystyle begin aligned A amp 63365028312971999585426220 amp 28337702140800842046825600 sqrt 5 amp 384 sqrt 5 big 10891728551171178200467436212395209160385656017 amp left 4870929086578810225077338534541688721351255040 sqrt 5 right frac 1 2 B amp 7849910453496627210289749000 amp 3510586678260932028965606400 sqrt 5 amp 2515968 sqrt 3110 big 6260208323789001636993322654444020882161 amp left 2799650273060444296577206890718825190235 sqrt 5 right frac 1 2 C amp 214772995063512240 amp 96049403338648032 sqrt 5 amp 1296 sqrt 5 big 10985234579463550323713318473 amp left 4912746253692362754607395912 sqrt 5 right frac 1 2 end aligned nbsp Then C 3 p n 0 6 n 3 n n 3 A n B C 3 n displaystyle frac sqrt C 3 pi sum n 0 infty frac 6n 3n n 3 frac A nB C 3n nbsp Each additional term of the series yields approximately 50 digits Iterative algorithms editQuadratic convergence 1984 edit Start by setting 2 a 0 2 b 0 0 p 0 2 2 displaystyle begin aligned a 0 amp sqrt 2 b 0 amp 0 p 0 amp 2 sqrt 2 end aligned nbsp Then iterate a n 1 a n 1 a n 2 b n 1 1 b n a n a n b n p n 1 1 a n 1 p n b n 1 1 b n 1 displaystyle begin aligned a n 1 amp frac sqrt a n frac 1 sqrt a n 2 b n 1 amp frac 1 b n sqrt a n a n b n p n 1 amp frac 1 a n 1 p n b n 1 1 b n 1 end aligned nbsp Then pk converges quadratically to p that is each iteration approximately doubles the number of correct digits The algorithm is not self correcting each iteration must be performed with the desired number of correct digits for p s final result Cubic convergence 1991 edit Start by setting a 0 1 3 s 0 3 1 2 displaystyle begin aligned a 0 amp frac 1 3 s 0 amp frac sqrt 3 1 2 end aligned nbsp Then iterate r k 1 3 1 2 1 s k 3 1 3 s k 1 r k 1 1 2 a k 1 r k 1 2 a k 3 k r k 1 2 1 displaystyle begin aligned r k 1 amp frac 3 1 2 left 1 s k 3 right frac 1 3 s k 1 amp frac r k 1 1 2 a k 1 amp r k 1 2 a k 3 k left r k 1 2 1 right end aligned nbsp Then ak converges cubically to 1 p that is each iteration approximately triples the number of correct digits Quartic convergence 1985 edit Start by setting 3 a 0 2 2 1 2 y 0 2 1 displaystyle begin aligned a 0 amp 2 left sqrt 2 1 right 2 y 0 amp sqrt 2 1 end aligned nbsp Then iterate y k 1 1 1 y k 4 1 4 1 1 y k 4 1 4 a k 1 a k 1 y k 1 4 2 2 k 3 y k 1 1 y k 1 y k 1 2 displaystyle begin aligned y k 1 amp frac 1 left 1 y k 4 right frac 1 4 1 left 1 y k 4 right frac 1 4 a k 1 amp a k left 1 y k 1 right 4 2 2k 3 y k 1 left 1 y k 1 y k 1 2 right end aligned nbsp Then ak converges quartically against 1 p that is each iteration approximately quadruples the number of correct digits The algorithm is not self correcting each iteration must be performed with the desired number of correct digits for p s final result One iteration of this algorithm is equivalent to two iterations of the Gauss Legendre algorithm A proof of these algorithms can be found here 4 Quintic convergence edit Start by setting a 0 1 2 s 0 5 5 2 5 ϕ 3 displaystyle begin aligned a 0 amp frac 1 2 s 0 amp 5 left sqrt 5 2 right frac 5 phi 3 end aligned nbsp where ϕ 1 5 2 displaystyle phi tfrac 1 sqrt 5 2 nbsp is the golden ratio Then iterate x n 1 5 s n 1 y n 1 x n 1 1 2 7 z n 1 1 2 x n 1 y n 1 y n 1 2 4 x n 1 3 1 5 a n 1 s n 2 a n 5 n s n 2 5 2 s n s n 2 2 s n 5 s n 1 25 z n 1 x n 1 z n 1 1 2 s n displaystyle begin aligned x n 1 amp frac 5 s n 1 y n 1 amp left x n 1 1 right 2 7 z n 1 amp left frac 1 2 x n 1 left y n 1 sqrt y n 1 2 4x n 1 3 right right frac 1 5 a n 1 amp s n 2 a n 5 n left frac s n 2 5 2 sqrt s n left s n 2 2s n 5 right right s n 1 amp frac 25 left z n 1 frac x n 1 z n 1 1 right 2 s n end aligned nbsp Then ak converges quintically to 1 p that is each iteration approximately quintuples the number of correct digits and the following condition holds 0 lt a n 1 p lt 16 5 n e 5 n p displaystyle 0 lt a n frac 1 pi lt 16 cdot 5 n cdot e 5 n pi nbsp Nonic convergence edit Start by setting a 0 1 3 r 0 3 1 2 s 0 1 r 0 3 1 3 displaystyle begin aligned a 0 amp frac 1 3 r 0 amp frac sqrt 3 1 2 s 0 amp left 1 r 0 3 right frac 1 3 end aligned nbsp Then iterate t n 1 1 2 r n u n 1 9 r n 1 r n r n 2 1 3 v n 1 t n 1 2 t n 1 u n 1 u n 1 2 w n 1 27 1 s n s n 2 v n 1 a n 1 w n 1 a n 3 2 n 1 1 w n 1 s n 1 1 r n 3 t n 1 2 u n 1 v n 1 r n 1 1 s n 1 3 1 3 displaystyle begin aligned t n 1 amp 1 2r n u n 1 amp left 9r n left 1 r n r n 2 right right frac 1 3 v n 1 amp t n 1 2 t n 1 u n 1 u n 1 2 w n 1 amp frac 27 left 1 s n s n 2 right v n 1 a n 1 amp w n 1 a n 3 2n 1 left 1 w n 1 right s n 1 amp frac left 1 r n right 3 left t n 1 2u n 1 right v n 1 r n 1 amp left 1 s n 1 3 right frac 1 3 end aligned nbsp Then ak converges nonically to 1 p that is each iteration approximately multiplies the number of correct digits by nine 5 See also editBailey Borwein Plouffe formula Chudnovsky algorithm Gauss Legendre algorithm Ramanujan Sato seriesReferences edit Jonathan M Borwein Peter B Borwein Pi and the AGM A Study in Analytic Number Theory and Computational Complexity Wiley New York 1987 Many of their results are available in Jorg Arndt Christoph Haenel Pi Unleashed Springer Berlin 2001 ISBN 3 540 66572 2 Arndt Jorg Haenel Christoph 1998 p Unleashed Springer Verlag p 236 ISBN 3 540 66572 2 Mak Ronald 2003 The Java Programmers Guide to Numerical Computation Pearson Educational p 353 ISBN 0 13 046041 9 Milla Lorenz 2019 Easy Proof of Three Recursive p Algorithms arXiv 1907 04110 Henrik Vestermark 4 November 2016 Practical implementation of p Algorithms PDF Retrieved 29 November 2020 External links editPi Formulas from Wolfram MathWorld Retrieved from https en wikipedia org w index php title Borwein 27s algorithm amp oldid 1115360750, wikipedia, wiki, book, books, library,
