The Fastest Way to Multiply? Still Unknown, But We Keep Getting Closer

Multiplication is everywhere in computing — encryption, AI, audio processing, you name it. And for decades, mathematicians thought the grade-school stacking algorithm (O(n²)) was the fastest possible. Then a 23-year-old student shattered that belief, sparking a race that continues today.

The Grade-School Bottleneck

The classic algorithm multiplies every digit of one number by every digit of the other. Doubling the digit count quadruples the work — O(n²). For thousand-digit numbers, that's a million single-digit multiplications. Acceptable for small numbers, but a nightmare at scale.

Karatsuba's Trick: Trade Multiplications for Additions

In 1960, Anatoly Karatsuba realized you could replace some multiplications with cheaper additions. For two-digit numbers, instead of four multiplications you need only three, plus a few adds. Recursively applied, this drops complexity to O(n^1.585). Python uses this today for numbers above ~630 decimal digits.

The Harvey–van der Hoeven Algorithm

In 2019, David Harvey and Joris van der Hoeven published an algorithm running in O(n log n) — nearly as fast as just reading the numbers. But there's a catch: it only beats Karatsuba for numbers so astronomically large they'll never appear in practice. It's a galactic algorithm: theoretically beautiful, practically irrelevant.

What's Next?

The O(n log n) bound is tantalizingly close to optimal, but no one has proven it's the floor. The question remains open — and every new insight pushes the limits of what computers can do efficiently.