Implementing a spigot algorithm for the digits of e

For Perl Weekly Challenge 004 I showed how the digits for π could be generated using a so called spigot algorithm which generated the digits one at a time, as if the were flowing like water from a spigot. These algorithms were first described not for π but for Euler's number e in 1968 by Sale[1].

The algorithm

Sale's paper is linked to below and, unlike a lot of academic articles, is freely available. The paper is two pages long and is pretty digestible. Clearly it is a product of its time (1968) but the main points are timeless. The core idea is that if you examine the standard computation for e 

e = 1/0! + 1/1! + 1/2! + 1/3! + ...

you see that after the second term all subsequent terms are less than 1. If you pick the number of digits you want ahead of time you can iteratively compute each term (starting from the "right side") and multiply it by 10 to generate an integer part, which is the digit you seek, along with the remainder which is used to compute the next digit. Each digit is computed in this way.

Both the Perl 5 and Perl 6 implementations proceed roughly the same way.

  1. The number of terms required ($m) are computed using logarithms to ease computation as done in the paper.
  2. The initial list of values for each term is set to be all 1s.
  3. The computation of digits is performed in a loop with each digit stored for output. How this is handled is the only significant difference between the Perl 5 and Perl 6 implementations. In Perl 5 the digits are saved to an array which is returned and then printed. In Perl 6 they are sent to a channel and printed in batches. That is, my Perl 5 code computes the digits, prints them and exits while my Perl 6 code runs in an infinite loop continuously printing digits.

Perl 5

Sample Run

$ perl perl5/ch-1.pl 50
2.71828182845904523536028747135266249775724709369995

Perl 6

Sample Run

Discussion

Once there Perl 5 version was done I thought it would be worthwhile to try something different in the Perl 6 version. How about creating a true spigot! Meaning, one that runs continuously. Sale's algorithm is not perfectly suited for this because we are starting "from the right" but since we want to create an infinite generator we need to do a lot of wasted computation. For each computed batch we only print out the net new terms.

The use of gather loop is the construct used to create the infinite generator, along with the take, which checks to see if the channel is empty in which case it computes the next batch of 50 digits. The choice of 50 here was arbitrary.

References

[1] A. H. J. Sale, The Calculation of e to Many Significant Digits, The Computer Journal, Volume 11, Issue 2, August 1968, Pages 229–230

Comments for this post were locked by the author