Pi Iterations

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

			(1)
			(2)

and

			(3)
			(4)

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

			(8)
			(9)

then defining

			(10)
			(11)

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

			(14)
			(15)

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)

Wolfram Web Resources