The Miraculous Bailey-Borwein-Plouffe Pi Algorithm

Steven Finch, MathSoft Engineering & Education, Inc.

Overview: 10/1/95

David Bailey, Peter Borwein and Simon Plouffe have recently computed the ten billionth digit in the hexadecimal expansion of pi. They utilized an astonishing formula:

which enables one to calculate the dth digit of pi without being forced to calculate all the preceding d-1 digits. No one had previously even conjectured that such a digit-extraction algorithm for pi was possible. Click here to see the original CECM announcement and here to see a description for a non-technical audience. Bailey, Borwein and Plouffe discovered their formula using the PSLQ lattice reduction algorithm.

We present here a very small verification of the digit-extraction result. Mathcad PLUS 6.0 was useful to us for the purpose of a hasty check up to 1000 digits. A check of more digits is ongoing. We wished to post our work as rapidly as possible, believing that this incomplete work would be of interest to others.

The Mathcad PLUS 6.0 file plffe1.mcd contains a dynamic, working version of our verification. If you have 6.0 and don't know how to view web-based Mathcad files, then you should read these instructions.

The following screenshot exhibits our verification algorithm (which, incidentally, we recognize is far less efficient than Bailey, Borwein and Plouffe's original algorithm).

Here are the results of our quick check, which we plan to update later:

It is trivial to convert a hexadecimal expansion to a binary expansion. On the other hand, the following question evidently remains unanswered. Do there exist polynomials a(n) and b(n) possessing integer coefficients such that

Postscript: 10/5/95

Simon Plouffe very kindly visited this site and has pointed out that our verification algorithm above will execute significantly faster if the four terms in his formula are evaluated separately rather than collecting them as we have into a ratio of a quadratic with a quartic. The highly-efficient Fortran program (used to compute the ten billionth digit of pi) is now available. Here is a version of the same program in C. A further summary is found in the sci.math announcement.

The just-released, historic Bailey-Borwein-Plouffe paper On the rapid computation of various polylogarithmic constants starts where we have left off. Reading it, one gains the impression of an emerging and deep theory of transcendental number computation. The untapped consequences of the digit-extraction formula and others like it would appear to be rich and profound. (The official version of the paper is in Mathematics of Computation 66 (1997) 903-913.)

Postscript: 1/15/96

Victor Adamchik and Stan Wagon have recently published a fascinating HTML paper Pi: A 2000-Year Search Changes Direction. This paper presents many new formulas, including the following:

for any real or complex value r. Observe that this specializes to the original Bailey-Borwein-Plouffe formula when we set r = 0. (Their article was published in American Math. Monthly 104 (1997) 852-854.)

We refer the interested reader to the essay Archimedes' constant for a detailed overview of pi facts and formulas and to CECM preprint 96:070: The Quest for Pi (which appeared in Math. Intellig. 19 (1997) 50-57). Plouffe has also compiled a Table of current records for the computation of constants which gives the latest information on calculations such as these.

Postscript: 10/7/96

Fabrice Bellard has completed a computation of the 100 billionth hexadecimal digit of pi. Here is his sci.math posting, which interestingly appeared one year, almost to the day, after Bailey, Borwein and Plouffe's announcement. Might the one trillionth hexadecimal digit of pi be known next year?

Postscript: 1/12/97

Simon Plouffe has discovered a new algorithm to compute the nth digit of pi and certain other mathematical constants in any base with very little memory. The price of such generality is speed: it is not as fast as the Bailey-Borwein-Plouffe algorithm (but is comparable to other classical methods for computing pi). Here is a description of his work, along with Bellard's improvement.

Postscript: 2/28/97

Progress continues! Fabrice Bellard has discovered another miraculous formula which he estimates is 43% faster than the Bailey-Borwein-Plouffe formula. A very simple proof is found here. Another CECM resource is also now available: The Pi Pages.

Postscript: 9/22/97

Fabrice Bellard has employed the Bailey-Borwein-Plouffe formula to compute the trillionth (10^12th) binary digit of pi. Here is his announcement.

Postscript: 2/9/99

Colin Percival has succeeded in calculating the five trillionth bit (1.25 trillionth hexit) and the forty trillionth bit (10 trillionth hexit) of pi using Bellard's formula. See his web page for more information. He is now heading an effort to calculate the quadrillionth bit (250 trillionth hexit) of pi.

More articles on the Bailey-Borwein-Plouffe formula continue to appear. For example, Mike Hirschhorn's paper A new formula for pi (available here in postscript) gives a slightly different generalization of the formula, but his proof is simply an undergraduate exercise in integration! (An abbreviated version appeared in Australian Math. Society Gazette 25 (1998) 82-83.)

Postscript: 2/5/00

Alexandru Lupas has discovered an identity which includes the Bailey-Borwein-Plouffe and Adamchik-Wagon formulas as special cases. His preprint, Some BBP-functions, is available in DVI format.

Postscript: 9/11/00

The quadrillionth bit of pi is 0, according to Colin Percival!