Did You Ever Wonder . . ?

An alchemical algorithm

In 1977, Helaman Ferguson and Rodney Forcade made the biggest advance in integer-relation detection since Euclid, whose method for finding the greatest common divisor of two numbers dates to about 300 BCE. For over 2,000 years mathematicians as renowned as Leonhard Euler, Carl Gustav Jacobi, Henri Poincaré, and Hermann Minkowksi sought ways to find integer relations among more than two numbers. Ferguson and Forcade succeeded where they failed.

In the 1990s David Bailey collaborated with Ferguson on a new algorithm called PSLQ, which runs on high-performance computers. Integer-relation detection suddenly became practical, efficient, and fruitful -- so much so that in 2000, the editors of Computing in Science and Engineering named PSLQ one of the "top 10 algorithms of the century."

pi formula
This simple formula can calculate any binary or hexadecimal digit of pi without calculating the digits preceding it.

Among other relations, PSLQ has uncovered formulas in algebraic number theory, relations among quantum field theory constants symbolized by Feynman diagrams, and a surprisingly simple formula, given in a paper by Bailey, Peter Borwein, and Simon Plouffe (BBP), that can calculate any binary digit of pi without calculating the digits preceding it.

Now a desktop computer can do what mathematicians, until recently, thought was impossible (although BBP works only for binary digits, not decimal ones).

Finding pi's millionth binary digit takes a few seconds, using this simple program and very little memory.

Or visit a NERSC web page, to find out if your name, or any short digit string, appears within pi's first four billion binary digits.

Underlying the astonishing BBP formula lies a deeper theory of the expansions of fundamental constants, one that has provided a remarkable proof of the digit randomness of an entire class of numbers. Pi isn't included yet, but it may not be far behind.

More on the BBP algorithm

More on PSLQ and its uses


Did You Ever Wonder Web Site

Ernest Orlando Lawrence Berkeley National Laboratory