Karatsuba 乘法

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

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

$$\begin{array}{rcl}& & a\cdot b\\ & =& (a_0{B}^m+a_1)(b_0{B}^m+b_1)\\ & =& a_0{b}_0{B}^{2m}+(a_0{b}_1+b_0{a}_1)B^m+a_1{b}_1\\ & =& a_0{b}_0{B}^{2m}+(a_0+a_1)(b_0+b_1)B^m-(a_0{b}_0+a_1{b}_1)B^m+a_1{b}_1\end{array}$$

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