Earlier this year, the journal Computing in Science & Engineering (CISE) published a list of the top 10 algorithms of the century (see http://computer.org/cise/articles/Top_Algorithms.htm).
“Computational algorithms are probably as old as civilization,” Francis Sullivan of the Institute for Defense Analyses’ Center for Computing Sciences in Bowie, Md. noted in an editorial in the January/February issue of CISE. Ancient tablets bearing Sumerian cuneiform, for example, feature descriptions of procedures for reckoning in base 60.
“Algorithms have advanced in startling and unexpected ways in the 20th century,” Sullivan continued. “The algorithms we chose. . .have been essential for progress in communications, health care, manufacturing, economics, weather prediction, defense, and fundamental science. Conversely, progress in these areas has stimulated the search for ever-better algorithms.”
Many of the selections are now familiar, finely tuned, heavily used tools. The Metropolis algorithm for Monte Carlo methods, the simplex method in linear programming, the Fast Fourier Transform for analyzing and manipulating digital data, and the Quicksort algorithm fit into this category.
Some, however, are somewhat less familiar. In particular, the so-called PSLQ algorithm has only recently become a computational staple. It gives researchers an efficient method for detecting what are called integer relations. Given a string of n real numbers, x1,. . .,xn, the problem is to find a set of integers a1,. . .,an (if they exist and are not all zero) such that a1x1 +. . .+anxn = 0.
The PSLQ procedure can be regarded as a jazzed-up version of an integer-relation algorithm dating back more than 2,000 years to the Greek geometer Euclid of Alexandria (365–300 B.C.).
The Euclidean algorithm offers a recipe for finding the greatest common divisor of two whole numbers. Suppose the given numbers are 12 and 18. Twelve is evenly divisible by 1, 2, 3, 4, 6, and 12; 18 is evenly divisible by 1, 2, 3, 6, 9, and 18. By comparing the lists, you can see that both numbers are evenly divisible by 1, 2, 3, and 6. Hence, the largest common divisor is 6. That’s easy to figure out by trial and error when the given numbers are small. The Euclidean algorithm works with numbers of any size.
To find the greatest common divisor of 77 and 187 using the Euclidean algorithm involves the process of long division, which you might have first encountered in elementary school. Divide 77 into 187. The remainder is 33. Divide the remainder, 33, into the original divisor, 77. The new remainder is 11. Divide 11 into 33. The remainder is 0. You can then conclude that the greatest common divisor is 11. (See http://www.cut-the-knot.com/blue/Euclid.html.)
Determining the greatest common divisor is an example of finding an integer relation between two numbers. In 1977, mathematician Helaman Ferguson, then at Brigham Young University in Provo, Utah, and colleague Rodney Forcade discovered a generalization of the Euclidean algorithm. The PSLQ version now serves as a practical computational scheme for finding integer relations involving more than two numbers and for performing a process known as lattice reduction.
Since that landmark achievement, Ferguson has gained fame as a sculptor of mathematically inspired forms (see Minimal Snow, March 6, 1999). Indeed, he sees an intimate link between his mathematical algorithm and the art of carving. Both are subtractive processes. In the Euclidean algorithm, the mathematician chips away at a pair of numbers until their greatest common divisor is finally revealed. In sculpture, the artist chisels away rock until the envisioned form appears.
The PSLQ algorithm has become an important component of the emerging discipline of experimental mathematical–the use of computers as an exploratory tool in mathematical research. It has been used to discover unknown mathematical identities, such as a remarkable, simple formula for calculating isolated binary digits of the number pi without computing and keeping track of all the preceding numbers (see Pick a Digit, Any Digit, Feb. 28, 1998).
More recently, physicist David J. Broadhurst of the Open University in Milton Keynes, England, has used the PSLQ algorithm to discover unexpected relations in quantum field theory.
Such discoveries may have important ramifications. The pi formula, for instance, raises questions about the long-held but never proved assumption that pi’s digits are random. The results in quantum field theory involving Feynman diagrams suggest unsuspected relationships among formulas associated with fundamental particles.
Then there is the wonder of the algorithm itself.
“For me, great algorithms are the poetry of computation,” Sullivan remarked in his CISE editorial. “Just like verse, they can be terse, allusive, dense, and even mysterious. But once unlocked, they cast a brilliant new light on some aspect of computing.”
References:
