Karatsuba算法

Karatsuba算法是一种快速相乘算法，它由Anatolii Alexeevitch Karatsuba于1960年提出并于1962年发表。[1][2][3]它将两个${\displaystyle n}$位数字相乘所需的一位数乘法次数减少到了至多${\displaystyle 3n^{\log _{2}3}\approx 3n^{1.585}}$（如果${\displaystyle n}$是2的乘方，则正好为${\displaystyle n^{\log _{2}3}}$）。因此它比要${\displaystyle n^{2}}$次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（${\displaystyle n=1024=2^{10}}$），Karatsuba算法需要${\displaystyle 3^{10}=59049}$次个位数乘法，而经典算法需要${\displaystyle (2^{10})^{2}=1048576}$次。Toom–Cook算法是此算法更快速的泛型。对于充分大的${\displaystyle n(n\gg 1)}$,Schönhage–Strassen算法甚至更快，算法的时间复杂度为${\displaystyle O(n\log n\log \log n)}$。

值得一提的是，Karatsuba算法是第一个比小学二次乘法算法渐进快速的算法。