Borwein's algorithm (others)

From Wikipedia, the free encyclopedia

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:

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$
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.
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 π.
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$
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.
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\sqrt5$
  
  $+ 384\sqrt5(10891728551171178200467436212395209160385656017$
  
  $+ 4870929086578810225077338534541688721351255040\sqrt5)^{1/2}$
  
  $\,B = 7849910453496627210289749000$
  
  $+ 3510586678260932028965606400\sqrt5$
  
  $+ 2515968\sqrt{3110}(6260208323789001636993322654444020882161$
  
  $+ 2799650273060444296577206890718825190235\sqrt5)^{1/2}$
  
  $\,C = -214772995063512240$
  
  $- 96049403338648032\sqrt5$
  
  $- 1296\sqrt5(10985234579463550323713318473$
  
  $+ 4912746253692362754607395912\sqrt5)^{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.