Abstract:
How would you go about finding, say, the billionth digit of π? There are many algorithms, that can calculate the billionth digit of π in various bases within a reasonable amount of time on a powerful computer system. However, they usually rely on calculating all the digits of π less than and including one billion. This necessarily involves arithmetic of huge numbers, which is typically implemented by means of Fast Fourier Transforms. There are also very elegant new algorithms that allow us to compute many digits of π on a personal computer. The software package Mathematica, for example, uses a fast converging series technique, developed by the Chudnovsky brothers in 1987, to compute all the decimal digits of π less than a given number [3]. However, it is not feasible to go beyond 10 million decimal digits with this method on a personal computer, because of speed and storage limitations.
In 1997, David Baily, Peter Borwein and Simon Plouffe discovered a formula for π, which allows us to extract any given hexadecimal digit of π by means of a strikingly simple method, without ever computing the digits leading up to it, in essentially linear time and logarithmic storage space [1]. Indeed, it could be programmed on a hand-held calculator. While 16 is a very natural base for computers, its occurrence in this context is rather coincidental, as we shall see below. Recall that, in base 16, the familiar decimal expansion