For most of us, multiplying anything bigger than the times tables we learnt at school requires a calculator. Should we not have one handy, we would do long multiplication, those towers we wrote out in primary school. But these take quite a long time, and even computers take long using this algorithm when computing billion-digit numbers. Now, these mathematicians from Australia and France have devised a new way to multiply larger numbers faster.
The technique these mathematicians use is not a new algorithm, rather it is the Schönhage–Strassen algorithm, which was never proved by German mathematicians.
This algorithm “predicted that there should exist an algorithm that multiplies n-digit numbers using essentially n*log(n) basic operations,” said David Harvey from the University of New South Wales, one of the paper’s authors.
“Our paper gives the first known example of an algorithm that achieves this,” Harvey said. “People have been hunting for such an algorithm for almost 50 years. It was not a forgone conclusion that someone would eventually be successful.”
So, using this technique, the authors theorise that a computer could complete a multiplication that could take months with billion-digit numbers in just 30 seconds.
This new algorithm would only ever be useful for these kinds of extremely large numbers. In the paper the one example equates to 10214857091104455251940635045059417341952
The authors acknowledged that they still have to prove their theory rigorously. “I’m still terrified that it might turn out to be wrong,” Harvey told the AAP.