Borwein's algorithm

From Wikipedia, the free encyclopedia

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.

1 Borwein's algorithm
2 Quadratic convergence (1987)
3 Cubic convergence (1991)
4 Quartic convergence (1984)
5 Quintic convergence
6 Nonic convergence
7 Another formula for π (1989)
8 Jonathan Borwein and Peter Borwein's Version (1993)
9 See also

[edit] Borwein's algorithm

Start out by setting

$a_0 = 6 - 4\sqrt{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.

[edit] 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$

[edit] 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.

[edit] 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 π.

[edit] 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}\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$