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.

Weird ways to calculate pi