杏吧原创

Forget your times tables 鈥� mathematicians have found a new, faster way to multiply two numbers together. The method, which works only for whole numbers, is a landmark result in computer science. 鈥淭his is big news,鈥� says Joshua Cooper at the University of South Carolina.

To understand the new technique, which was by David Harvey at the University of New South Wales, Australia, and Joris van der Hoeven at the Ecole Polytechnique near Paris, France, it helps to think back to the longhand multiplication you learned at school.

We write down two numbers, one on top of the other, and then painstakingly multiply each digit of one by each digit of the other, before adding all the results together. 鈥淭his is an ancient algorithm,鈥� says Cooper.

If your two numbers each have n digits, this way of multiplying will require roughly n² individual calculations. 鈥淭he question is, can you do better?鈥� says Cooper.

Lots of logs

Starting in the 1960s, mathematicians began to prove that they could. First Anatoly Karatsuba found an algorithm that could turn out an answer in no more than n^1.58 steps, and in 1971, Arnold Sch枚nhage and Volker Strassen found a way to peg the number of steps to the complicated expression n*(log(n))*log(log(n)) 鈥� here 鈥渓og鈥� is short for logarithm.

These advances had a major impact on computing. Whereas a computer using the longhand multiplication method would take about聽six months to multiply two billion-digit numbers together, says Harvey, the Sch枚nhage-Strassen algorithm can do it in 26 seconds.

The landmark 1971 paper also suggested a possible improvement, a tantalising prediction that multiplication might one day be possible in no more than n*log(n) steps. Now Harvey and van der Hoeven appear to have proved this is the case. 鈥淚t finally appears to be possible,鈥� says Cooper. 鈥淚t passes the smell test.鈥�

鈥淚f the result is correct, it鈥檚 a major achievement in computational complexity theory,鈥� says Fredrik Johansson at INRIA, the French research institute for digital sciences, in Bordeaux. 鈥淭he new ideas in this work are likely to inspire further research and could lead to practical improvements down the road.鈥�

Cooper also praises the originality of the research, although stresses the complexity of the mathematics involved. 鈥淵ou think, jeez, I鈥檓 just multiplying two integers, how complicated can it get?鈥� says Cooper. 鈥淏ut boy, it gets complicated.鈥�

So, will this make calculating your tax returns any easier? 鈥淔or human beings working with pencil and paper, absolutely not,鈥� says Harvey. Indeed, their version of the proof only works for numbers with more than 10 to the power of 200 trillion trillion trillion digits. 鈥淭he word 鈥榓stronomical鈥� falls comically short in trying to describe this number,鈥� says Harvey.

While future improvements to the algorithm may extend the proof to more humdrum numbers only a few trillion digits long, Cooper thinks its real value lies elsewhere. From a theoretical perspective, he says, this work allows programmers to provide a definitive guarantee of how long a certain algorithm will take. 鈥淲e are optimistic that our new paper will allow us to achieve further practical speed-ups,鈥� says van der Hoeven.

Harvey thinks this may well be the end of the story, with no future algorithm capable of beating n*log(n). 鈥淚 would be extremely surprised if this turned out to be wrong,鈥� he says, 鈥渂ut stranger things have happened.鈥