Borwein's algorithm (others)

Jonathan and Peter Borwein devised various algorithms to calculate the value of π. The most prominent and oft-used one is explained under Borwein's algorithm and Bailey-Borwein-Plouffe formula. Other algorithms found by them include the following:

1. Quadratic convergence, 1987:
   • Start out by setting

     $x_{0}={\sqrt {2}}$

     $y_{0}={\sqrt[{4}]{2}}$

     $p_{0}=2+{\sqrt {2}}$

   • Then iterate

     $x_{k}={\frac {1}{2}}(x_{k-1}^{1/2}+x_{k-1}^{-1/2})$

     $y_{k}={\frac {y_{k-1}x_{k-1}^{1/2}+x_{k-1}^{-1/2}}{y_{k-1}+1}}$

     $p_{k}=p_{k-1}{\frac {x_{k}+1}{y_{k}+1}}$

   Then p_k converges monotonically to π; with

   $p_{k}-\pi =10^{-2^{k+1}}$

   for $k>=2$

2. Cubical convergence, 1991:
   • Start out by setting

     $a_{0}={\frac {1}{3}}$

     $s_{0}={\frac {{\sqrt {3}}-1}{2}}$

   • Then iterate

     $r_{k+1}={\frac {3}{1+2(1-s_{k}^{3})^{1/3}}}$

     $s_{k+1}={\frac {r_{k+1}-1}{2}}$

     $a_{k+1}=r_{k+1}^{2}a_{k}-3^{k}(r_{k+1}^{2}-1)$

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

3. Quartical convergence, 1984:
   • Start out by setting

     $a_{0}={\sqrt {2}}$

     $b_{0}=0\,\!$

     $p_{0}=2+{\sqrt {2}}$

   • Then iterate

     $a_{n+1}={\frac {{\sqrt {a_{n}}}+1/{\sqrt {a_{n}}}}{2}}$

     $b_{n+1}={\frac {{\sqrt {a_{n}}}(1+b_{n})}{a_{n}+b_{n}}}$

     $p_{n+1}={\frac {p_{n}b_{n+1}(1+a_{n+1})}{1+b_{n+1}}}$

   Then p_k converges quartically against π; 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 of π.

4. Quintical convergence:
   • Start out by setting

     $a_{0}={\frac {1}{2}}$

     $s_{0}=5({\sqrt {5}}-2)$

   • Then iterate

     $x_{n+1}={\frac {5}{s_{n}}}-1$

     $y_{n+1}=(x_{n+1}-1)^{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)^{1/5}$

     $a_{n+1}=s_{n}^{2}a_{n}-5^{n}\left({\frac {s_{n}^{2}-5}{2}}+{\sqrt {s_{n}(s_{n}^{2}-2s_{n}+5)}}\right)$

     $s_{n+1}={\frac {25}{(z_{n+1}+x_{n+1}/z_{n+1}+1)^{2}s_{n}}}$

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

   $0<a_{n}-{\frac {1}{\pi }}<16\cdot 5^{n}\cdot e^{-5^{n}}\pi$

5. Nonical convergence:
   • Start out by setting

     $a_{0}={\frac {1}{3}}$

     $r_{0}={\frac {{\sqrt {3}}-1}{2}}$

     $s_{0}=(1-r_{0}^{3})^{1/3}$

   • Then iterate

     $t_{n+1}=1+2r_{n}\,\!$

     $u_{n+1}=(9r_{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}={\frac {27(1+s_{n}+s_{n}^{2})}{v_{n+1}}}$

     $a_{n+1}=w_{n+1}a_{n}+3^{2n-1}(1-w_{n+1})\,\!$

     $s_{n+1}={\frac {(1-r_{n})^{3}}{(t_{n+1}+2u_{n+1})v_{n+1}}}$

     $r_{n+1}=(1-s_{n+1}^{3})^{1/3}$

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

6. Another formula for π, 1989:
   • Start out by setting

     $A=212175710912{\sqrt {61}}+1657145277365$

     $B=13773980892672{\sqrt {61}}+107578229802750$

     $C=(5280(236674+30303{\sqrt {61}}))^{3}$

   • Then

     $1/\pi =12\sum _{n=0}^{\infty }{\frac {(-1)^{n}(6n)!(A+nB)}{(n!)^{3}(3n)!C^{n+1/2}}}$

   Each additional term of the series yields approximately 31 digits.

   • Jonathan Borwein and Peter Borwein, 1993:
     • Start out by setting

       $\,A=63365028312971999585426220$

       $+28337702140800842046825600{\sqrt {5}}$

       $+384{\sqrt {5}}(10891728551171178200467436212395209160385656017$

       $+4870929086578810225077338534541688721351255040{\sqrt {5}})^{1/2}$

       $\,B=7849910453496627210289749000$

       $+3510586678260932028965606400{\sqrt {5}}$

       $+2515968{\sqrt {3110}}(6260208323789001636993322654444020882161$

       $+2799650273060444296577206890718825190235{\sqrt {5}})^{1/2}$

       $\,C=-214772995063512240$

       $-96049403338648032{\sqrt {5}}$

       $-1296{\sqrt {5}}(10985234579463550323713318473$

       $+4912746253692362754607395912{\sqrt {5}})^{1/2}$

     • Then

       ${\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.