Borwein's algorithm

Quality 0.50 · 3 views · Updated 2 months ago

Method for calculating the value of pi

title: "Borwein's algorithm" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["pi-algorithms"] description: "Method for calculating the value of pi" topic_path: "technology/algorithms" source: "https://en.wikipedia.org/wiki/Borwein's_algorithm" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Method for calculating the value of pi ::

Borwein's algorithm was devised by Jonathan and Peter Borwein to calculate the value of 1 / \pi. This and other algorithms can be found in 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{align} A & = 212175710912 \sqrt{61} + 1657145277365 \ B & = 13773980892672 \sqrt{61} + 107578229802750 \ C & = \left(5280\left(236674+30303\sqrt{61}\right)\right)^3 \end{align}

Then

:\frac{1}{\pi} = 12\sum_{n=0}^\infty \frac{ (-1)^n (6n)!, (A+nB) }{(n!)^3(3n)!, C^{n+\frac12}}

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

Class number 4 (1993)

Start by setting

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

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.

Iterative algorithms

Quadratic convergence (1984)

Start by setting

: \begin{align} a_0 & = \sqrt{2} \ b_0 & = 0 \ p_0 & = 2 + \sqrt{2} \end{align}

Then iterate

: \begin{align} 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{align}

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{align} a_0 & = \frac13 \ s_0 & = \frac{\sqrt{3} - 1}{2} \end{align}

Then iterate

: \begin{align} r_{k+1} & = \frac{3}{1 + 2\left(1-s_k^3\right)^\frac13} \ s_{k+1} & = \frac{r_{k+1} - 1}{2} \ a_{k+1} & = r_{k+1}^2 a_k - 3^k\left(r_{k+1}^2-1\right) \end{align}

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

Quartic convergence (1985)

Start by setting

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

Then iterate

: \begin{align} y_{k+1} & = \frac{1-\left(1-y_k^4\right)^\frac14}{1+\left(1-y_k^4\right)^\frac14} \ a_{k+1} & = a_k\left(1+y_{k+1}\right)^4 - 2^{2k+3} y_{k+1} \left(1 + y_{k+1} + y_{k+1}^2\right) \end{align}

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{align} a_0 & = \frac12 \ s_0 & = 5\left(\sqrt{5} - 2\right) = \frac{5}{\phi^3} \end{align}

where \phi = \tfrac{1+\sqrt5}{2} is the golden ratio. Then iterate

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

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

Nonic convergence

Start by setting

: \begin{align} a_0 & = \frac13 \ r_0 & = \frac{\sqrt{3} - 1}{2} \ s_0 & = \left(1 - r_0^3\right)^\frac13 \end{align}

Then iterate

: \begin{align} t_{n+1} & = 1 + 2r_n \ u_{n+1} & = \left(9r_n \left(1 + r_n + r_n^2\right)\right)^\frac13 \ v_{n+1} & = t_{n+1}^2 + t_{n+1}u_{n+1} + u_{n+1}^2 \ w_{n+1} & = \frac{27 \left(1 + s_n + s_n^2\right)}{v_{n+1}} \ a_{n+1} & = w_{n+1}a_n + 3^{2n-1}\left(1-w_{n+1}\right) \ s_{n+1} & = \frac{\left(1 - r_n\right)^3}{\left(t_{n+1} + 2u_{n+1}\right)v_{n+1}} \ r_{n+1} & = \left(1 - s_{n+1}^3\right)^\frac13 \end{align}

Then a**k converges nonically to ; that is, each iteration approximately multiplies the number of correct digits by nine.

References

Jonathan M. Borwein, Peter B. Borwein, ''Pi and the AGM – A Study in Analytic Number Theory and Computational Complexity'', Wiley, New York, 1987. Many of their results are available in: Jorg Arndt, Christoph Haenel, Pi Unleashed, Springer, Berlin, 2001, {{ISBN. 3-540-66572-2
Bailey, David H. (2023-04-01). "Peter Borwein: A Visionary Mathematician". Notices of the American Mathematical Society.
(1993). "Class number three Ramanujan type series for 1/π". Journal of Computational and Applied Mathematics.
(1998). "{{pi}} Unleashed". Springer-Verlag.
Mak, Ronald. (2003). "The Java Programmers Guide to Numerical Computation". Pearson Educational.
(2019). "Easy Proof of Three Recursive {{pi}}-Algorithms".
Henrik Vestermark. (4 November 2016). "Practical implementation of π Algorithms".

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::