Editing Borwein's algorithm (section)

==Iterative algorithms==

===Quadratic convergence (1984)===

Start by setting<ref>{{cite book| title={{pi}} Unleashed |first1=Jörg |last1=Arndt |first2=Christoph |last2=Haenel |publisher=Springer-Verlag |isbn=3-540-66572-2 |year=1998 |page=236}}</ref>

:<math> \begin{align} a_0 & = \sqrt{2} \\
                      b_0 & = 0 \\
                      p_0 & = 2 + \sqrt{2}
         \end{align}
</math>

Then iterate

:<math> \begin{align} 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{align}
</math>

Then ''p''<sub>''k''</sub> converges quadratically to {{pi}}; 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 {{pi}}'s final result.

===Cubic convergence (1991)===

Start by setting

:<math> \begin{align} a_0 & = \frac13 \\
                      s_0 & = \frac{\sqrt{3} - 1}{2}
        \end{align}
</math>

Then iterate

:<math> \begin{align} r_{k+1} & = \frac{3}{1 + 2\left(1-s_k^3\right)^\frac13} \\
                      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{align}
</math>

Then ''a<sub>k</sub>'' converges cubically to {{sfrac|1|{{pi}}}}; that is, each iteration approximately triples the number of correct digits.

===Quartic convergence (1985)===

Start by setting<ref>{{cite book | title=The Java Programmers Guide to Numerical Computation |last=Mak |first=Ronald |publisher=Pearson Educational |year=2003 |isbn=0-13-046041-9 |page=353}}</ref>

:<math> \begin{align} a_0 & = 2\left(\sqrt{2}-1\right)^2 \\
                      y_0 & = \sqrt{2}-1
        \end{align}
</math>

Then iterate

: <math> \begin{align} y_{k+1} & = \frac{1-\left(1-y_k^4\right)^\frac14}{1+\left(1-y_k^4\right)^\frac14} \\
                       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{align}
</math>

Then ''a''<sub>''k''</sub> converges quartically against {{sfrac|1|{{pi}}}}; 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 {{pi}}'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:<ref>{{citation|title=Easy Proof of Three Recursive {{pi}}-Algorithms|last1=Milla|first1=Lorenz|arxiv=1907.04110|year=2019}}</ref>

===Quintic convergence===

Start by setting

:<math> \begin{align} a_0 & = \frac12 \\
                      s_0 & = 5\left(\sqrt{5} - 2\right) = \frac{5}{\phi^3}
         \end{align}
</math>

where <math>\phi = \tfrac{1+\sqrt5}{2}</math> is the [[golden ratio]]. Then iterate

:<math> \begin{align} x_{n+1} & = \frac{5}{s_n} - 1 \\
                      y_{n+1} & = \left(x_{n+1} - 1\right)^2 + 7 \\
                      z_{n+1} & = \left(\frac12 x_{n+1}\left(y_{n+1} + \sqrt{y_{n+1}^2 - 4x_{n+1}^3}\right)\right)^\frac15 \\
                      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{align}
</math>

Then a<sub>k</sub> converges quintically to {{sfrac|1|{{pi}}}} (that is, each iteration approximately quintuples the number of correct digits), and the following condition holds:

:<math>0 < a_n - \frac{1}{\pi} < 16\cdot 5^n\cdot e^{-5^n}\pi\,\!</math>

===Nonic convergence===

Start by setting

:<math> \begin{align} a_0 & = \frac13 \\
                      r_0 & = \frac{\sqrt{3} - 1}{2} \\
                      s_0 & = \left(1 - r_0^3\right)^\frac13
        \end{align}
</math>

Then iterate

:<math> \begin{align} t_{n+1} & = 1 + 2r_n \\
                      u_{n+1} & = \left(9r_n \left(1 + r_n + r_n^2\right)\right)^\frac13 \\
                      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)^\frac13
        \end{align}
</math>

Then ''a''<sub>''k''</sub> converges nonically to {{sfrac|1|{{pi}}}}; that is, each iteration approximately multiplies the number of correct digits by nine.<ref>{{cite web|url=http://www.hvks.com/Numerical/Downloads/HVE%20Practical%20implementation%20of%20PI%20Algorithms.pdf|title=Practical implementation of π Algorithms|author=Henrik Vestermark|date=4 November 2016|access-date=29 November 2020}}</ref>