A team of mathematicians from the University of New South Wales in Australia and the L’École Polytechnique in France has solved a decades-old maths riddle that allows multiplication of large numbers in a much faster time. The team’s paper was published in the multi-disciplinary open access archive HAL.
Harvey & van der Hoeven cracked a maths problem that has stood for almost half a century which will enable computers to multiply huge numbers together much more quickly. Image credit: Gerd Altmann.
“More technically, we have proved a 1971 conjecture of Schönhage and Strassen about the complexity of integer multiplication,” said Dr. David Harvey, from the School of Mathematics and Statistics at the University of New South Wales.
“They predicted that there should exist an algorithm that multiplies n-digit numbers using essentially n * log(n) basic operations.”
“Our paper gives the first known example of an algorithm that achieves this.”
“In other words, if we were to multiply the numbers 314 by 159 with the usual primary school method, we would need to calculate 9 digit-by-digit products.”
“In general, if n represents the number of digits in each number, the answer can be arrived at in n2 operations.”
Schönhage and Strassen themselves invented an algorithm needing fewer than n2 operations, but were unable to get it down to n * log(n).
“The Schönhage-Strassen algorithm is already quite fast: a computer using the primary school method would take months to multiply two numbers with a billion digits, but can do it in under 30 seconds using the Schönhage-Strassen algorithm,” Dr. Harvey said.
But for numbers with enough digits — billion, trillions or even gazillions — the new algorithm, developed by Dr. Harvey and Dr. Joris van der Hoeven from the Laboratoire d’informatique at the L’École Polytechnique, would outrun even Schönhage and Strassen’s algorithm.
Schönhage and Strassen also predicted that n * log(n) is the ‘best possible’ result — that no-one will ever find a faster multiplication algorithm.
“So in this sense, our work is expected to be the end of the road for this problem, although we don’t know yet how to prove this rigorously,” Dr. Harvey said.
“While it’s still early days, this breakthrough has an enormous number of consequences.”
“It means you can do all sorts of arithmetic more efficiently, for example division and square roots. You could also calculate digits of pi more efficiently than before. It even has applications to problems involving huge prime numbers.”
_____
David Harvey & Joris van der Hoeven. 2019. Integer multiplication in time O(n log n). HAL, id: hal-02070778
