Karatsuba Algorithm

The Karatsuba algorithm is a fast multiplication algorithm. It was invented by Anatolii Alexeevitch Karatsuba in 1960 and published in 1962. It reduces the multiplication of two n-digit numbers to at most single-digit multiplications in general (and exactly when n is a power of 2). It is therefore faster than the classical algorithm, which requires n2 single-digit products. If n = 210 = 1024, in particular, the exact counts are 310 = 59,049 and (210)2 = 1,048,576, respectively. The Toom–Cook algorithm is a faster generalization of this algorithm. For sufficiently large n, another generalization, the Schönhage–Strassen algorithm, is even faster.

The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm.