TOPICS
Search

Pi Iterations

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

pi may be computed using a number of iterative algorithms. The best known such algorithms are the Archimedes algorithm, which was derived by Pfaff in 1800, and the Brent-Salamin formula. Borwein et al. (1989) discuss pth-order iterative algorithms.

The Brent-Salamin formula is a quadratically converging algorithm.

Another quadratically converging algorithm (Borwein and Borwein 1987, pp. 46-48) is obtained by defining

x_0=sqrt(2)
(1)
y_1=2^(1/4)
(2)

and

x_n=1/2(x_(n-1)^(1/2)+x_(n-1)^(-1/2))
(3)
y_n=(y_(n-1)x_(n-1)^(1/2)+x_(n-1)^(-1/2))/(y_(n-1)+1).
(4)

Then

pi_n=pi_(n-1)(x_n+1)/(y_n+1),
(5)

with pi_0=2+sqrt(2). pi_n decreases monotonically to pi with

pi_n-pi<10^(-2^(n+1))
(6)

for n>=2.

A cubically converging algorithm which converges to the nearest multiple of pi to f_0 is the simple iteration

f_n=f_(n-1)+sin(f_(n-1))
(7)

(Beeler et al. 1972). For example, applying to 23 gives the sequence 23, 22.1537796, 21.99186453, 21.99114858, ..., which converges to 7pi approx 21.99114858.

A quartically converging algorithm is obtained by letting

y_0=sqrt(lambda^*(r))
(8)
alpha_0=alpha(r),
(9)

then defining

y_n=(1-(1-y_(n-1)^4)^(1/4))/(1+(1-y_(n-1)^4)^(1/4))
(10)
alpha_n=(1+y_n)^4alpha_(n-1)-4^nsqrt(r)y_n(1+y_n+y_n^2).
(11)

Then

pi=lim_(n->infty)1/(alpha_n)
(12)

and alpha_n converges to 1/pi quartically with

alpha_n-1/pi<16·4^nsqrt(r)e^(-4^npisqrt(r))
(13)

(Borwein and Borwein 1987, pp. 170-171; Bailey 1988, Borwein et al. 1989). This algorithm rests on a modular equation identity of order 4. Taking the special case r=2 gives y_0=sqrt(2)-1 and alpha_0=2(sqrt(2)-1)^2=6-4sqrt(2).

A quintically converging algorithm is obtained by letting

s_0=5(sqrt(5)-2)
(14)
alpha_0=1/2.
(15)

Then let

s_n=(25)/((z+x/z+1)^2s_(n-1)),
(16)

where

x=5/(s_n)-1
(17)
y=(x-1)^2+7
(18)
z=[1/2x(y+sqrt(y^2-4x^3))]^(1/5).
(19)

Finally, let

alpha_(n+1)=s_n^2alpha_n-5^n[1/2(s_n^2-5)+sqrt(s_n(s_n^2-2s_n+5))],
(20)

then

0<alpha_n-1/pi<16·5^ne^(-pi5^n)
(21)

(Borwein et al. 1989). This algorithm rests on a modular equation identity of order 5.

Beginning with any positive integer n, round up to the nearest multiple of n-1, then up to the nearest multiple of n-2, and so on, up to the nearest multiple of 1. Let f(n) denote the result. Then the ratio

lim_(n->infty)(n^2)/(f(n))=pi.
(22)

David (1957) credits this result to Jabotinski and Erdős and gives the more precise asymptotic result

f(n)=(n^2)/pi+O(n^(4/3)).
(23)

The first few numbers in the sequence {f(n)} are 1, 2, 4, 6, 10, 12, 18, 22, 30, 34, ... (OEIS A002491).

Another algorithm is due to Woon (1995). Define a(0)=1 and

a(n)=sqrt(1+[sum_(k=0)^(n-1)a(k)]^2).
(24)

It can be proved by induction that

a(n)=csc(pi/(2^(n+1))).
(25)

For n=0, the identity holds. If it holds for n<=t, then

a(t+1)=sqrt(1+[sum_(k=0)^tcsc(pi/(2^(k+1)))]^2),
(26)

but

csc(pi/(2^(k+1)))=cot(pi/(2^(k+2)))-cot(pi/(2^(k+1))),
(27)

so

sum_(k=0)^tcsc(pi/(2^(k+1)))=cot(pi/(2^(t+2))).
(28)

Therefore,

a(t+1)=csc(pi/(2^(t+2))),
(29)

so the identity holds for n=t+1 and, by induction, for all nonnegative n, and

lim_(n->infty)(2^(n+1))/(a(n))=lim_(n->infty)2^(n+1)sin(pi/(2^(n+1)))
(30)
=lim_(n->infty)2^(n+1)pi/(2^(n+1))(sin(pi/(2^(n+1))))/(pi/(2^(n+1)))
(31)
=pilim_(theta->0)(sintheta)/theta=pi.
(32)

See also

Archimedes Algorithm, Brent-Salamin Formula, Pi, Pi Digits, Pi Formulas

Explore with Wolfram|Alpha

References

Bailey, D. H. "The Computation of pi to 29360000 Decimal Digit using Borwein's' Quartically Convergent Algorithm." Math. Comput. 50, 283-296, 1988.Beeler, M. et al. Item 140 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 69, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/pi.html#item140.Borwein, J. M. and Borwein, P. B. Pi & the AGM: A Study in Analytic Number Theory and Computational Complexity. New York: Wiley, 1987.Borwein, J. M.; Borwein, P. B.; and Bailey, D. H. "Ramanujan, Modular Equations, and Approximations to Pi, or How to Compute One Billion Digits of Pi." Amer. Math. Monthly 96, 201-219, 1989.David, Y. "On a Sequence Generated by a Sieving Process." Riveon Lematematika 11, 26-31, 1957.Sloane, N. J. A. Sequence A002491/M1009 in "The On-Line Encyclopedia of Integer Sequences."Woon, S. C. "Problem 1441." Math. Mag. 68, 72-73, 1995.

Referenced on Wolfram|Alpha

Pi Iterations

Cite this as:

Weisstein, Eric W. "Pi Iterations." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PiIterations.html

Subject classifications