Karatsuba 乘法是一种快速的乘法算法，它是由 Anatolii Alexeevitch Karatsuba 在 1960 年发现，并且在 1962 年公开发表的算法。 传统的高精度乘法复杂度会达到 $n^2$，而 Karatsuba 乘法则是基于分治策略，复杂度是 $3n^{\log_23}$，近似值大约为 $3n^{1.585}$。

首先，假设在 $B$ 进制下有两个大整数 $a, b$，现在我们要计算 $a\cdot b$ 我们可以将其写成 $$ a=a_0\cdot B^m + a_1 \\ b=b_0\cdot B^m + b_1 $$ 其中 $m$ 是最小的正整数使得 $a_0, a_1, b_0, b_1 < B^m$，也就是把 $a, b$ 切成了均匀两半，之后注意到

\[\begin{eqnarray*} &&a\cdot b\\ &=&(a_0B^m + a_1)(b_0B^m + b_1)\\ &=&a_0b_0B^{2m}+(a_0b_1+b_0a_1)B^m+a_1b_1\\ &=&a_0b_0B^{2m}+(a_0+a_1)(b_0+b_1)B^m-(a_0b_0+a_1b_1)B^m+a_1b_1 \end{eqnarray*}\]

到了最后一步，我们发现只需要计算三次乘法 $a_0b_0, a_1b_1, (a_0+a_1)(b_0+b_1)$ 以及六次加法。这样复杂度就变为 $$ T(n) = 3T(\frac{n}{2}) + 6n = O(n^{\log_23}) $$ 当然这个方法也可以用来计算多项式乘法，你只要认为 $B$ 是多项式的形式变量就好了（而且还不用像高精度那样写个加减进位退位似乎更好写）

本文遵守 CC BY-NC 4.0 许可协议。