Misplaced Pages

Spigot algorithm

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Digit extraction algorithm) Algorithm for computing the value of a transcendental number

A spigot algorithm is an algorithm for computing the value of a transcendental number (such as π or e) that generates the digits of the number sequentially from left to right providing increasing precision as the algorithm proceeds. Spigot algorithms also aim to minimize the amount of intermediate storage required. The name comes from the sense of the word "spigot" for a tap or valve controlling the flow of a liquid. Spigot algorithms can be contrasted with algorithms that store and process complete numbers to produce successively more accurate approximations to the desired transcendental.

Interest in spigot algorithms was spurred in the early days of computational mathematics by extreme constraints on memory, and such an algorithm for calculating the digits of e appeared in a paper by Sale in 1968. In 1970, Abdali presented a more general algorithm to compute the sums of series in which the ratios of successive terms can be expressed as quotients of integer functions of term positions. This algorithm is applicable to many familiar series for trigonometric functions, logarithms, and transcendental numbers because these series satisfy the above condition. The name "spigot algorithm" seems 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 terms of the infinite series that will be processed must be specified in advance. The term "streaming algorithm" indicates an approach without this restriction. This allows the calculation to run indefinitely varying the amount of intermediate storage as the calculation progresses.

A variant of the spigot approach uses an algorithm which can be used to compute a single arbitrary digit of the transcendental without computing the preceding digits: an example is the Bailey–Borwein–Plouffe formula, a digit extraction algorithm for π which produces base 16 digits. The inevitable truncation of the underlying infinite series of the algorithm means that the accuracy of the result may be limited by the number of terms calculated.

Example

This example illustrates the working of a spigot algorithm by calculating the binary digits of the natural logarithm of 2 (sequence A068426 in the OEIS) using the identity

ln ⁡ ( 2 ) = ∑ k = 1 ∞ 1 k 2 k . {\displaystyle \ln(2)=\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.}

To start calculating binary digits from, as an example, the 8th place we multiply this identity by 2 (since 7 = 8 − 1):

2 7 ln ⁡ ( 2 ) = 2 7 ∑ k = 1 ∞ 1 k 2 k . {\displaystyle 2^{7}\ln(2)=2^{7}\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.}

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:

2 7 ln ⁡ ( 2 ) = ∑ k = 1 7 2 7 − k k + ∑ k = 8 ∞ 1 k 2 k − 7 . {\displaystyle 2^{7}\ln(2)=\sum _{k=1}^{7}{\frac {2^{7-k}}{k}}+\sum _{k=8}^{\infty }{\frac {1}{k2^{k-7}}}\,.}

We are only interested in the fractional part of this value, so we can replace each of the summands in the "head" by

2 7 − k k mod 1 = 2 7 − k mod k k . {\displaystyle {\frac {2^{7-k}}{k}}{\bmod {1}}={\frac {2^{7-k}{\bmod {k}}}{k}}\,.}

Calculating each of these terms and adding them to a running total where we again only keep the fractional part, we have:

k A = 2 B = A mod k C = ⁠B/k⁠ Sum of C mod 1
1 64 0 0 0
2 32 0 0 0
3 16 1 ⁠1/3⁠ ⁠1/3⁠
4 8 0 0 ⁠1/3⁠
5 4 4 ⁠4/5⁠ ⁠2/15⁠
6 2 2 ⁠1/3⁠ ⁠7/15⁠
7 1 1 ⁠1/7⁠ ⁠64/105⁠

We add a few terms in the "tail", noting that the error introduced by truncating the sum is less than the final term:

k D = ⁠1/k2⁠ Sum of D Maximum error
8 ⁠1/16⁠ ⁠1/16⁠ ⁠1/16⁠
9 ⁠1/36⁠ ⁠13/144⁠ ⁠1/36⁠
10 ⁠1/80⁠ ⁠37/360⁠ ⁠1/80⁠

Adding the "head" and the first few terms of the "tail" together we get:

2 7 ln ⁡ ( 2 ) mod 1 ≈ 64 105 + 37 360 = 0.10011100 … 2 + 0.00011010 … 2 = 0.1011 … 2 , {\displaystyle 2^{7}\ln(2){\bmod {1}}\approx {\frac {64}{105}}+{\frac {37}{360}}=0.10011100\ldots _{2}+0.00011010\ldots _{2}=0.1011\ldots _{2}\,,}

so the 8th to 11th binary digits in the binary expansion of ln(2) are 1, 0, 1, 1. Note that we have not calculated the values of the first seven binary digits – indeed, all information about them has been intentionally discarded by using modular arithmetic in the "head" sum.

The same approach can be used to calculate digits of the binary expansion of ln(2) starting from an arbitrary nth position. The number of terms in the "head" sum increases linearly with n, but the complexity of each term only increases with the logarithm of n if an efficient method of modular exponentiation is used. The precision of calculations and intermediate results and the number of terms taken from the "tail" sum are all independent of n, and only depend on the number of binary digits that are being calculated – single precision arithmetic can be used to calculate around 12 binary digits, regardless of the starting position.

References

  1. Sale, AHJ (1968). "The calculation of e to many significant digits". The Computer Journal. 11 (2): 229–230. doi:10.1093/comjnl/11.2.229.
  2. Abdali, S Kamal (1970). "Special Series Summation with Arbitrary Precision" (PDF). Communications of the ACM. 13 (9): 570. doi:10.1145/362736.362756.
  3. Rabinowitz, Stanley; Wagon, Stan (1995). "A Spigot Algorithm for the Digits of Pi" (PDF). American Mathematical Monthly. 102 (3): 195–203. doi:10.2307/2975006. JSTOR 2975006. Retrieved 8 May 2013.
  4. Gibbons, Jeremy (24 May 2004). "Unbounded Spigot Algorithms for the Digits of Pi" (PDF).

Further reading

Category: