Skip to main content

An Unbounded Spigot Algorithm for the Digits of Pi

Jeremy Gibbons

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.

Journal
American Mathematical Monthly
Month
April
Note
Reprinted on p245−257 of "Pi: The Next Generation"‚ ed David H. Bailey and Jonathan M. Borwein‚ Springer 2016‚ ISBN 978−3−319−32377−0
Number
4
Pages
318−328
Volume
113
Year
2006
Video of talk at IIJ in March 2017, Part 1
Video of talk at IIJ in March 2017, Part 2