Generated by Codex with GPT 5.6 Sol High

The hidden cost of an elementary operation

Multiplication feels settled because children learn a dependable method for it: stack two numbers, multiply every digit of one by every digit of the other, then add the shifted partial products. For two numbers with n digits, however, that familiar algorithm requires work that grows roughly as n squared. Doubling the length of the inputs means about four times as many single-digit multiplications; multiplying two 1,000-digit numbers takes about one million of them.

Computer scientists care about this growth rate more than the speed of any particular machine. Hardware changes, but the number of steps an algorithm needs reveals how it will behave as the inputs become enormous. In big O notation, the grade-school method runs in O(n²) time. Multiplication underlies encryption, robotics, artificial intelligence and nearly every other form of computation, so even a small improvement can matter when computers repeat it at vast scale.

For centuries mathematicians assumed that the quadratic workload was unavoidable. Soviet mathematician Andrey Kolmogorov turned that belief into a formal conjecture during a 1960 seminar at Moscow State University. Anatoly Karatsuba, then a 23-year-old student in the audience, disproved it within a week. Kolmogorov was so impressed that he wrote up the proof himself, named Karatsuba as lead author and submitted it for publication. Karatsuba learned about the paper only when the reprints arrived.

Trading multiplication for addition

Karatsuba’s key insight was that a calculation can use fewer expensive multiplications if it performs some extra additions and subtractions. Take 12 × 34. Split the numbers into tens and ones, so 12 = 10a + b and 34 = 10c + d, where a = 1, b = 2, c = 3 and d = 4. Expanding the product gives:

100(ac) + 10(ad + bc) + bd.

The obvious route computes the four products ac, ad, bc and bd. Karatsuba noticed that after calculating ac and bd, the middle term can be recovered with only one more multiplication:

(ad + bc) = [(a + b) × (c + d)] − ac − bd.

For 12 × 34, the bracketed multiplication is 3 × 7. Subtracting 3 and 8 leaves 10 for the middle term, and the full expression becomes 300 + 100 + 8 = 408. Using three multiplications instead of four looks like a tiny gain, especially because the procedure adds several sums and subtractions. The advantage emerges through recursion.

For 1,234 × 5,678, each number can be split into two-digit halves. The same trick reduces four two-digit multiplications to three. Each of those can then be split and reduced again, continuing until only single-digit operations remain. The savings compound at every level. Karatsuba’s algorithm runs in roughly O(n^1.585) time, far better than O(n²). For two 1,000-digit inputs, that means fewer than 57,000 single-digit multiplications instead of one million.

The method is not automatically faster for small numbers. Splitting and recombining inputs creates overhead, so practical software mixes algorithms. Python uses the grade-school method for modest integers and changes strategies once the inputs become large enough; on most modern machines, the documented cutoff corresponds to roughly 630 decimal digits. Karatsuba’s idea is therefore not merely theoretical. It is embedded in ordinary software.

Nearing the apparent speed limit

Karatsuba’s discovery started a decades-long race. In 2019 David Harvey and Joris van der Hoeven described an algorithm that multiplies n-digit numbers in O(n × log n) time. Because the logarithm grows very slowly, this is only slightly more work than the O(n) steps needed simply to read the input digits. In an asymptotic sense, multiplication had come remarkably close to the lowest plausible cost.

There is a catch: the 2019 method wins only for numbers so enormous that it is considered a “galactic algorithm”—impressive at a scale unlikely to arise in practice. Karatsuba’s earlier technique remains more useful for the merely huge integers real computers encounter.

The deeper question is still open. Theoretical computer scientists widely suspect that O(n × log n) is the fastest multiplication can ever be, but no proof establishes that lower bound. The history of the subject makes confidence especially risky: the last supposedly obvious speed limit survived for millennia, then fell to a student in a week. Fast multiplication is therefore both a practical achievement and a reminder that consensus, however durable, is not proof.