An Unbounded Spigot Algorithm for the Digits of Pi

Abstract

Rabinowitz and Wagon (American Mathematical Monthly 102(3):195–203, 1995) present a spigot algorithm for computing the digits of π. 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 π, with the same incremental characteristics but without requiring the prior bound.

There is a typo (an off-by-one error) in the definition of piG: in the function next, the variable x should be 27*i-12 rather than 27*i+15; thank you to Frank Taylor for spotting this. Also, the matrix multiplication was the wrong way round in the definition of p in Conjecture 1, and the definition of extr didn't typecheck.