Karatsuba Algorithm: The 1960 Discovery That Revolutionized Math

The School Method Everyone Thought Was Perfect

Every elementary school student knows the ritual: write one number beneath the other, draw a line, and multiply each digit of the bottom number by each digit of the top number. For two 2-digit numbers, that means 4 single-digit multiplications. Move up to two 3-digit numbers, and suddenly you're doing 9 of them.

This is the method that mathematicians from Antiquity onward believed was unbeatable for multiplication. The workload grows with the square of the digit count, which computer scientists express in Big O notation as O(n²), read as "n squared order." Double the number of digits, and the computation quadruples. Increase the digits a thousand-fold, and the work jumps by a million times.

For centuries, this seemed like an unbreakable mathematical law. The famous Soviet mathematician Andrey Kolmogorov even formalized this belief into an official conjecture, presenting it at a seminar at Moscow State University in 1960. He argued that no multiplication method could ever beat this n-squared barrier. The claim stood for exactly one week, until a 23-year-old student in the audience proved him wrong with what would become known as the Karatsuba algorithm.

A 23-Year-Old Shatters a Legend's Conjecture

In 1960, a 23-year-old student named Anatoly Karatsuba walked into a seminar at Moscow State University and heard something that would change his life. The speaker was Andrey Kolmogorov, one of the most celebrated Soviet mathematicians of the twentieth century. Kolmogorov stood before the room and declared that the traditional method of multiplication, which requires about n² operations for n-digit numbers, was the fastest possible. He framed this belief as an official conjecture, a formal challenge to the mathematical community.

Karatsuba sat in the audience and listened. He was young, just a student, but something about Kolmogorov's claim bothered him. Within about a week, he returned to Kolmogorov with a counterexample, a proof that the great mathematician was wrong. Kolmogorov was astonished. He wrote up the proof himself and submitted it to the journal of the Soviet Academy of Sciences, listing Karatsuba as the lead author. Karatsuba only learned the work had been published when the printed copies reached him.

That discovery, now known as the Karatsuba algorithm, opened a door that mathematicians had assumed was locked forever. It showed that multiplication could be done faster than anyone had believed possible, and it sparked a mystery that remains unsolved today: what is the true speed limit for multiplying two numbers?

How Karatsuba's Trick Actually Works

Karatsuba's breakthrough in 1960 came down to a surprisingly simple idea: swap some slow multiplications for faster additions. The classic schoolbook method for multiplying two two-digit numbers demands four separate single-digit multiplications. Karatsuba found a way to get the same answer with only three.

Let's walk through it with 12 × 34, the same example that illustrates the whole trick. Write the numbers as (10a + b) and (10c + d), where for 12 you have a = 1 and b = 2, and for 34 you have c = 3 and d = 4. Expand those parentheses using the distributive property and you get 100ac + 10(ad + bc) + bd.

The traditional route computes each piece separately: ac = 3, ad = 4, bc = 6, and bd = 8. That's four multiplications, and the final answer assembles as 100(3) + 10(4 + 6) + 8 = 408.

Here's where Karatsuba's algebraic insight kicks in. Instead of calculating ad and bc as two separate multiplications, he spotted that the middle term can be rewritten: ad + bc = (a + b)(c + d) − ac − bd. You already know ac and bd from the first and last terms, so you only need one extra multiplication, (a + b)(c + d), to get the middle piece. Four multiplications become three.

Substituting the values gives (1 + 2)(3 + 4) = 21, then subtract ac (3) and bd (8) to get 10. That matches the ad + bc = 4 + 6 = 10 from before. The full expression 100(3) + 10(10) + 8 still equals 408.

Saving one multiplication on a tiny example seems trivial. But the advantage compounds as numbers grow. For a four-digit pair, the schoolbook method needs 16 single-digit multiplications, while Karatsuba's approach completes the job with just nine.

That scaling difference is what makes the Karatsuba algorithm so powerful. Its complexity lands at roughly O(n^1.585), where the exponent is log₂(3). Compare that to the familiar O(n²) of traditional multiplication, and the gap becomes dramatic. For two 1000-digit numbers, the standard method requires about 1,000,000 single-digit multiplications. Karatsuba's method finishes in fewer than 57,000.

