An anonymous reader quotes Popular Mechanics:
An assistant professor from the University of New South Wales Sydney in Australia has developed a new method for multiplying giant numbers together that’s more efficient than the “long multiplication” so many are taught at an early age. “More technically, we have proved a 1971 conjecture of Schönhage and Strassen about the complexity of integer multiplication,” associate professor David Harvey says in this video…
Schönhage and Strassen predicted that an algorithm multiplying n-digit numbers using n * log(n) basic operations should exist, Harvey says. His paper is the first known proof that it does…
The [original 1971] Schönhage-Strassen method is very fast, Harvey says. If a computer were to use the squared method taught in school on a problem where two numbers had a billion digits each, it would take months. A computer using the Schönhage-Strassen method could do so in 30 seconds. But if the numbers keep rising into the trillions and beyond, the algorithm developed by Harvey and collaborator Joris van der Hoeven at École Polytechnique in France could find solutions faster than the 1971 Schönhage-Strassen algorithm.
“It means you can do all sorts of arithmetic more efficiently, for example division and square roots,” he says. “You could also calculate digits of pi more efficiently than before. It even has applications to problems involving huge prime numbers.
“The question is, how deep does n have to be for this algorithm to actually be faster than the previous algorithms?” the assistant professor says in the video. “The answer is we don’t know.
“It could be billions of digits. It could be trillions. It could be much bigger than that. We really have no idea at this point.”
of this story at Slashdot.
Source:: Slashdot