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/π. The most prominent and oft-used one is explained under the first section.

Borwein's algorithm

Start out by setting

: a_0 = 6 - 4sqrt{2}: y_0 = sqrt{2} - 1

Then iterate

: y_{k+1} = frac{1-(1-y_k^4)^{1/4{1+(1-y_k^4)^{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)

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

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 pk converges monotonically to π; with

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

for k >= 2

Cubic 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 ak converges cubically against 1/π; that is, each iteration approximately triples the number of correct digits.

Quartic 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 pk 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 π.

Quintic 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} ight) ight)^{1/5}: a_{n+1} = s_n^2 a_n - 5^nleft(frac{s_n^2 - 5}{2} + sqrt{s_n(s_n^2 - 2s_n + 5)} ight): s_{n+1} = frac{25}{(z_{n+1} + x_{n+1}/z_{n+1} + 1)^2 s_n}

Then ak 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} < 16cdot 5^ncdot e^{-5^n}pi

Nonic 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 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{61} + 1657145277365: B = 13773980892672 sqrt{61} + 107578229802750: C = (5280(236674+30303sqrt{61}))^3

Then

: 1 / pi = 12sum_{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's Version (1993)

Start out by setting

: egin{align} A &= 63365028312971999585426220 \ &quad + 28337702140800842046825600sqrt{5} \ &quad + 384sqrt{5} (10891728551171178200467436212395209160385656017 \ &qquad + 4870929086578810225077338534541688721351255040sqrt{5})^{1/2} \ B &= 7849910453496627210289749000 \ &quad + 3510586678260932028965606400sqrt{5} \ &quad + 2515968sqrt{3110}(6260208323789001636993322654444020882161 \ &qquad + 2799650273060444296577206890718825190235sqrt{5})^{1/2} \ C &= -214772995063512240 \ &quad - 96049403338648032sqrt{5} \ &quad - 1296sqrt{5}(10985234579463550323713318473 \ &qquad + 4912746253692362754607395912sqrt{5})^{1/2}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.

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