A Sydney mathematician has cracked a maths problem that has stood for almost half a century which will enable computers to multiply huge numbers together much more quickly.
Associate Professor David Harvey, from UNSW’s School of Mathematics and Statistics, has developed a new method for multiplying together huge numbers, which is much faster than the familiar “long multiplication” method that we all learn at primary school.
“More technically, we have proved a 1971 conjecture of Schönhage and Strassen about the complexity of integer multiplication,” A/Professor Harvey says.
“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.”
Big numbers = big problems
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 (see video). 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).
Harvey says that 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.
But for numbers with enough digits – billion, trillions or even gazillions – the new algorithm, developed by Harvey and his collaborator Joris van der Hoeven at École Polytechnique (France), would outrun even Schönhage and Strassen’s algorithm.
No-one will ever find a faster method
A/Professor Harvey says that 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.”
While it’s still early days, A/Professor Harvey imagines that 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.”
A/Professor Harvey says he was surprised that such a fast multiplication algorithm is even possible.
“People have been hunting for such an algorithm for almost 50 years. It was not a forgone conclusion that someone would eventually be successful. It might have turned out that Schönhage and Strassen were wrong, and that no such algorithm is possible.
“But now we know better,” he says.
The work was posted recently online at HAL.
This article was first published on Australia’s Science Channel, the original news platform of The Royal Institution of Australia.