Karatsuba algorithm

The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962.^[1][2][3] It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most ${\displaystyle n^{\log _{2}3}\approx n^{1.58}}$ single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs ${\displaystyle n^{2}}$ single-digit products.

The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. The Toom–Cook algorithm (1963) is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm (1971) is even faster, for sufficiently large n.