TOPICS
Search

Pi Iterations

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Pi iterations are iterative algorithms for computing pi. Examples include the Archimedes algorithm 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, for positive integers n,

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)

where the recurrence relation for y_n applies for n>=2. Then, for n>=1,

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

with pi_0=2+sqrt(2). The sequence {pi_n} decreases monotonically to pi with

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

for n>=2.

The simple iteration

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

converges cubically to (2k+1)pi when 2kpi<f_0<2(k+1)pi and k is an integer. An initial value f_0=2kpi remains fixed (Beeler et al. 1972, Item 142). For example, starting with f_0=23 gives the sequence 23, 22.1537796, 21.99186453, 21.99114858, ..., which converges to 7pi approx 21.99114858.

For a positive real number r, a quartically converging algorithm is obtained by letting

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

where lambda^*(r) is the elliptic lambda function and alpha(r) is the elliptic alpha function, then defining, for positive integers n,

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=4 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)

For nonnegative integers n, let

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

where x=5/s_n-1, y=(x-1)^2+7, and z=[1/2x(y+sqrt(y^2-4x^3))]^(1/5). 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))],
(17)

then

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

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

Beginning with a positive integer n>=2, 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 and define f(1)=1. Then the ratio

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

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)).
(20)

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, for positive integers n,

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

It can be proved by mathematical induction that

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

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),
(23)

but

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

so

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

Therefore,

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

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

lim_(n->infty)(2^(n+1))/(a(n))=lim_(n->infty)2^(n+1)sin(pi/(2^(n+1)))
(27)
=lim_(n->infty)2^(n+1)pi/(2^(n+1))(sin(pi/(2^(n+1))))/(pi/(2^(n+1)))
(28)
=pilim_(theta->0)(sintheta)/theta=pi.
(29)

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 Digits Using Borweins' Quartically Convergent Algorithm." Math. Comput. 50, 283-296, 1988.Beeler, M.; Gosper, R. W.; and Schroeppel, R. Item 142 in HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Feb. 1972. https://www.inwap.com/pdp10/hbaker/hakmem/pi.html#item142.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