In less than a week, Karatsuba found a faster way to multiply large numbers than long multiplication, disproving Kolmogorov’s conjecture

In the autumn of 1960, Andrey Kolmogorov, one of the great mathematicians of the 20th century, stated a conjecture about multiplication at a seminar he led at Moscow State University. Multiplying two n-digit numbers, he conjectured, takes on the order of n² steps, as long multiplication does, and no method can do fundamentally better. In less than a week, Anatoly Karatsuba, a 23-year-old mathematics student, found a method that did — the one now called the Karatsuba algorithm.

By his own account, Karatsuba was working toward a lower bound — a proof that multiplication must take at least a certain number of steps, the kind of limit Kolmogorov had conjectured. The algorithm he planned to use for that proof turned out to need only about n^1.58 steps. He took the result to Kolmogorov.

Kolmogorov “was very agitated because this contradicted his very plausible conjecture,” Karatsuba recalled in 1995. At the seminar’s next meeting, Kolmogorov himself told the participants about the method, “and at this point the seminar ended.”

Today the algorithm runs inside the standard implementation of Python whenever two large enough integers are multiplied. It was also the first of a series of faster multiplication methods, a line of work that reached a milestone in 2019.

What Kolmogorov’s n² conjecture said

Long multiplication multiplies every digit of one number by every digit of the other. Two four-digit numbers need 16 single-digit products, and doubling the length of both numbers quadruples the work. Kolmogorov’s conjecture said that every method would show the same n² growth.

Kolmogorov may have made the conjecture before 1960. David Harvey, one of the two mathematicians behind the 2019 result, writes that Kolmogorov conjectured it “around 1956”; Karatsuba’s account has Kolmogorov stating it at the 1960 seminar. The details of that week, including Kolmogorov’s agitation and the seminar’s end, come from Karatsuba’s own account, published 35 years later.

Three multiplications instead of four

Karatsuba’s trick fits in a two-digit example. To multiply 12 by 34, long multiplication needs four single-digit products: 1 × 3, 1 × 4, 2 × 3 and 2 × 4. Karatsuba’s method needs three:

1 × 3 = 3, the product of the first digits;
2 × 4 = 8, the product of the last digits;
(1 + 2) × (3 + 4) = 3 × 7 = 21, the product of the two digit sums.

Subtracting the first two products from the third leaves 21 − 3 − 8 = 10, which is exactly the middle term, 1 × 4 + 2 × 3. The answer then assembles from the pieces: 3 hundreds, 10 tens and 8 ones, or 300 + 100 + 8 = 408.

Saving one product out of four looks trivial at two digits. The trick matters because the same split works on long numbers. Cut each number into a high half and a low half, and the three products become multiplications of half-length numbers, each of which can be split the same way again.

On long numbers, the extra additions and subtractions are cheap next to the multiplications they save. By Harvey’s count, four-digit numbers need nine single-digit multiplications instead of 16, and for thousand-digit numbers the saving reaches a factor of about 17. Doubling the length of both numbers triples the single-digit multiplications instead of quadrupling them, so the cost grows like n raised to the power log₂ 3, about 1.58, instead of n².

Who wrote the 1962 Karatsuba–Ofman paper

The method appeared in 1962 in Doklady Akademii Nauk SSSR, the proceedings of the Soviet Academy of Sciences, under a Russian title that translates as “Multiplication of Many-Digital Numbers by Automatic Computers.” The byline read A. Karatsuba and Yu. Ofman.

According to accounts that draw on Karatsuba’s 1995 recollections, Kolmogorov wrote the paper himself. It contained two separate results on multiplication — Karatsuba’s algorithm and one by Yuri Ofman — and Karatsuba learned of the paper only when he received the reprints from the publisher. Some papers still call the method the Karatsuba–Ofman algorithm, but in these accounts the three-multiplication trick was Karatsuba’s.

What came after the Karatsuba algorithm

Once n² had fallen, others pushed further. Andrei Toom in 1963 and Stephen Cook in his 1966 Harvard thesis generalized the split from two pieces to more, a family now called Toom–Cook multiplication. In 1971, Arnold Schönhage and Volker Strassen used the fast Fourier transform to reach n × log n × log(log n) steps, and conjectured that n × log n should be possible.

Harvey and Joris van der Hoeven announced an n × log n algorithm on March 18, 2019, and it was published in the Annals of Mathematics in 2021. Harvey wrote that the proof “only works for ludicrously large numbers.”

Where the Karatsuba algorithm runs today

Karatsuba’s method sits in the integer code of widely used languages, behind a cutoff. The source of CPython, the standard implementation of Python, says it uses “the O(N**2) school algorithm unless both operands contain more than KARATSUBA_CUTOFF digits,” and sets that cutoff at 70 of its internal digits.

Java’s BigInteger class, which handles integers far larger than Java’s built-in integer types, has used Karatsuba since Java 8. It keeps long multiplication when either number is shorter than 80 words of 32 bits, uses Karatsuba when both are at least 80 and both are under 240, and switches to three-way Toom–Cook beyond that. The threshold of 80, its comment says, “is found experimentally to work well,” and the code describes Karatsuba as “more efficient for large numbers” than long multiplication. For short numbers, both languages keep the old method, because Karatsuba “has some overhead,” as the Java code notes.

What the n² conjecture shows about unproved limits

Kolmogorov’s conjecture was, in Karatsuba’s words, very plausible. As Harvey puts it, “Kolmogorov felt that if a short cut was possible, surely it would have already been discovered.” What the conjecture lacked was a proof that no other method could do better, and the attempt to supply such a proof is where Karatsuba found the faster method.

The trick itself is a reusable pattern: when one operation dominates the cost, an algebraic identity can trade it for cheaper ones. Karatsuba spent a few additions to save a multiplication, and the saving compounded at every level of the split.

A limit that has only been observed, not proved, describes the methods people have tried so far, not every method that could exist.

Kolmogorov’s seminar ended at the meeting where he presented the method. The method did not: more than six decades later, CPython still switches to Karatsuba’s split once both numbers pass 70 of its internal digits.

Explore

Stay connected