Elementary students can memorize their multiplication tables for single-digit numbers, but memorization won’t be enough when the teacher asks for three-digit multiplication. This requires an algorithm: students learn to stack one number on top of another and multiply each digit of the bottom number by each digit of the top number. For millennia, mathematicians believed it to be the fastest method of multiplication, until a 23-year-old made a shocking discovery in 1960, which led to a mystery that remains unsolved to this day.
This mystery is essential for anyone participating in the digital world, because multiplication is a fundamental operation for computers. Encryptionrobotics, artificial intelligenceaudio processing and just about everything else we do silicon chips with involves multiplication, sometimes of huge numbers several times. At this scale, even a single operation becomes a bottleneck, and any efficiency gains have global economic consequences.
To understand the nature of this bottleneck, look at how the elementary school algorithm handles growth. When you multiply two two-digit numbers, you perform four single-digit multiplications. If you increase this to a pair of three-digit numbers, you perform nine single-digit multiplications. The workload changes with the square of the number of digits (n2Or n is the number of digits in the multiplied numbers). When analyzing an algorithm like this, computer scientists don’t measure the speed in seconds, because that depends on the hardware. Instead, they count the calculation steps. They also ignore minor details of accounting, such as the time it takes to complete one when multiplying. When the numbers get large enough, these lower-level operations cease to matter, entirely eclipsed by the more intensive operations involved. Computer scientists note the number of steps using what is called Big O notation: the elementary school algorithm, for example, takes O(n2) steps, which reads like “command n ” Generally speaking, if the numbers are twice as long, it requires four times as much computational work to run the algorithm. If the numbers are a thousand times as long, it requires a million (1,000 squared) times more work.
On supporting science journalism
If you enjoy this article, please consider supporting our award-winning journalism by subscribe. By purchasing a subscription, you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
Since ancient times, mathematicians have suspected that O(n2) was a speed limit inherent to multiplication. The famous Soviet mathematics professor Andrei Kolmogorov posed the O(n^2) speed limit as a formal conjecture and mentioned it in a 1960 seminar at Moscow State University. Whenever mathematicians come up with a conjecture, they plant a sort of flag and wait for others to prove or disprove it. It took only a week for Anatoly Karatsuba, then a 23-year-old student in the audience, to return and prove Kolmogorov wrong. Kolmogorov was stunned. The result was published in the prestigious Proceedings of the USSR Academy of Sciencesbut oddly enough, Karatsuba didn’t write it. Kolmogorov wrote the formal proof himself and submitted it for publication with Karatsuba listed as the primary author. Karatsuba only discovered the journal’s existence after receiving the reprints in the mail.
Karatsuba’s genius understood that it was possible to exchange expensive and tedious multiplications for quick and cheap additions. By adding two n-digit numbers only take O(n) time because this involves a single scan of the digits rather than a full scan of the top number For each number of the bottom number, as in multiplication. To see how Karatsuba swapped multiplication for addition, let’s look at a small example. The method would be too complicated for such a simple problem, but it saves a lot of time when the numbers increase.
In this simple example, let’s calculate 12 × 34.
First, we divide the two numbers into tens and ones digits. Assign A = 1 and b = 2 (for 12), and c = 3 and d = 4 (for 34). Algebraically, we can rewrite 12 × 34 as (10A + b) × (10c + d).
Expanding this, we get 100(That) + 10(announcement + BC) + (comic).
To solve the equation in the traditional way, you must perform four distinct multiplications: That = 3, announcement = 4, BC = 6 and comic = 8, which is exactly what the stacking method implies in elementary school. (Note that we do not count multiplications by 100 or by 10 because these only involve inserting zeros at the end of numbers.) Karatsuba noticed a brilliant algebraic trick. Once you have calculated the first and last term, That And comicyou can understand this damn middle term (announcement + BC) with A more multiplication steps instead of two. You don’t need to calculate announcement And BC individually:
(announcement + BC) = ((A + b) × (c + d)) – That – bd,
Or with our concrete figures:
((1 × 4) + (2 × 3)) = ((1 + 2) × (3 + 4)) – 3 – 8 = 10.
Pause to notice the strangeness of the equation above. This suggests that to quickly multiply 12 × 34, you need to add the 1 and 2 in 12 and the 3 and 4 in 34. This is not a natural thing to do. No wonder it took so long for anyone to realize it. But this ends up reducing the workload: because we have already calculated That And bd, the right side contains only one more multiplication, plus some additions and subtractions.
Returning to 100(That) + 10(announcement + BC) + (comic), we only need three multiplications instead of four. We calculate That And comic in a simple way, then use Karatsuba’s trick to calculate (announcement + BC) with a single multiplication. Connection That = 3, comic = 8 and (announcement + BC) = 10 gives our answer of 408.
We have removed a multiplication from the procedure. If that seems insignificant, Karatsuba has another idea in store. Suppose we multiply larger numbers: 1234 × 5678. We divide them in half as we did before: A = 12, b = 34, c = 56 and d = 78, and we write the problem as (100A + b) × (100c + d) = 10,000(That) + 100(announcement + BC) + (comic).
We can solve this problem with three multiplications. Those however, multiplications now involve two-digit numbers. Luckily, we know a way to multiply two-digit numbers with just three single-digit multiplications each! In total, a problem that would require 16 single-digit multiplications the traditional way now only requires nine. By recursively applying Karatsuba’s trick to large numbers, the savings accumulate. It divides the entered numbers in half, then divides those halves in half, and so on, applying this four-for-three swap all the way down. The algorithm works to have a running time of approximately O(n1,585), which is considerably faster than O(n2). For reference, multiplying a pair of thousand-digit numbers involves a million single-digit multiplications using the elementary school method, but fewer than 57,000 using the Karatsuba algorithm.
The 23-year-old’s efficiency is built into software that runs daily. Due to its additional overhead (the additions, handling repeated division and recombination of numbers, etc.), its advantages over the elementary school algorithm only become apparent when the numbers become relatively large. Pythonfor example, is a popular programming language known for easily handling integers of all sizes. If you take a look at the underlying Python source code (search for “Karatsuba” here), you will see that it is based on a hybrid approach. For modestly sized inputs, it uses elementary school math, but once the numbers reach about 630 decimal digits, it flips a switch and uses the Karatsuba algorithm. This number of digits may seem gargantuan by Earth standards, but computers manage much bigger. (Technical side: on most modern machines Python stores large numbers in base 230therefore the Karatsuba threshold linked to 70 digits in base 230 translates to approximately 630 decimal digits).
Karatsuba’s algorithm sparked a decades-long race to find the ultimate speed limit of multiplication. This quest culminated in 2019, when mathematicians David Harvey and Joris van der Hoeven describes an extremely sophisticated algorithm which beat Karatsuba’s more than any of the previous breakthroughs. The new algorithm runs in O(n × newspaper n) time. Here, log denotes the logarithm of nwhich is a function that grows very slowly. This is a stunning result. The function n × newspaper n is just a little bigger than n himself. This means that calculating the product of two massive numbers requires only a little more time than adding them, or even while reading them, would be in the first place (it is necessary n calculation steps to read everything n digits of a number).
This triumph, however, comes with a crucial caveat. Just as the Karatsuba algorithm only outperforms the elementary school approach when the numbers become reasonably large, the Harvey-van der Hoeven algorithm does not advance until the numbers become truly galactic. In computing, a “galactic algorithmis a formal term for a method that is incredibly effective on sufficiently large numbers, but will never be useful in practice because the numbers are so large.
Even with that asterisk, it was a watershed moment. He obtained in principle the record of the multiplication method n known fastest and could open the way to algorithms operating in O(n × newspaper n), not only in principle, but also in practice. Today, theoretical computer scientists widely suspect that O(n × newspaper n) is the fastest multiplication speed possible, and formally prove that it has become the Holy Grail for this niche area of mathematics. But as history reminds us, widespread consensus is not mathematical proof. Conjectures about the speed limit of multiplication have already been overturned.
