Borwein's algorithm

Short description: Method for calculating pi

In mathematics, Borwein's algorithm is an algorithm devised by Jonathan and Peter Borwein to calculate the value of 1/π. They devised several other algorithms. They published the book Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity.

Ramanujan–Sato series

These two are examples of a Ramanujan–Sato series. The related Chudnovsky algorithm uses a discriminant with class number 1.

Class number 2 (1989)

Start by setting

$\begin{array}{rl}A& =212175710912\sqrt{61}+1657145277365\\ B& =13773980892672\sqrt{61}+107578229802750\\ C& ={\left(5280(236674+30303\sqrt{61})\right)}^3\end{array}$

Then

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

Each additional term of the partial sum yields approximately 25 digits.

Class number 4 (1993)

Start by setting

$\begin{array}{rl}A=& 63365028312971999585426220\\ & +28337702140800842046825600\sqrt{5}\\ & +384\sqrt{5}(10891728551171178200467436212395209160385656017\\ & +{4870929086578810225077338534541688721351255040\sqrt{5})}^{\frac{1}{2}}\\ B=& 7849910453496627210289749000\\ & +3510586678260932028965606400\sqrt{5}\\ & +2515968\sqrt{3110}(6260208323789001636993322654444020882161\\ & +{2799650273060444296577206890718825190235\sqrt{5})}^{\frac{1}{2}}\\ C=& -214772995063512240\\ & -96049403338648032\sqrt{5}\\ & -1296\sqrt{5}(10985234579463550323713318473\\ & +{4912746253692362754607395912\sqrt{5})}^{\frac{1}{2}}\end{array}$

Then

$\frac{\sqrt{-C^3}}{\pi }=\sum _{n=0}^{\mathrm{\infty }}\frac{(6n)!}{(3n)!(n!{)}^3}\frac{A+nB}{C^{3n}}$

Each additional term of the series yields approximately 50 digits.

Iterative algorithms

Quadratic convergence (1984)

Start by setting

$\begin{array}{rl}{a}_0& =\sqrt{2}\\ b_0& =0\\ p_0& =2+\sqrt{2}\end{array}$

Then iterate

$\begin{array}{rl}{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{array}$

Then p_k converges quadratically to π; 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 π's final result.

Cubic convergence (1991)

Start by setting

$\begin{array}{rl}{a}_0& =\frac{1}{3}\\ s_0& =\frac{\sqrt{3}-1}{2}\end{array}$

Then iterate

$\begin{array}{rl}{r}_{k+1}& =\frac{3}{1+2{(1-s_k^3)}^{\frac{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)\end{array}$

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

Quartic convergence (1985)

Start by setting

$\begin{array}{rl}{a}_0& =2{(\sqrt{2}-1)}^2\\ y_0& =\sqrt{2}-1\end{array}$

Then iterate

$\begin{array}{rl}{y}_{k+1}& =\frac{1-{(1-y_k^4)}^{\frac{1}{4}}}{1+{(1-y_k^4)}^{\frac{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)\end{array}$

Then a_k converges quartically against 1/π; 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 π'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:

Quintic convergence

Start by setting

$\begin{array}{rl}{a}_0& =\frac{1}{2}\\ s_0& =5(\sqrt{5}-2)=\frac{5}{{\varphi }^3}\end{array}$

where $\varphi =\frac{1+\sqrt{5}}{2}$ is the golden ratio. Then iterate

$\begin{array}{rl}{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}(y_{n+1}+\sqrt{y_{n+1}^2-4x_{n+1}^3})\right)}^{\frac{1}{5}}\\ a_{n+1}& =s_n^2{a}_n-5^n(\frac{s_n^2-5}{2}+\sqrt{s_n(s_n^2-2s_n+5)})\\ s_{n+1}& =\frac{25}{{(z_{n+1}+\frac{x_{n+1}}{z_{n+1}}+1)}^2{s}_n}\end{array}$

Then a_k converges quintically to 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$

Nonic convergence

Start by setting

$\begin{array}{rl}{a}_0& =\frac{1}{3}\\ r_0& =\frac{\sqrt{3}-1}{2}\\ s_0& ={(1-r_0^3)}^{\frac{1}{3}}\end{array}$

Then iterate

$\begin{array}{rl}{t}_{n+1}& =1+2r_n\\ u_{n+1}& ={\left(9r_n(1+r_n+r_n^2)\right)}^{\frac{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)}^{\frac{1}{3}}\end{array}$

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

See also

• Bailey–Borwein–Plouffe formula
• Chudnovsky algorithm
• Gauss–Legendre algorithm
• Ramanujan–Sato series

External links

• Pi Formulas from Wolfram MathWorld