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 th-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
and
Then
|
(5) |
with . decreases monotonically to with
|
(6) |
for .
A cubically converging algorithm which converges to the nearest multiple of to is the simple iteration
|
(7) |
(Beeler et al. 1972). For example, applying to 23 gives the sequence 23, 22.1537796, 21.99186453, 21.99114858, ..., which converges to .
A quartically converging algorithm is obtained by letting
then defining
Then
|
(12) |
and converges to quartically with
|
(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 gives and .
A quintically converging algorithm is obtained by letting
Then let
|
(16) |
where
|
(17) | |||
|
(18) | |||
|
(19) |
Finally, let
|
(20) |
then
|
(21) |
(Borwein et al. 1989). This algorithm rests on a modular equation identity of order 5.
Beginning with any positive integer , round up to the nearest multiple of , then up to the nearest multiple of , and so on, up to the nearest multiple of 1. Let denote the result. Then the ratio
|
(22) |
David (1957) credits this result to Jabotinski and Erdős and gives the more precise asymptotic result
|
(23) |
The first few numbers in the sequence are 1, 2, 4, 6, 10, 12, 18, 22, 30, 34, ... (OEIS A002491).
Another algorithm is due to Woon (1995). Define and
|
(24) |
It can be proved by induction that
|
(25) |
For , the identity holds. If it holds for , then
|
(26) |
but
|
(27) |
so
|
(28) |
Therefore,
|
(29) |
so the identity holds for and, by induction, for all nonnegative , and
|
(30) | |||
|
(31) | |||
|
(32) |
See also
Archimedes Algorithm, Brent-Salamin Formula, Pi, Pi Digits, Pi Formulas
Explore with Wolfram|Alpha
References
Bailey, D. H. "The Computation of to 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
Cite this as:
Weisstein, Eric W. "Pi Iterations." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PiIterations.html