Mathematics & Computer Science

Why Nobody Knows the Fastest Way to Multiply

The grade-school way to multiply two n-digit numbers needs roughly n² single-digit steps. For two thousand years that was assumed to be the limit. It wasn't — but finding the true floor has proven far harder than anyone expected.

• In 1960, Andrey Kolmogorov formally conjectured at Moscow State University that O(n²) was multiplication's unbreakable speed limit.
• At 23, Anatoly Karatsuba proved him wrong the same year, cutting 12 × 34 from four small multiplications to three by trading multiplications for cheap additions.
• In 2019, David Harvey and Joris van der Hoeven set today's record at O(n log n) — theoretically the likely end of the line.

The trick Karatsuba discovered is almost a parlor move once you see it. Multiplying 12 × 34 the traditional way means four products: 1×3, 1×4, 2×3 and 2×4. Karatsuba noticed that the middle term can be rebuilt from a single extra product — multiply (1+2) × (3+4) once, then subtract the two ends. The job shrinks from four multiplications to three. It feels almost like cheating, which is exactly why nobody thought of it for centuries.

The beauty is that the trick is recursive. To multiply 1,234 × 5,678, split each number in half and apply the same three-multiplication recipe. The problems inside are themselves two-digit numbers, so they too get solved with three small products. A problem that would cost 16 single-digit multiplications the old way now costs just 9. Re-split, recurse, and the exponent on n drops from 2 to about 1.585. Python uses this same idea — under a certain size the overhead of all the splitting and recombining isn't worth it, but as numbers grow it quietly becomes the faster path.

Karatsuba started a decades-long chase to the ultimate floor. Strassen and others kept chipping away, until Harvey and van der Hoeven finally reached O(n log n) in 2019. The catch: it is a "galactic algorithm" in the computer-science sense — it only beats its predecessors when the numbers become so enormous they would not fit in any practical computer. It is right in principle, not in practice. Theorists now widely believe O(n log n) is the true speed limit, but proving it is the open problem that has kept the record officially provisional for six decades.

Knowledge takeaway: Multiplication was long thought to cost O(n²) steps. Karatsuba's 1960 three-multiplication trick started a race that led to an O(n log n) record in 2019 — but that record wins only for absurdly huge numbers, and the proof that nothing faster is possible remains one of computer science's open questions.