Karatsuba algorithm

The Karatsuba algorithm is a fast <a href="/facts/Multiplication_algorithm/68xf6EdK">multiplication algorithm</a>. It was discovered by <a href="/facts/Anatoly_Karatsuba/QbbUpfne">Anatoly Karatsuba</a> in 1960 and published in 1962. It is a <a href="/facts/Divide-and-conquer_algorithm/pC1X7Ws7">divide-and-conquer algorithm</a> 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 
 
 
 
 
 n
 
 
 log
 
 2
 
 
 ⁡
 3
 
 
 ≈
 
 n
 
 1.58
 
 
 
 
 {\displaystyle n^{\log _{2}3}\approx n^{1.58}}
 
 single-digit multiplications. It is therefore <a href="/facts/Asymptotic_complexity/etHuVF3U">asymptotically faster</a> than the <a href="/facts/Long_multiplication/68xf6EdK">traditional</a> algorithm, which performs 
 
 
 
 
 n
 
 2
 
 
 
 
 {\displaystyle n^{2}}
 
 single-digit products.
The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm.
The <a href="/facts/Toom%E2%80%93Cook_multiplication/5AuKo2IJ">Toom–Cook algorithm</a> (1963) is a faster generalization of Karatsuba's method, and the <a href="/facts/Sch%C3%B6nhage%E2%80%93Strassen_algorithm/7dLGaI4d">Schönhage–Strassen algorithm</a> (1971) is even faster, for sufficiently large n.

Karatsuba algorithm open-in-new

Karatsuba algorithm