Spigot algorithm
A spigot algorithm is an algorithm for computing the value of a mathematical constant such as π or e which generates output digits left to right, with limited intermediate storage.
The name comes from a "spigot", meaning a tap or valve controlling the flow of a liquid.
Interest in such algorithms was spurred in the early days of computational mathematics by extreme constraints on memory, and an algorithm for calculating the digits of e appears in a paper by Sale in 1968. The name "Spigot algorithm" appears to have been coined by Stanley Rabinowitz and Stan Wagon, whose algorithm for calculating the digits of π is sometimes referred to as "the spigot algorithm for π".
The spigot algorithm of Rabinowitz and Wagon is bounded, in the sense that the number of required digits must be specified in advance. Jeremy Gibbons (2004) uses the term "streaming algorithm" to mean one which can be run indefinitely, without a prior bound. A further refinement is an algorithm which can compute a single arbitrary digit, without first computing the preceding digits: an example is the Bailey-Borwein-Plouffe formula, a digit extraction algorithm for π which produces hexadecimal digits.
This example illustrates the working of a spigot algorithm by calculating the binary digits of the natural logarithm of 2 (sequence in the OEIS) using the identity
To start calculating binary digits from, say, the 8th place we multiply this identity by 27(since 7 = 8 - 1):
We then divide the infinite sum into a "head", in which the exponents of 2 are greater than or equal to zero, and a "tail", in which the exponents of 2 are negative:
We are only interested in the fractional part of this value, so we can replace each of the summands in the "head" by
Calculating each of these terms and adding them to a running total where we again only keep the fractional part, we have:
We add a few terms in the "tail", noting that the error introduced by truncating the sum is less than the final term:
Adding the "head" and the first few terms of the "tail" together we get:
...
Wikipedia