Borwein's Algorithm

In mathematics, Borwein's algorithm is an algorithm devised by Jonathan and Peter Borwein to calculate the value of . 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 A & = 212175710912 \sqrt + 1657145277365 \\ B & = 13773980892672 \sqrt + 107578229802750 \\ C & = \left(5280\left(236674+30303\sqrt\right)\right)^3 \end$

Then

:$\frac = 12\sum_^\infty \frac$

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

Class number 4 (1993)

Start by setting

: $\begin A = & 63365028312971999585426220 \\ & + 28337702140800842046825600\sqrt \\ & + 384\sqrt \big(10891728551171178200467436212395209160385656017 \\ & + \left. 4870929086578810225077338534541688721351255040\sqrt\right)^\frac12 \\ B = & 7849910453496627210289749000 \\ & + 3510586678260932028965606400\sqrt \\ & + 2515968\sqrt\big(6260208323789001636993322654444020882161 \\ & + \left. 2799650273060444296577206890718825190235\sqrt\right)^\frac12 \\ C = & -214772995063512240 \\ & - 96049403338648032\sqrt \\ & - 1296\sqrt\big(10985234579463550323713318473 \\ & + \left. 4912746253692362754607395912\sqrt\right)^\frac12 \end$

Then

: $\frac = \sum_^$

Each additional term of the series yields approximately 50 digits.

Iterative algorithms

Quadratic convergence (1984)

Start by setting

:$\begin a_0 & = \sqrt \\ b_0 & = 0 \\ p_0 & = 2 + \sqrt \end$

Then iterate

:$\begin a_ & = \frac \\ b_ & = \frac \\ p_ & = \frac \end$

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 a_0 & = \frac13 \\ s_0 & = \frac \end$

Then iterate

:$\begin r_ & = \frac \\ s_ & = \frac \\ a_ & = r_^2 a_k - 3^k\left(r_^2-1\right) \end$

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

Quartic convergence (1985)

Start by setting

:$\begin a_0 & = 2\left(\sqrt-1\right)^2 \\ y_0 & = \sqrt-1 \end$

Then iterate

: $\begin y_ & = \frac \\ a_ & = a_k\left(1+y_\right)^4 - 2^ y_ \left(1 + y_ + y_^2\right) \end$

Then ''a''_''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 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 a_0 & = \frac12 \\ s_0 & = 5\left(\sqrt - 2\right) = \frac \end$

where $\phi = \tfrac$ is the golden ratio. Then iterate

:$\begin x_ & = \frac - 1 \\ y_ & = \left(x_ - 1\right)^2 + 7 \\ z_ & = \left(\frac12 x_\left(y_ + \sqrt\right)\right)^\frac15 \\ a_ & = s_n^2 a_n - 5^n\left(\frac + \sqrt\right) \\ s_ & = \frac \end$

Then a_k converges quintically to (that is, each iteration approximately quintuples the number of correct digits), and the following condition holds:

:$0 < a_n - \frac < 16\cdot 5^n\cdot e^\pi\,\!$

Nonic convergence

Start by setting

:$\begin a_0 & = \frac13 \\ r_0 & = \frac \\ s_0 & = \left(1 - r_0^3\right)^\frac13 \end$

Then iterate

:$\begin t_ & = 1 + 2r_n \\ u_ & = \left(9r_n \left(1 + r_n + r_n^2\right)\right)^\frac13 \\ v_ & = t_^2 + t_u_ + u_^2 \\ w_ & = \frac \\ a_ & = w_a_n + 3^\left(1-w_\right) \\ s_ & = \frac \\ r_ & = \left(1 - s_^3\right)^\frac13 \end$

Then ''a''_''k'' converges nonically to ; that is, each iteration approximately multiplies the number of correct digits by nine.{{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

See also

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

References

External links

Pi Formulas
from Wolfram MathWorld

Pi algorithms