Bailey–Borwein–Plouffe formula

Bailey–Borwein–Plouffe formula. The Bailey–Borwein–Plouffe (BBP) formula is a remarkable spigot algorithm for computing the binary representation of the mathematical constant pi. Discovered in 1995 by David H. Bailey, Peter Borwein, and Simon Plouffe, it allows for the extraction of specific hexadecimal digits of pi without calculating all preceding digits. This property revolutionized computational approaches to pi and influenced research in experimental mathematics and distributed computing projects.

Definition and formula

The standard BBP formula for pi is an infinite series given by: $\backslash pi\; =\; \backslash sum\_\{k\; =\; 0\}^\backslash infty\; \backslash left[\; \backslash frac\{1\}\{16^k\}\; \backslash left(\; \backslash frac\{4\}\{8k\; +\; 1\}\; -\; \backslash frac\{2\}\{8k\; +\; 4\}\; -\; \backslash frac\{1\}\{8k\; +\; 5\}\; -\; \backslash frac\{1\}\{8k\; +\; 6\}\; \backslash right)\; \backslash right]$. The formula's structure is a linear combination of rational number terms with a power of two denominator, specifically $16^k$. This base-16 form is key to its digit-extraction property. Similar BBP-type formulas have been discovered for other mathematical constants, including Catalan's constant and Apéry's constant, by mathematicians like Victor Adamchik.

Discovery and history

The formula was discovered in September 1995 by David H. Bailey using a computer program implementing the PSLQ algorithm, an integer relation algorithm he helped develop with Helaman Ferguson. The discovery was made at the NASA Ames Research Center, where Bailey worked. Simon Plouffe independently conjectured the existence of such a formula, and Peter Borwein contributed to the formal proof and analysis. The announcement was a major event at the time, covered by publications like The New York Times.

Mathematical properties

The most significant property is its status as a spigot algorithm, enabling the computation of the $n$th hexadecimal digit of pi directly using modular arithmetic and binary exponentiation, without needing the first $n-1$ digits. This relies on the formula's structure, where multiplying by $16^n$ and taking the fractional part isolates the desired digit. The formula is not a Machin-like formula but is related to identities involving the dilogarithm. Its irrationality measure and connections to transcendental number theory have been studied extensively.

Applications and significance

The primary application is in the efficient, distributed verification of computed digits of pi, notably in projects like PiHex and later y-cruncher. It allowed Fabrice Bellard to set records for digit extraction. Beyond computation, the formula's existence spurred the field of experimental mathematics, demonstrating the power of integer relation algorithms like PSLQ. It has theoretical implications in complexity theory for questions about the normal number status of pi and other constants, influencing work by mathematicians such as Jonathan Borwein and Richard Crandall.

Computation and algorithms

Practical computation uses the digit-extraction algorithm, which performs calculations modulo the denominator terms to avoid high-precision arithmetic. Key optimizations include the binary exponentiation method for computing $16^n\; \backslash mod\; (8k+c)$ efficiently. This algorithm was implemented in the PiHex project, which used a distributed computing network. Subsequent refinements by David H. Bailey and Richard Crandall generalized the approach to other bases and constants, forming the basis for efficient computations in software like Mathematica and Maple.

Category:Pi algorithms Category:1995 in science