Girish Mahajan (Editor)

Borwein's algorithm

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

Jonathan Borwein and Peter Borwein's version (1993)

Start by setting

A = 63365028312971999585426220 + 28337702140800842046825600 5 + 384 5 ( 10891728551171178200467436212395209160385656017 + 4870929086578810225077338534541688721351255040 5 ) 1 / 2 B = 7849910453496627210289749000 + 3510586678260932028965606400 5 + 2515968 3110 ( 6260208323789001636993322654444020882161 + 2799650273060444296577206890718825190235 5 ) 1 / 2 C = − 214772995063512240 − 96049403338648032 5 − 1296 5 ( 10985234579463550323713318473 + 4912746253692362754607395912 5 ) 1 / 2

Then

− C 3 π = ∑ n = 0 ∞ ( 6 n ) ! ( 3 n ) ! ( n ! ) 3 A + n B C 3 n

Each additional term of the series yields approximately 50 digits. This is an example of a Ramanujan–Sato series.

Cubic convergence (1991)

Start by setting

a 0 = 1 3 s 0 = 3 − 1 2

Then iterate

r k + 1 = 3 1 + 2 ( 1 − s k 3 ) 1 / 3 s k + 1 = 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 to 1/π; that is, each iteration approximately triples the number of correct digits.

Another formula for π (1989)

Start by setting

A = 212175710912 61 + 1657145277365 B = 13773980892672 61 + 107578229802750 C = ( 5280 ( 236674 + 30303 61 ) ) 3

Then

1 / π = 12 ∑ n = 0 ∞ ( − 1 ) n ( 6 n ) ! ( A + n B ) ( n ! ) 3 ( 3 n ) ! C n + 1 / 2

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

Quartic algorithm (1985)

Start by setting

a 0 = 2 ( 2 − 1 ) 2 y 0 = 2 − 1

Then iterate

y k + 1 = 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 2 k + 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. The algorithm is not self-correcting; each iteration must be performed with the desired number of correct digits for π's final result.

Quadratic convergence (1984)

Start by setting

a 0 = 2 b 0 = 0 p 0 = 2 + 2

Then iterate

a n + 1 = a n + 1 / a n 2 b n + 1 = ( 1 + b n ) a n a n + b n p n + 1 = ( 1 + a n + 1 ) p n b n + 1 1 + b n + 1

Then pk converges quadraticly 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.

Quintic convergence

Start by setting

a 0 = 1 2 s 0 = 5 ( 5 − 2 )

Then iterate

x n + 1 = 5 s n − 1 y n + 1 = ( x n + 1 − 1 ) 2 + 7 z n + 1 = ( 1 2 x n + 1 ( y n + 1 + y n + 1 2 − 4 x n + 1 3 ) ) 1 / 5 a n + 1 = s n 2 a n − 5 n ( s n 2 − 5 2 + s n ( s n 2 − 2 s n + 5 ) ) s n + 1 = 25 ( z n + 1 + x n + 1 / z n + 1 + 1 ) 2 s n

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

0 < a n − 1 π < 16 ⋅ 5 n ⋅ e − 5 n π

Nonic convergence

Start by setting

a 0 = 1 3 r 0 = 3 − 1 2 s 0 = ( 1 − r 0 3 ) 1 / 3

Then iterate

t n + 1 = 1 + 2 r n u n + 1 = ( 9 r 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 = 27 ( 1 + s n + s n 2 ) v n + 1 a n + 1 = w n + 1 a n + 3 2 n − 1 ( 1 − w n + 1 ) s n + 1 = ( 1 − r n ) 3 ( t n + 1 + 2 u n + 1 ) v n + 1 r n + 1 = ( 1 − s n + 1 3 ) 1 / 3

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

References

Borwein's algorithm Wikipedia
(Text) CC BY-SA