Its discovery is quite legendary. It was the first multiplication algorithm faster than long multiplication known to humans. Before 1960, few people thought it

Its discovery is quite legendary. It was the first multiplication algorithm faster than long multiplication known to humans. Before 1960, few people thought it was possible to do it faster than O(n^2). Even one of the best mathematician in the 20th century, Kolmogorov, believed the long multiplication is probably asymptotically optimal in 1955, and asked people to try proving this conjecture in a 1960 conference. And within a week, his student Karatsuba found this algorithm. It's also one of the earliest divide-and-conquer algorithms discovered in computer science. Since then, faster and faster algorithms have been discovered. Although in practice, the ALU itself is almost never the bottleneck of computation on a modern computer. The setup cost of these algorithms is often greater, making them only useful for bignum (Karatsuba is only faster for number longer than a few hundreds of decimal digits?) It also explains why faster algorithms haven't been discovered in the last 2000 years. --- The historical review paper by Karatsuba * The Complexity of Computations http://www.ccas.ru/personal/karatsuba/divcen.pdf http://www.ccas.ru/personal/karatsuba/divcen.pdf