Cyber Oppression

     I’ve been doing a lot of research on the practice of computing the digits of Pi.  The first question is, “Why?”.  In the great majority of real-world applications, an approximation of few digits (i.e. 3.14) is close enough — it’s hard to imagine any calculation where an approximation to 20 digits would not be accurate enough.
One of the most interesting things about Pi is how much we don’t know — the “state of our ignorance” as Borwein puts it (CHECK).  For instance, in all calculations so far, the frequency of decimal and hexidecimal digits has been very close to what you would expect from a completely random  distribbution of digits (each digit has about 1/10th probability of occurring, or 1/16th for hexadecimal)… but there is no proof that this must be the case for all digits.  In “Contact” by Arthur Clarke he speculated about a binary “message” hidden in the digits of Pi — we currently have no proof that such a message or similar statistical anomaly exists, though of course it seems unlikely.
Also, as an excersize in computability and algorithms, it is somewhat interesting to look at the records for calculating the digits of pi.  The last few records have been set by Professor Kanada, using a number of supercomputers… the current record is about 1.3 trillion digits.  In ASCII format, that’s 1.3TB of digits (or in a more efficient 4-bits-per-digit representation, 650GB).  This means that memory/disk efficiency will be key, and algorithms that calculate digits indiviually will probably be preferred; if at all-possible, the only number of the final precision we want to store/use in our algorithm is our final answer, not a number of intermediate steps.

The algorithms for approximating Pi involve some kind of converging series.

Here are some links to interesting papers on this topic:

* Unbounded Spigot Algorithms for the Digits of Pi — Jeremy Gibbons responds to and improves upon the spigot algorithm proposed by Rabinowitz and Wagon in 1995.

* A Spigot Algorithm for the Digits of Pi — Rabinowitz and Wagon give a great “spigot” style algorithm for computing digits of Pi,

Ramanujan, Modular Equations, and Approximations to Pi OR How to Compute One Billion Digits of Pi .  — Borwein, Borwein, and Bailey evaluate a number of different series and algorithms that converge upon Pi. with a focus on computability and speed of convergence. Expands on Ramanujan’s work.