A 23-year-old student needed one week to beat schoolbook multiplication
In 1960 Andrey Kolmogorov told a Moscow seminar he believed long multiplication was as fast as multiplying could ever get. Within a week, Anatoly Karatsuba, a 23-year-old student, proved him wrong with a trick that replaces four smaller multiplications with three, and repeats the saving all the way down.
Schoolbook multiplication of two n-digit numbers takes work proportional to n squared, and Kolmogorov conjectured that nothing could do asymptotically better. Split each number into a high half and a low half, though, and the product becomes three pieces: high times high, low times low, and a cross term mixing the two. Computing those naively takes four multiplications, a scheme Charles Babbage already knew. Karatsuba's insight was that the cross term equals the product of the two half-sums minus the other two pieces, so three multiplications suffice, paid for with a few extra additions and subtractions.
Take 12345 times 6789 with the numbers split in base 1000. The high parts multiply to 72 and the low parts, 345 and 789, to 272205. Then 357 times 795 gives 283815, and subtracting both earlier results leaves 11538 for the middle term. Shifting and adding the three pieces yields 83810205. Because the smaller products can themselves be split the same way, recursion drives the count of single-digit multiplications down to roughly n raised to 1.58 instead of n squared. The additions and shifts grow only linearly, so their cost fades for large inputs.
Kolmogorov was thrilled, announced the result at the next session and then closed the seminar. He lectured on it internationally, including at the 1962 International Congress of Mathematicians in Stockholm, and wrote it up that year in the Proceedings of the USSR Academy of Sciences, together with a separate result by Yuri Ofman, listing both young men as authors. Karatsuba learned of the paper only when reprints arrived in the post.
It was the first method known to beat the quadratic approach. The Toom–Cook algorithm of 1963 generalised it, and the Schönhage–Strassen method of 1971 goes faster still for very large numbers. On hardware with a 32-bit multiplier, choosing a base of 2 to the 31st keeps the half-sums from overflowing, letting the recursion run down to single digits.
Source: Karatsuba algorithm
