# Borwein's algorithm

﻿
Borwein's algorithm

In mathematics, Borwein's algorithm is an algorithm devised by Jonathan and Peter Borwein to calculate the value of 1/&pi;. The most prominent and oft-used one is explained under the first section.

Borwein's algorithm

Start out by setting

: $a_0 = 6 - 4sqrt\left\{2\right\}$: $y_0 = sqrt\left\{2\right\} - 1$

Then iterate

: $y_\left\{k+1\right\} = frac\left\{1-\left(1-y_k^4\right)^\left\{1/4\left\{1+\left(1-y_k^4\right)^\left\{1/4$: $a_\left\{k+1\right\} = a_k\left(1+y_\left\{k+1\right\}\right)^4 - 2^\left\{2k+3\right\} y_\left\{k+1\right\} \left(1 + y_\left\{k+1\right\} + y_\left\{k+1\right\}^2\right)$

Then ak converges quartically against 1/&pi;; that is, each iteration approximately quadruples the number of correct digits.

Start out by setting

: $x_0 = sqrt2$: $y_0 = sqrt \left[4\right] 2$: $p_0 = 2+sqrt2$

Then iterate

: $x_k = frac\left\{1\right\}\left\{2\right\}\left(x_\left\{k-1\right\}^\left\{1/2\right\} + x_\left\{k-1\right\}^\left\{-1/2\right\}\right)$: $y_k = frac\left\{y_\left\{k-1\right\}x_\left\{k-1\right\}^\left\{1/2\right\} + x_\left\{k-1\right\}^\left\{-1/2 \left\{y_\left\{k-1\right\}+1\right\}$: $p_k = p_\left\{k-1\right\}frac\left\{x_k+1\right\}\left\{y_k+1\right\}$

Then pk converges monotonically to &pi;; with

: $p_k - pi = 10^\left\{-2^\left\{k+1$

for $k >= 2$

Cubic convergence (1991)

Start out by setting

: $a_0 = frac\left\{1\right\}\left\{3\right\}$: $s_0 = frac\left\{sqrt\left\{3\right\} - 1\right\}\left\{2\right\}$

Then iterate

: $r_\left\{k+1\right\} = frac\left\{3\right\}\left\{1 + 2\left(1-s_k^3\right)^\left\{1/3$: $s_\left\{k+1\right\} = frac\left\{r_\left\{k+1\right\} - 1\right\}\left\{2\right\}$: $a_\left\{k+1\right\} = r_\left\{k+1\right\}^2 a_k - 3^k\left(r_\left\{k+1\right\}^2-1\right)$

Then ak converges cubically against 1/&pi;; that is, each iteration approximately triples the number of correct digits.

Quartic convergence (1984)

Start out by setting

: $a_0 = sqrt\left\{2\right\}$: $b_0 = 0,!$: $p_0 = 2 + sqrt\left\{2\right\}$

Then iterate

: $a_\left\{n+1\right\} = frac\left\{sqrt\left\{a_n\right\} + 1/sqrt\left\{a_n\left\{2\right\}$: $b_\left\{n+1\right\} = frac\left\{sqrt\left\{a_n\right\} \left(1 + b_n\right)\right\}\left\{a_n + b_n\right\}$: $p_\left\{n+1\right\} = frac\left\{p_n b_\left\{n+1\right\} \left(1 + a_\left\{n+1\right\}\right)\right\}\left\{1 + b_\left\{n+1$

Then pk converges quartically against &pi;; 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 &pi;.

Quintic convergence

Start out by setting

: $a_0 = frac\left\{1\right\}\left\{2\right\}$: $s_0 = 5\left(sqrt\left\{5\right\} - 2\right)$

Then iterate

: $x_\left\{n+1\right\} = frac\left\{5\right\}\left\{s_n\right\} - 1$: $y_\left\{n+1\right\} = \left(x_\left\{n+1\right\} - 1\right)^2 + 7,!$: $z_\left\{n+1\right\} = left\left(frac\left\{1\right\}\left\{2\right\} x_\left\{n+1\right\}left\left(y_\left\{n+1\right\} + sqrt\left\{y_\left\{n+1\right\}^2 - 4x_\left\{n+1\right\}^3\right\} ight\right) ight\right)^\left\{1/5\right\}$: $a_\left\{n+1\right\} = s_n^2 a_n - 5^nleft\left(frac\left\{s_n^2 - 5\right\}\left\{2\right\} + sqrt\left\{s_n\left(s_n^2 - 2s_n + 5\right)\right\} ight\right)$: $s_\left\{n+1\right\} = frac\left\{25\right\}\left\{\left(z_\left\{n+1\right\} + x_\left\{n+1\right\}/z_\left\{n+1\right\} + 1\right)^2 s_n\right\}$

Then ak converges quintically against 1/&pi; (that is, each iteration approximately quintuples the number of correct digits), and the following condition holds:

: $0 < a_n - frac\left\{1\right\}\left\{pi\right\} < 16cdot 5^ncdot e^\left\{-5^n\right\}pi$

Nonic convergence

Start out by setting

: $a_0 = frac\left\{1\right\}\left\{3\right\}$: $r_0 = frac\left\{sqrt\left\{3\right\} - 1\right\}\left\{2\right\}$: $s_0 = \left(1 - r_0^3\right)^\left\{1/3\right\}$

Then iterate

: $t_\left\{n+1\right\} = 1 + 2r_n,!$: $u_\left\{n+1\right\} = \left(9r_n \left(1 + r_n + r_n^2\right)\right)^\left\{1/3\right\}$: $v_\left\{n+1\right\} = t_\left\{n+1\right\}^2 + t_\left\{n+1\right\}u_\left\{n+1\right\} + u_\left\{n+1\right\}^2$: $w_\left\{n+1\right\} = frac\left\{27 \left(1 + s_n + s_n^2\right)\right\}\left\{v_\left\{n+1$: $a_\left\{n+1\right\} = w_\left\{n+1\right\}a_n + 3^\left\{2n-1\right\}\left(1-w_\left\{n+1\right\}\right),!$: $s_\left\{n+1\right\} = frac\left\{\left(1 - r_n\right)^3\right\}\left\{\left(t_\left\{n+1\right\} + 2u_\left\{n+1\right\}\right)v_\left\{n+1$: $r_\left\{n+1\right\} = \left(1 - s_\left\{n+1\right\}^3\right)^\left\{1/3\right\}$

Then ak converges nonically against 1/&pi;; that is, each iteration approximately multiplies the number of correct digits by nine.

Another formula for &pi; (1989)

Start out by setting

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

Then

: $1 / pi = 12sum_\left\{n=0\right\}^infty frac\left\{ \left(-1\right)^n \left(6n\right)! \left(A+nB\right) \right\}\left\{\left(n!\right)^3\left(3n\right)! C^\left\{n+1/2$

Each additional term of the series yields approximately 31 digits.

Jonathan Borwein and Peter Borwein's Version (1993)

Start out by setting

:

Then

: $frac\left\{sqrt\left\{-C^3\left\{pi\right\} = sum_\left\{n=0\right\}^\left\{infty\right\} \left\{frac\left\{\left(6n\right)!\right\}\left\{\left(3n\right)!\left(n!\right)^3\right\} frac\left\{A+nB\right\}\left\{C^\left\{3n\right\}$

Each additional term of the series yields approximately 50 digits.

ee also

* Gauss–Legendre algorithm - another algorithm to calculate &pi;
* Bailey-Borwein-Plouffe formula

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Gauss–Legendre algorithm — The Gauss–Legendre algorithm is an algorithm to compute the digits of pi;. It is notable for being rapidly convergent, with only 25 iterations producing 45 million correct digits of pi;. However, the drawback is that it is memory intensive and it …   Wikipedia

• Jonathan Borwein — Jonathan Michael Borwein (born 1951) is a Canadian mathematician noted for his prolific and creative work throughout the international mathematical community. He is a close associate of David H. Bailey, and they have recently been among the most… …   Wikipedia

• Bailey–Borwein–Plouffe formula — The Bailey–Borwein–Plouffe formula (BBP formula) provides a spigot algorithm for the computation of the n th binary digit of π. This summation formula was discovered in 1995 by Simon Plouffe. The formula is named after the authors of the paper in …   Wikipedia

• Integer relation algorithm — An integer relation between a set of real numbers x 1, x 2, ..., x n is a set of integers a 1, a 2, ..., a n, not all 0, such that:a 1x 1 + a 2x 2 + cdots + a nx n = 0.,An integer relation algorithm is an algorithm for finding integer relations.… …   Wikipedia

• Peter Borwein — Peter Benjamin Borwein (St. Andrews, Scotland, 1953) is a Canadian mathematician, co developer of an algorithm for calculating π to the n th digit, PiHex, co discoverer of the trillionth, four trillionth, 40th trillionth, and quadrillionth digits …   Wikipedia

• Lenstra–Lenstra–Lovász lattice basis reduction algorithm — The Lenstra–Lenstra–Lovász lattice basis reduction (LLL) is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász. Given as input d lattice basis vectors with n dimensional integer coordinates… …   Wikipedia

• Spigot algorithm — A spigot algorithm is an algorithm used to compute the value of a mathematical constant such as pi; or e. Unlike recursive algorithms, a spigot algorithm yields digits incrementally without using previously computed digits. The Bailey Borwein… …   Wikipedia

• Approximations of π — Timeline of approximations for pi …   Wikipedia

• List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

• Computing π — Similarly, the more complex approximations of π given below involve repeated calculations of some sort, yielding closer and closer approximations with increasing numbers of calculations.Continued fractionsBesides its simple continued fraction… …   Wikipedia