The multiplication of integers is a problem that has kept mathematicians busy since Antiquity. The “Babylonian” method we learn at school requires us to multiply each digit of the first number by each digit of the second one. But when both numbers have a billion digits each, that means a billion times a billion or 1018 operations.
At a rate of a billion operations per second, it would take a computer a little over 30 years to finish the job. In 1971, the mathematicians Schönhage and Strassen discovered a quicker way, cutting calculation time down to about 30 seconds on a modern laptop. In their article, they also predicted that another algorithm—yet to be found—could do an even faster job. Joris van der Hoeven, a CNRS researcher from the École Polytechnique Computer Science Laboratory LIX, and David Harvey from the University of New South Wales (Australia) have found that algorithm.
They present their work in a new article that is available to the scientific community through the online HAL archive. But one problem raised by Schönhage et Strassen remains to be solved: proving that no quicker method exists. This poses a new challenge for theoretical computer science.
Comments are closed.