Editing Spigot algorithm (section)

{{Short description|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 [[pi|{{pi}}]] or [[e (mathematical constant)|''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 (valve)|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.<ref>{{cite journal |author=Sale, AHJ |year=1968 |title=The calculation of ''e'' to many significant digits |journal= The Computer Journal|volume=11 |issue=2 |pages=229–230 |doi=10.1093/comjnl/11.2.229|doi-access=free }}</ref> 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.<ref>{{cite journal |url=http://geomete.com/abdali/papers/algoCACM393.pdf |author=Abdali, S Kamal |year=1970 |title=Special Series Summation with Arbitrary Precision |journal=Communications of the ACM |volume=13 |issue=9 |page=570 |doi=10.1145/362736.362756}}</ref> The name "spigot algorithm" seems to have been coined by [[Stanley Rabinowitz]] and [[Stan Wagon]], whose algorithm for calculating the digits of {{pi}} is sometimes referred to as "''the'' spigot algorithm for {{pi}}".<ref>
{{cite journal |url=http://stanleyrabinowitz.com/bibliography/spigot.pdf |title= A Spigot Algorithm for the Digits of Pi|last1= Rabinowitz|first1= Stanley|last2=Wagon|first2=Stan|journal=American Mathematical Monthly|volume=102|year=1995|pages=195–203|accessdate=8 May 2013 |doi=10.2307/2975006 |issue=3|jstor= 2975006}}</ref>

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"<ref>{{cite web|first=Jeremy|last=Gibbons|date=24 May 2004|url=http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/spigot.pdf|title=Unbounded Spigot Algorithms for the Digits of Pi}}</ref> 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 {{pi}} 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.