An Algorithm for the Ages

Australian researchers have done the impossible—they’ve found the sixty-trillionth binary digit of Pi-squared! The calculation would have taken a single computer processor unit (CPU) 1,500 years to calculate, but scientists from IBM and the University of Newcastle managed to complete this work in just a few months on IBM’s BlueGene/P supercomputer, which is designed to run continuously at 1petaflop/s—that’s one quadrillion calculations per second!

Their work was based on a mathematical formula discovered a decade ago in part by the Department of Energy’s David H. Bailey, the Chief Technologist of the Computational Research Department at the Lawrence Berkeley National Laboratory.  The Australian team took Bailey’s program, which ran on a single PC processor, made it run faster and in parallel—on thousands of independent processors.

“What is interesting in these computations is that until just a few years ago, it was widely believed that such mathematical objects were forever beyond the reach of human reasoning or machine computation,” Bailey said.  “Once again we see the utter futility in placing limits on human ingenuity and technology.”

A binary digit or “bit” is the “DNA” of all computing.  In a computer, everything is represented as strings of zeroes and ones.  The decimal number 12, for instance, is represented as “1100,” and the fraction 9/16 is represented as “0.1001.”  So as one might imagine, calculating the sixty-trillionth binary digit of a number is quite a feat.

According to Professor Jonathan Borwein of the University of Newcastle, this work represents the largest single computation done for any mathematical object to date. The idea for this project sparked when IBM Australia was looking for something to do related to “Pi Day” (March 14) on a new IBM BlueGene/P computer system. Borwein proposed running Bailey’s formula for Pi-squared, as the calculation had been done for Pi itself. The team also calculated Catalan’s constant, another important number that arises in mathematics.

Why Pi?

The importance of Pi has long been known—multiply it by the diameter of any circle to get the circumference. Ancient Egyptians used this number in their design of the pyramids, meanwhile ancient scholars in Jerusalem, India, Babylon, Greece and China used this proportions in their studies of architecture and symbols.

Yet despite its longevity, Pi is one of the most mysterious numbers in mathematics. Because it is “irrational,” Pi can never be expressed as a finite decimal number and humanity will never have anything but approximations of it. So why bother solving Pi to the sixy-trillionth decimal unit? After all, a value of Pi to 40 digits would be more than enough to compute the circumference of the Milky Way galaxy to an error less than the size of a proton.

According to Bailey, one application for computing the digits of Pi is to test the integrity of computer hardware and software, which is a focus of Bailey’s research at Berkeley Lab. “If two separate computations of digits of Pi, say using different algorithms, are in agreement except perhaps for a few trailing digits at the end, then almost certainly both computers performed trillions of operations flawlessly,” he says.

For example in 1986, a Pi-calculating program that Bailey wrote at NASA, using an algorithm due to Jonathan and Peter Borwein, detected some hardware problems in one of the original Cray-2 supercomputers that had escaped the manufacturer’s tests. Along this same line, some improved techniques for computing what is known as the fast Fourier transform on modern computer systems had their roots in efforts to accelerate computations of Pi. These improved techniques are now very widely employed in scientific and engineering applications. And of course, from a mathematical perspective it’s just plain fascinating to see the digits of Pi in action.