Borwein's algorithm

In mathematics, Borwein's algorithm is an algorithm devised by Jonathan and Peter Borwein to calculate the value of 1/π. The most prominent and oft-used one is explained under the first section.

Borwein's algorithm

Start out by setting

: $a\_0\; =\; 6\; -\; 4sqrt\{2\}$: $y\_0\; =\; sqrt\{2\}\; -\; 1$

Then iterate

: $y\_\{k+1\}\; =\; frac\{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^\{2k+3\}\; y\_\{k+1\}\; (1\; +\; y\_\{k+1\}\; +\; y\_\{k+1\}^2)$

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

Quadratic convergence (1987)

Start out by setting

: $x\_0\; =\; sqrt2$: $y\_0\; =\; sqrt\; [4]\; 2$: $p\_0\; =\; 2+sqrt2$

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$

Cubic 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.

Quartic 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 π.

Quintic 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\}\; ight)\; ight)^\{1/5\}$: $a\_\{n+1\}\; =\; s\_n^2\; a\_n\; -\; 5^nleft(frac\{s\_n^2\; -\; 5\}\{2\}\; +\; sqrt\{s\_n(s\_n^2\; -\; 2s\_n\; +\; 5)\}\; ight)$: $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:

:

Nonic 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.

Another formula for π (1989)

Start out by setting

: $A\; =\; 212175710912\; sqrt\{61\}\; +\; 1657145277365$: $B\; =\; 13773980892672\; sqrt\{61\}\; +\; 107578229802750$: $C\; =\; (5280(236674+30303sqrt\{61\}))^3$

Then

: $1\; /\; pi\; =\; 12sum\_\{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's Version (1993)

Start out by setting

:

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.

ee also

* Gauss–Legendre algorithm - another algorithm to calculate π
* Bailey-Borwein-Plouffe formula