An assistant professor from the University of New South Wales Sydney in Australia has come up with a new technique for multiplying huge numbers together that is reportedly more efficient as compared to the long multiplication.
Associate professor David Harvey says, ‘More technically, we have proved a 1971 conjecture of Schönhage and Strassen about the complexity of integer multiplication.’ The Schönhage–Strassen algorithm was developed by two German mathematicians. It was the fastest method of multiplication from 1971 through 2007. A faster method was developed back in 2007, but it is rarely used today.
Harvey says that Schönhage and Strassen did predict that an algorithm multiplying n-digit numbers by making use of n* log(n) basic operations should exist. His paper is the very first proof that it does indeed exist. Harvey chose the example of 314 multiplied by 150. Most of the people reply on multiplying each individual number together and then adding up the sums; 9 is multiplied by 4, 1, and 3; then 5 gets multiplied by 4, 1, and 3, and so on. The result ends with 9 digit-by-digit products.
This method is referred to as n2 or n squared since one must multiply n by n a number of times. It yields the right answer, but Schönhage and Strassen came with a quicker method. It was able to step away from n2 and into something smaller. However, the form of n*log(n) did present a problem. The Schönhage-Strassen method is incredibly fast, nonetheless, as per Professor David Harvey. A computer using the squared method for multiplying two numbers each having a billion digits each would need months to complete the calculation. On the other hand, using the Schönhage-Strassen method, the computer could do it in 30 seconds.
However, if numbers keep on going up into trillions and beyond, the algorithm that has been developed by Harvey and collaborator Joris van der Hoeven at École Polytechnique in France; can solve the problems much quicker than the 1971 Schönhage-Strassen algorithm. Harvey said, ‘It means you can do all sorts of arithmetic more efficiently, for example, division, and square roots. You could also calculate the digits of pi more efficiently than before. It even has applications to problems involving huge prime numbers. People have been hunting for such an algorithm for almost 50 years.’
