Faster multiplies with (what else) the FFT

A friend sent me a great writeup of the new fastest known algorithm for multiplying two large numbers. Just like past fastest algorithms, it uses the Fast Fourier Transform, a clever algorithm for computing the Fourier Transform efficiently that was developed in 1965 (and a re-discovery of something Gauss originally developed in 1805). The Fourier Transform is simply a way of changing coordinate system of a signal to the Fourier domain, a beautiful and elegant coordinate system for representing the frequencies of a signal.

As the article points out, this new algorithm may only be used in a limited setting, as hardware implementation constraints dictate. But in cryptography or scientific computing, one may need to multiply extremely large numbers, and the hardware overhead of transferring to an on-chip FFT implementation may become worthwhile. The article itself points out that even the relative computational cost of multiplication versus addition has changed at the hardware level.

That said, the new algorithm achieves what people believe is the lower bound for multiplicative computations. Now on to proving that it is, indeed, the lower bound.

From the article:

On March 18, two researchers described the fastest method ever discovered for multiplying two very large numbers. The paper marks the culmination of a long-running search to find the most efficient procedure for performing one of the most basic operations in math.

...

In 1971 Arnold Schönhage and Volker Strassen published a method capable of multiplying large numbers in n × log n × log(log n) multiplicative steps, where log n is the logarithm of n. For two 1-billion-digit numbers, Karatsuba’s method would require about 165 trillion additional steps.

Schönhage and Strassen’s method, which is how computers multiply huge numbers, had two other important long-term consequences. First, it introduced the use of a technique from the field of signal processing called a fast Fourier transform. The technique has been the basis for every fast multiplication algorithm since.

Second, in that same paper Schönhage and Strassen conjectured that there should be an even faster algorithm than the one they found — a method that needs only n × log n single-digit operations — and that such an algorithm would be the fastest possible. Their conjecture was based on a hunch that an operation as fundamental as multiplication must have a limit more elegant than n × log n × log(log n).

“It was kind of a general consensus that multiplication is such an important basic operation that, just from an aesthetic point of view, such an important operation requires a nice complexity bound,” Fürer said. “From general experience the mathematics of basic things at the end always turns out to be elegant.”

Schönhage and Strassen’s ungainly n × log n × log(log n) method held on for 36 years. In 2007 Fürer beat it and the floodgates opened. Over the past decade, mathematicians have found successively faster multiplication algorithms, each of which has inched closer to n × log n, without quite reaching it. Then last month, Harvey and van der Hoeven got there.

Their method is a refinement of the major work that came before them. It splits up digits, uses an improved version of the fast Fourier transform, and takes advantage of other advances made over the past forty years. “We use [the fast Fourier transform] in a much more violent way, use it several times instead of a single time, and replace even more multiplications with additions and subtractions,” van der Hoeven said.