For two 1-billion-digit numbers, Karatsuba’s method would require about 165 trillion additional steps. Then in 1971 Arnold Schönhage and Volker Strassen published a method capable of multiplying large numbers in n × log n × log(log n) multiplicative steps, where log n is the logarithm of n. Karatsuba’s method made it possible to multiply numbers using only n 1.58 single-digit multiplications. “You can turn some of the multiplications into additions, and the idea is additions will be faster for computers,” said David Harvey, a mathematician at the University of New South Wales and a co-author on the new paper. And with each splitting, you replace multiplications that require many steps to compute with additions and subtractions that require far fewer. When dealing with large numbers, you can repeat the Karatsuba procedure, splitting the original number into almost as many parts as it has digits. “With addition, you do it a year earlier in school because it’s much easier, you can do it in linear time, almost as fast as reading the numbers from right to left,” said Martin Fürer, a mathematician at Pennsylvania State University who in 2007 created what was at the time the fastest multiplication algorithm. The method saves time because addition takes only 2 n steps, as opposed to n 2 steps. Karatsuba’s method involves breaking up the digits of a number and recombining them in a novel way that allows you to substitute a small number of additions and subtractions for a large number of multiplications. Karatsuba thought there was - and after a week of searching, he found it. Kolmogorov asserted that there was no general procedure for doing multiplication that required fewer than n 2 steps. Then in 1960, the 23-year-old Russian mathematician Anatoly Karatsuba took a seminar led by Andrey Kolmogorov, one of the great mathematicians of the 20th century. To multiply two numbers with 1 billion digits requires 1 billion squared, or 10 18, multiplications, which would take a modern computer roughly 30 years.įor millennia it was widely assumed that there was no faster way to multiply.
The carrying method works well for numbers with just a few digits, but it bogs down when we’re multiplying numbers with millions or billions of digits (which is what computers do to accurately calculate pi or as part of the worldwide search for large primes). So three-digit numbers require nine multiplications, while 100-digit numbers require 10,000 multiplications. The grade school or “carrying” method requires about n 2 steps, where n is the number of digits of each of the numbers you’re multiplying. If you’re multiplying two two-digit numbers, you end up performing four smaller multiplications to produce a final product. We stack two numbers, multiply every digit in the bottom number by every digit in the top number, and do addition at the end. Most everyone learns to multiply the same way. “If you want to know how fast computers can solve certain mathematical problems, then integer multiplication pops up as some kind of basic building brick with respect to which you can express those kinds of speeds.” “In physics you have important constants like the speed of light which allow you to describe all kinds of phenomena,” van der Hoeven said. Van der Hoeven describes their result as setting a kind of mathematical speed limit for how fast many other kinds of problems can be solved. The complexity of many computational problems, from calculating new digits of pi to finding large prime numbers, boils down to the speed of multiplication.
“Everybody thinks basically that the method you learn in school is the best one, but in fact it’s an active area of research,” said Joris van der Hoeven, a mathematician at the French National Center for Scientific Research and one of the co-authors. The paper marks the culmination of a long-running search to find the most efficient procedure for performing one of the most basic operations in math. On March 18, two researchers described the fastest method ever discovered for multiplying two very large numbers. Four thousand years ago, the Babylonians invented multiplication.
0 kommentar(er)
