Communications of the ACM
This Guy Just Found a Faster Way to Multiply
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.
Credit: UNSW/YouTube
From grade school onward, complex multiplication has been a headache. But 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 the video below.
The Schönhage–Strassen algorithm, developed by two German mathematicians, was actually the fastest method of multiplication from 1971 through 2007. Although a faster method was developed in 2007, it's rarely used today.
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.
Harvey picks the example of 314 multiplied by 159—a large equation, sure, but much larger ones are used every day in real-life scenarios. To solve the problem, most people are taught to multiply each individual number together, and then add up the sums:
9 is multiplied by 4, 1, and 3; then 5 is multiplied by 4, 1, and 3, and so on. The result ends up with 9 digit-by-digit products.
This method is called n2 or n squared, because one must multiple n by n a number of times. It will get the correct answer, but Schönhage and Strassen designed a faster method. It was able to move beyond n2 and into something smaller, but a challenge still presented itself in the form of n * log(n).
For some, seeing a word in the middle of a math problem might be enough to make their eyes glaze over like they did in algebra class. As a refresher: log is short for logarithm, which helps people decipher exponents that make numbers squared or cubed or even something higher. So 2⁵ is 32, but expressed logarithmically, it would look like log₂(32)=5. While it may seem like a mouthful, logarithms are crucial when numbers get much larger.
From Popular Mechanics
View Full Article
No entries found