From jhedden@motown.ge.com Thu Nov 2 16:37:34 1995
The spigot algorithm for pi is:
1 2 3 k
pi = 2 + --- * (2 + --- * (2 + --- * (2 + ... (2 + ---- * (2 + ... ))...)))
3 5 7 2k+1
The last term can be approximated by:
k
(2 + ---- * (4))
2k+1
where k = n * log (10)
2
for a desired precision of n decimal digits.
-------------------
a remark by Jacques Gelinas:
the following
article that presents a PROOF of correctness for the spigot
algorithms for e and \pi.
/*
A spigot algorithm for the Digits of \pi, Stanley Rabinowitz
and Stan Wagon, Am.Math.Monthly, March 1995, 195-203
*/
Footnote, page 197:
"Any digit-producing algorithm fo a presumed-normal number x suffers
from the drawback that, although unlikely, can impinge on the result.
If x is between 1 and 10 and the algorithm says that the first 100
digits of x are, say, 4,6,5,0,7,...,3,9,9,9,9,9 then one cannot be sure
that the last 6 digits are correct. They will be the digits of a
certain approximation to x that is within 5x10^-100 of the true value.
One cannot simply go farther until a non-9 is reached, because memory
allocation must be made in advance..."