Revision as of 09:51, 15 March 2008 editGandalf61 (talk | contribs)Autopatrolled, Extended confirmed users, Pending changes reviewers16,144 edits add example← Previous edit | Revision as of 16:10, 18 April 2008 edit undoGandalf61 (talk | contribs)Autopatrolled, Extended confirmed users, Pending changes reviewers16,144 edits add exampleNext edit → | ||
Line 1: | Line 1: | ||
A '''spigot algorithm''' is an ] used to compute the value of a mathematical constant such as ] or ]. Unlike ] algorithms, a spigot algorithm yields digits incrementally without using previously computed digits. The ] for the binary digits of π is an example of a spigot algorithm. | A '''spigot algorithm''' is an ] used to compute the value of a mathematical constant such as ] or ]. Unlike ] algorithms, a spigot algorithm yields digits incrementally without using previously computed digits. The ] for the binary digits of π is an example of a spigot algorithm. | ||
==Example== | |||
This example illustrates the working of a spigot algorithm by calculating the binary digits of the ] of 2 {{OEIS|id=A068426}} using the identity | |||
:<math>\ln(2)=\sum_{k=1}^{\infty}\frac{1}{k2^k}\, .</math> | |||
To start calculating binary digits from, say, the 8th place we multiply this identity by 2<sup>7</sup>: | |||
:<math>2^7\ln(2) =2^7\sum_{k=1}^{\infty}\frac{1}{k2^k}\, .</math> | |||
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: | |||
:<math>2^7\ln(2) =\sum_{k=1}^{7}\frac{2^{7-k}}{k}+\sum_{k=8}^{\infty}\frac{1}{k2^{k-7}}\, .</math> | |||
We are only interested in the fractional part of this value, so we can replace each of the terms in the "head" by | |||
:<math>\frac{2^{7-k} \mod k}{k}\, .</math> | |||
Calculating each of these terms and adding them to a running total where we again only keep the fractional part, we have: | |||
:{| class="wikitable" | |||
|- | |||
! ''k'' | |||
! ''A'' = 2<sup>7-''k''</sup> | |||
! ''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: | |||
:{| class="wikitable" | |||
|- | |||
! ''k'' | |||
! ''D'' = 1/''k''2<sup>''k''-7</sup> | |||
! 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: | |||
:<math>2^7\ln(2)\mod{1} \approx \frac{64}{105}+\frac{37}{360}=0.10011100 \cdots_{2} + 0.00011010 \cdots_{2} = 0.1011 \cdots_{2}\, ,</math> | |||
so the 8th to 11th binary digits in the binary expansion of ln(2) are 1, 0, 1, 1. | |||
The same approach can be used to calculate digits of the binary expansion of ln(2) starting from an arbitary ''n''<sup>th</sup> 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 ] is used. The ] 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 - ] arithmetic can be used to calculate around 12 binary digits, regardless of the starting position. | |||
==External links== | ==External links== |
Revision as of 16:10, 18 April 2008
A spigot algorithm is an algorithm used to compute the value of a mathematical constant such as π or e. Unlike recursive algorithms, a spigot algorithm yields digits incrementally without using previously computed digits. The Bailey-Borwein-Plouffe formula for the binary digits of π is an example of a spigot algorithm.
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
To start calculating binary digits from, say, the 8th place we multiply this identity by 2:
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 terms 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:
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:
so the 8th to 11th binary digits in the binary expansion of ln(2) are 1, 0, 1, 1.
The same approach can be used to calculate digits of the binary expansion of ln(2) starting from an arbitary n 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.
External links
- Weisstein, Eric W. "Spigot algorithm". MathWorld.
- "Unbounded Spigot Algorithms for the Digits of Pi" (PDF).