Where Karatsuba's Algorithm Lives Today

The Karatsuba algorithm isn't just a historical curiosity locked away in mathematics journals. It's working right now inside software you probably use every day. Python, the programming language that powers everything from data science to web applications, quietly switches between two multiplication strategies depending on how big the numbers get.

For small numbers, Python sticks with the traditional school method you learned in elementary school. The reason is simple: splitting numbers apart and then reassembling them takes time too. When you're multiplying 12 by 34, just doing the four straightforward multiplications is faster than trying to be clever about it. But when numbers grow enormous, something shifts. At that point, Python hands the job over to the Karatsuba algorithm, and the savings become dramatic.

Consider what happens with two 1,000-digit numbers. The old-fashioned approach demands roughly one million single-digit multiplications. Karatsuba's method completes the same task in fewer than 57,000 multiplications. That's not a small improvement. That's the difference between waiting and not waiting.

Yet the Karatsuba algorithm represents something bigger than any single piece of software. His 1960 discovery cracked open a door that mathematicians had assumed was permanently sealed. For thousands of years, the schoolbook method seemed like the final word on multiplication. Karatsuba proved otherwise, and suddenly the hunt was on for something even faster.

That search reached a milestone in 2019. David Harvey and Joris van der Hoeven unveiled a new algorithm that multiplies very large numbers faster than Karatsuba's method, with complexity of approximately O(n log n). It's a theoretical triumph, though one with a practical catch. This newer approach only gains an advantage with numbers so staggeringly large that they barely exist outside pure mathematics. Computer scientists call such methods "galactic algorithms" for good reason. They're magnificent in theory and nearly useless in everyday computation.

Still, the Karatsuba algorithm remains the workhorse that actually gets used. It sits inside Python's codebase, ready to spring into action when numbers grow too large for simple methods. And it stands as proof that a 23-year-old student could overturn what the greatest mathematical minds of antiquity had accepted as settled.

The Unsolved Mystery of Multiplication's True Speed Limit

So where does this leave us? In 2019, mathematicians David Harvey and Joris van der Hoeven published an algorithm that multiplies numbers in roughly O(n log n) time, the fastest method ever discovered. But here's the catch: it only beats everything else on numbers so staggeringly enormous that they're essentially beyond human comprehension.

Computer scientists have a name for methods like this: galactic algorithms. They're theoretically brilliant, mathematically elegant, and utterly useless for anything you'd actually compute in daily life. The overhead of setting up the algorithm's complex machinery dwarfs any savings until the numbers reach sizes that have no practical application whatsoever.

That's a strange place to find ourselves. The Karatsuba algorithm, born in 1960 when Anatoly Karatsuba was just 23 years old, remains the workhorse for large-number multiplication in many systems. Python, for instance, switches from the traditional schoolbook method to Karatsuba's approach when numbers grow beyond a certain size. But the 2019 breakthrough? It's a theoretical triumph that exists mostly on paper.

Here's what makes this genuinely tantalizing. Many researchers now suspect that O(n log n) might be the absolute floor for multiplication, the true speed limit written into the fabric of mathematics itself. The intuition is compelling: you have to look at every digit at least once, and there's a certain irreducible amount of work involved in combining what you've seen.

But suspicion isn't proof. No one has definitively demonstrated that O(n log n) is the best anyone can ever do. The gap between what mathematicians believe and what they can prove remains wide open.

Think about what that means. Multiplication is one of the most fundamental operations in all of computation, used billions of times every second in encryption, scientific computing, and countless other applications. And yet, the question of its true speed limit sits unresolved, a quiet mystery at the heart of mathematics.

Kolmogorov's conjecture fell in a week to a young student's insight. The 2019 algorithm pushed the boundary further than anyone thought possible. Whether the O(n log n) barrier represents a genuine wall or just another assumption waiting to be shattered, nobody knows. The answer, whatever it turns out to be, is still out there.