Events / Oxford Seminar
Unbounded Spigot Algorithms for the Digits of Pi
There is a nifty short C program by Winter and Flammenkamp for computing the first 15000 digits of pi. It is a “spigot algorithm”: the digits appear one by one, like drips from a tap, and are not further processed after being produced. It is based on an elegant series due to Leibniz. Why 15000? It is bounded: this is as far as you can get with the precision of 32-bit integers. I will show an unbounded version, which computes digits indefinitely (at the cost of arbitrary precision). What’s more, I will derive it from Leibniz’s series. I will show a couple of other series too. The algorithm exhibits a pattern I call “streaming”, which Richard Bird and I studied first in the context of data compression.
Background reading: https://www.cs.ox.ac.uk/publications/publication1674-abstract.html
Assumed knowledge: no more than high-school algebra, plus ability to read a functional program. The latter is explained in the paper linked above (which is from American Mathematical Monthly, and is implicitly a tutorial on Haskell aimed at recreational mathematicians).