The spigot Pi algorithm

Euler's series can be rearranged to

Pi = (2+(1/3)*(2+(2/5)*(2+(3/7)*(2+(4/9)*(2+(5/11) ... ))))

This is the starting point of a clever base conversion algorithm, which draw much attention in the last ten years. It is called the spigot algorithm for Pi. I will not explain its working here, because of the many fine exposition already exist and refer the reader to [2] and [4], where he can also find pointers to further expositions and sources.

The following implementation is an adaption of the spigot program of Joerg Arndt and Christoph Haenel, written in 'C'. It can be found in the book ' Pi - Algorithmen, Computer, Arithmetik ' (see ref. [4]), p. 84. A similar procedure can be found in Delahaye's book on page 119.

Unfortunately the designers of Maple choose to emulate the 'C' I/O library. (The C-I/O model is inefficient and it's interface is cryptic - to say the least.) The correctness of the following procedure relies on the string "%04d". So I better explain to those not familiar with 'C'. "%04d" is a format specifier for an integer, indicating to pad the conversion of an integer with leading zeros (instead of spaces) and to use a minimum of 4 characters to generate the conversion. On the other hand the algorithm is design to output a maximum of 4 decimal digits with each iteration. So the procedure should output exactly 4 decimal digits in each iteration.

In more mathematical terms: The computation does not convert in base 10 but in base 10000, which results in a nice speed-up.

>

piSpigot(100); evalf(Pi,100);

3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067

Note: A 'Java'-implementation of the above algorithm can be found at PiSpigot.