|
Jeremy Gibbons (2003). An Unbounded Spigot Algorithm for the Digits of Pi.
Rabinowitz and Wagon (American Mathematical Monthly 102(3):195--203, 1995) present a spigot algorithm for computing the digits of Pi. A spigot algorithm yields its outputs incrementally, and does not reuse them after producing them. Their algorithm is inherently bounded; it requires a commitment in advance to the number of digits to be computed, and in fact might still produce an incorrect last few digits. We propose two streaming algorithms based on the same characterization of Pi, with the same incremental characteristics but without requiring the prior bound.
Working with infinite seriers is always fun, and in a lazy language it's also quite easy. As you'd expect, this paper uses Haskell.
Slightly more practical than the classic Hamming numbers example.
Posted to functional by Ehud Lamm on 11/20/03; 4:07:05 AM
|
An Unbounded Spigot Algorithm for the Digits of Pi
