Misplaced Pages

Borwein's algorithm

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Borweins algorithm) Method for calculating the value of pi

Borwein's algorithm was devised by Jonathan and Peter Borwein to calculate the value of 1 / π {\displaystyle 1/\pi } . This and other algorithms can be found in the book Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity.

Ramanujan–Sato series

These two are examples of a Ramanujan–Sato series. The related Chudnovsky algorithm uses a discriminant with class number 1.

Class number 2 (1989)

Start by setting

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}}}

Then

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}}}}}}

Each additional term of the partial sum yields approximately 25 digits.

Class number 4 (1993)

Start by setting

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}}}

Then

− 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}}}}}

Each additional term of the series yields approximately 50 digits.

Iterative algorithms

Quadratic convergence (1984)

Start by setting

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}}}

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}&={\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}}}

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)

Start by setting

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}}}

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}&={\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}}}

Then ak converges cubically to ⁠1/π⁠; that is, each iteration approximately triples the number of correct digits.

Quartic convergence (1985)

Start by setting

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}}}

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}&={\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}}}

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:

Quintic convergence

Start by setting

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}}}

where ϕ = 1 + 5 2 {\displaystyle \phi ={\tfrac {1+{\sqrt {5}}}{2}}} 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}&={\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}}}

Then ak converges quintically to ⁠1/π⁠ (that is, each iteration approximately quintuples the number of correct digits), and the following condition holds:

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 \,\!}

Nonic convergence

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}&={\frac {1}{3}}\\r_{0}&={\frac {{\sqrt {3}}-1}{2}}\\s_{0}&=\left(1-r_{0}^{3}\right)^{\frac {1}{3}}\end{aligned}}}

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}&=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}}}

Then ak converges nonically to ⁠1/π⁠; that is, each iteration approximately multiplies the number of correct digits by nine.

See also

References

  1. 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
  2. Bailey, David H (2023-04-01). "Peter Borwein: A Visionary Mathematician". Notices of the American Mathematical Society. 70 (04): 610–613. doi:10.1090/noti2675. ISSN 0002-9920.
  3. 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.
  4. Arndt, Jörg; Haenel, Christoph (1998). π Unleashed. Springer-Verlag. p. 236. ISBN 3-540-66572-2.
  5. Mak, Ronald (2003). The Java Programmers Guide to Numerical Computation. Pearson Educational. p. 353. ISBN 0-13-046041-9.
  6. Milla, Lorenz (2019), Easy Proof of Three Recursive π-Algorithms, arXiv:1907.04110
  7. Henrik Vestermark (4 November 2016). "Practical implementation of π Algorithms" (PDF). Retrieved 29 November 2020.

External links

Category: