Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Borwein's algorithm
open-in-new
<h2 id="ramanujansato-series">Ramanujan–Sato series</h2> <p>These two are examples of a <a href="/facts/Ramanujan%25E2%2580%2593Sato_series/umUvetRJ">Ramanujan–Sato series</a>. The related <a href="/facts/Chudnovsky_algorithm/cQmCNhEn">Chudnovsky algorithm</a> uses a discriminant with class number 1. </p> <h3>Class number 2 (1989)</h3> <p>Start by setting<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p> A = 212175710912 61 + 1657145277365 B = 13773980892672 61 + 107578229802750 C = ( 5280 ( 236674 + 30303 61 ) ) 3 {\displaystyle {\begin{aligned}A&=212175710912{\sqrt {61}}+1657145277365\\B&=13773980892672{\sqrt {61}}+107578229802750\\C&=\left(5280\left(236674+30303{\sqrt {61}}\right)\right)^{3}\end{aligned}}} <p>Then </p> 1 π = 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}}}}}} <p>Each additional term of the partial sum yields approximately 25 digits. </p> <h3>Class number 4 (1993)</h3> <p>Start by setting<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> 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={}&63365028312971999585426220\\&{}+28337702140800842046825600{\sqrt {5}}\\&{}+384{\sqrt {5}}{\big (}10891728551171178200467436212395209160385656017\\&{}+\left.4870929086578810225077338534541688721351255040{\sqrt {5}}\right)^{\frac {1}{2}}\\B={}&7849910453496627210289749000\\&{}+3510586678260932028965606400{\sqrt {5}}\\&{}+2515968{\sqrt {3110}}{\big (}6260208323789001636993322654444020882161\\&{}+\left.2799650273060444296577206890718825190235{\sqrt {5}}\right)^{\frac {1}{2}}\\C={}&-214772995063512240\\&{}-96049403338648032{\sqrt {5}}\\&{}-1296{\sqrt {5}}{\big (}10985234579463550323713318473\\&{}+\left.4912746253692362754607395912{\sqrt {5}}\right)^{\frac {1}{2}}\end{aligned}}} <p>Then </p> − C 3 π = ∑ 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}}}}} <p>Each additional term of the series yields approximately 50 digits. </p> <h2 id="iterative-algorithms">Iterative algorithms</h2> <h3>Quadratic convergence (1984)</h3> <p>Start by setting<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> a 0 = 2 b 0 = 0 p 0 = 2 + 2 {\displaystyle {\begin{aligned}a_{0}&={\sqrt {2}}\\b_{0}&=0\\p_{0}&=2+{\sqrt {2}}\end{aligned}}} <p>Then iterate </p> 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}&={\frac {{\sqrt {a_{n}}}+{\frac {1}{\sqrt {a_{n}}}}}{2}}\\b_{n+1}&={\frac {(1+b_{n}){\sqrt {a_{n}}}}{a_{n}+b_{n}}}\\p_{n+1}&={\frac {(1+a_{n+1})\,p_{n}b_{n+1}}{1+b_{n+1}}}\end{aligned}}} <p>Then <i>p</i><i>k</i> converges quadratically to π; that is, each iteration approximately doubles the number of correct digits. The algorithm is <i>not</i> self-correcting; each iteration must be performed with the desired number of correct digits for π's final result. </p> <h3>Cubic convergence (1991)</h3> <p>Start by setting </p> a 0 = 1 3 s 0 = 3 − 1 2 {\displaystyle {\begin{aligned}a_{0}&={\frac {1}{3}}\\s_{0}&={\frac {{\sqrt {3}}-1}{2}}\end{aligned}}} <p>Then iterate </p> 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}&={\frac {3}{1+2\left(1-s_{k}^{3}\right)^{\frac {1}{3}}}}\\s_{k+1}&={\frac {r_{k+1}-1}{2}}\\a_{k+1}&=r_{k+1}^{2}a_{k}-3^{k}\left(r_{k+1}^{2}-1\right)\end{aligned}}} <p>Then <i>ak</i> converges cubically to 1/π; that is, each iteration approximately triples the number of correct digits. </p> <h3>Quartic convergence (1985)</h3> <p>Start by setting<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p> a 0 = 2 ( 2 − 1 ) 2 y 0 = 2 − 1 {\displaystyle {\begin{aligned}a_{0}&=2\left({\sqrt {2}}-1\right)^{2}\\y_{0}&={\sqrt {2}}-1\end{aligned}}} <p>Then iterate </p> 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}&={\frac {1-\left(1-y_{k}^{4}\right)^{\frac {1}{4}}}{1+\left(1-y_{k}^{4}\right)^{\frac {1}{4}}}}\\a_{k+1}&=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}}} <p>Then <i>a</i><i>k</i> converges quartically against 1/π; that is, each iteration approximately quadruples the number of correct digits. The algorithm is <i>not</i> self-correcting; each iteration must be performed with the desired number of correct digits for π's final result. </p><p>One iteration of this algorithm is equivalent to two iterations of the <a href="/facts/Gauss%25E2%2580%2593Legendre_algorithm/QqzIk2L6">Gauss–Legendre algorithm</a>. A proof of these algorithms can be found here:<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h3>Quintic convergence</h3> <p>Start by setting </p> a 0 = 1 2 s 0 = 5 ( 5 − 2 ) = 5 ϕ 3 {\displaystyle {\begin{aligned}a_{0}&={\frac {1}{2}}\\s_{0}&=5\left({\sqrt {5}}-2\right)={\frac {5}{\phi ^{3}}}\end{aligned}}} <p>where ϕ = 1 + 5 2 {\displaystyle \phi ={\tfrac {1+{\sqrt {5}}}{2}}} is the <a href="/facts/Golden_ratio/anloSRmD">golden ratio</a>. Then iterate </p> 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}&={\frac {5}{s_{n}}}-1\\y_{n+1}&=\left(x_{n+1}-1\right)^{2}+7\\z_{n+1}&=\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}&=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}&={\frac {25}{\left(z_{n+1}+{\frac {x_{n+1}}{z_{n+1}}}+1\right)^{2}s_{n}}}\end{aligned}}} <p>Then ak converges quintically to 1/π (that is, each iteration approximately quintuples the number of correct digits), and the following condition holds: </p> 0 < a n − 1 π < 16 ⋅ 5 n ⋅ e − 5 n π {\displaystyle 0<a_{n}-{\frac {1}{\pi }}<16\cdot 5^{n}\cdot e^{-5^{n}}\pi \,\!} <h3>Nonic convergence</h3> <p>Start by setting </p> a 0 = 1 3 r 0 = 3 − 1 2 s 0 = ( 1 − r 0 3 ) 1 3 {\displaystyle {\begin{aligned}a_{0}&={\frac {1}{3}}\\r_{0}&={\frac {{\sqrt {3}}-1}{2}}\\s_{0}&=\left(1-r_{0}^{3}\right)^{\frac {1}{3}}\end{aligned}}} <p>Then iterate </p> 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}&=1+2r_{n}\\u_{n+1}&=\left(9r_{n}\left(1+r_{n}+r_{n}^{2}\right)\right)^{\frac {1}{3}}\\v_{n+1}&=t_{n+1}^{2}+t_{n+1}u_{n+1}+u_{n+1}^{2}\\w_{n+1}&={\frac {27\left(1+s_{n}+s_{n}^{2}\right)}{v_{n+1}}}\\a_{n+1}&=w_{n+1}a_{n}+3^{2n-1}\left(1-w_{n+1}\right)\\s_{n+1}&={\frac {\left(1-r_{n}\right)^{3}}{\left(t_{n+1}+2u_{n+1}\right)v_{n+1}}}\\r_{n+1}&=\left(1-s_{n+1}^{3}\right)^{\frac {1}{3}}\end{aligned}}} <p>Then <i>a</i><i>k</i> converges nonically to 1/π; that is, each iteration approximately multiplies the number of correct digits by nine.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <h2 id="see-also">See also</h2> <ul> <li>Mathematics portal</li></ul> <ul><li><a href="/facts/Bailey%25E2%2580%2593Borwein%25E2%2580%2593Plouffe_formula/m4v34n9d">Bailey–Borwein–Plouffe formula</a></li> <li><a href="/facts/Chudnovsky_algorithm/cQmCNhEn">Chudnovsky algorithm</a></li> <li><a href="/facts/Gauss%25E2%2580%2593Legendre_algorithm/QqzIk2L6">Gauss–Legendre algorithm</a></li> <li><a href="/facts/Ramanujan%25E2%2580%2593Sato_series/umUvetRJ">Ramanujan–Sato series</a></li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://mathworld.wolfram.com/PiFormulas.html">Pi Formulas</a> from Wolfram MathWorld</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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 <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Bailey, David H (2023-04-01). "Peter Borwein: A Visionary Mathematician". Notices of the American Mathematical Society. 70 (4): 610–613. doi:10.1090/noti2675. ISSN 0002-9920. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Borwein, J.M.; Borwein, P.B. (1993). "Class number three Ramanujan type series for 1/π". Journal of Computational and Applied Mathematics. 46 (1–2): 281–290. doi:10.1016/0377-0427(93)90302-R. <a href="https://doi.org/10.1016%2F0377-0427%2893%2990302-R" target="_blank">https://doi.org/10.1016%2F0377-0427%2893%2990302-R</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Arndt, Jörg; Haenel, Christoph (1998). π Unleashed. Springer-Verlag. p. 236. ISBN 3-540-66572-2. <a href="3-540-66572-2" target="_blank">3-540-66572-2</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Mak, Ronald (2003). The Java Programmers Guide to Numerical Computation. Pearson Educational. p. 353. ISBN 0-13-046041-9. <a href="0-13-046041-9" target="_blank">0-13-046041-9</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Milla, Lorenz (2019), Easy Proof of Three Recursive π-Algorithms, arXiv:1907.04110 <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Henrik Vestermark (4 November 2016). "Practical implementation of π Algorithms" (PDF). Retrieved 29 November 2020. <a href="http://www.hvks.com/Numerical/Downloads/HVE%20Practical%20implementation%20of%20PI%20Algorithms.pdf" target="_blank">http://www.hvks.com/Numerical/Downloads/HVE%20Practical%20implementation%20of%20PI%20Algorithms.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> </ol>