Mathematics & Computer Science
The Multiplication Problem: Why the Fastest Way to Multiply Still Eludes Mathematicians
A twenty-three-year-old student in 1960 shattered an ancient assumption about one of the simplest operations in math. Six decades later, nobody still knows where the true speed limit lies.
- The grade-school "stack and multiply" method needs O(n²) steps, where n is the number of digits — so doubling the numbers quadruples the work.
- At scales used by encryption, AI training and scientific simulation, even a small improvement in multiplication efficiency has massive real-world consequences.
- Theoretical computer scientists now suspect the ultimate limit is O(n log n), but that remains an unproven conjecture — and history shows consensus has been wrong before.
Multiply a two-digit number by another and it takes four single-digit multiplications. Bump up to three digits and the count becomes nine. To four digits, sixteen. Every time you add a digit to each number, the workload grows with the square of the number of digits. For thousands of years, mathematicians assumed this was simply how multiplication was built — an unavoidable speed limit.
That assumption lasted until a single moment at Moscow State University. In 1960, the celebrated mathematician Andrey Kolmogorov proposed O(n²) as a formal conjecture during a seminar and challenged his audience to prove or disprove it. Within a week, a 23-year-old student in the room, Anatoly Karatsuba, came back with the disproof.
Karatsuba's insight was elegantly counterintuitive: you can cut the number of heavy multiplications by paying instead in cheap additions. Adding two n-digit numbers is a single linear pass — O(n) work. Multiplication, by contrast, was thought to be inherently quadratic. Karatsuba showed that by splitting each number in half and using a clever algebraic identity, three multiplications can replace the four the grade-school method demands. Repeated recursively, this shaves the complexity to roughly O(n1.585).
That single trick opened a sixty-year relay race. In 1969 Volker Strassen applied a related divide-and-conquer idea to matrix multiplication, proving two n×n matrices could be multiplied with seven block multiplications instead of eight, lowering the matrix-multiplication exponent. In 1987 Don Coppersmith and Shmuel Winograd pushed the bound further, bringing the best known complexity for multiplying matrices down to roughly n2.3755 — a figure that has crept lower ever since, down to about 2.37 in the most recent work.
For ordinary integer multiplication the race culminated in 2019, when David Harvey and Joris van der Hoeven announced an algorithm running in O(n log n) time. At a glance that looks like the finish line. In practice, it is a "galactic algorithm" — a formal computer-science term for a method that is unbeatable on sufficiently large numbers but will never be used in any real program, because the numbers at which it wins are so vast they have no business existing.
That caveat is the heart of the mystery. The theoretical limit and the practical limit are not the same thing. Modern chips already use Karatsuba's idea and refinements of it well before numbers get large enough for the O(n log n) method to matter. So the everyday speed of every encryption key, every AI weight update, and every scientific calculation still rides on the sixty-five-year-old insight of a young student in Moscow.
The broader lesson is how deceptively simple fundamental operations can be. Multiplication feels elementary. It is also the engine under every layer of modern computation. Finding its true speed limit would settle a deep question about how efficiently the universe of numbers can be processed — and it may, in the end, be just out of reach.
Knowledge takeaway: The grade-school multiplication method scales as the square of the digit count (O(n²)); Karatsuba's 1960 trick cuts steps by trading multiplications for additions; and the 2019 O(n log n) algorithm is "galactic" — theoretically optimal but never practically useful.