🔗 Karatsuba Algorithm

🔗 Computing 🔗 Mathematics 🔗 Computing/Software 🔗 Computing/Computer science

The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It reduces the multiplication of two n-digit numbers to at most ${\displaystyle n^{\log _{2}3}\approx n^{1.58}}$ single-digit multiplications in general (and exactly ${\displaystyle n^{\log _{2}3}}$ when n is a power of 2). It is therefore faster than the classical algorithm, which requires ${\displaystyle n^{2}}$ single-digit products. For example, the Karatsuba algorithm requires 3¹⁰ = 59,049 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 2¹⁰), whereas the classical algorithm requires (2¹⁰)² = 1,048,576 (a speedup of 17.75 times).

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.