Two mathematicians from Australia and France have come up with a new, faster way to multiply extremely long numbers together.
In doing so, they have cracked an algorithmic puzzle that remained unsolved by some of the world's best-known math minds, for almost fifty years.
The problem with long multiplication
If we don't have a computer or a calculator, multiplying long numbers together can be an extremely time-consuming exercise.
To do so, we have to perform a separate multiplication for each digit in the problem before adding the results together. It's not just a problem for the average person, either. Computers also encounter problems with long multiplication.
As Science Alert points out, computers' bottlenecks in performing calculations are imposed by the limits of the abstract mathematical rules that we utilize.
In other words, long multiplication is an algorithm, but it's not a very efficient one, as the process is very drawn out and time-consuming.
A new method
Now, Associate Professor David Harvey, from the University of New South Wales (UNSW)’ School of Mathematics and Statistics, has developed a new method for multiplying large numbers together, which is much faster than the typical method taught in schools.
“We have proved a 1971 conjecture of Schönhage and Strassen about the complexity of integer multiplication,” A/Professor Harvey said in a press release. "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," Harvey explains.
You can also check out the new method in the video below.
A surprisingly fast algorithm
Professor Harvey says he was actually surprised how speedy the multiplication algorithm is.
“People have been hunting for such an algorithm for almost 50 years. It was not a foregone conclusion that someone would eventually be successful."
For numbers with many digits — billion, trillions, or even more — is able to calculate multiplications that could otherwise take months for a computer, running standard calculation methods.
The new algorithm was developed in collaboration between Harvey and his collaborator, Joris van der Hoeven at École Polytechnique (France). A paper detailing the work was posted online at HAL.