约定

现在要计算两个 $n$ 位二进制数 $a$ 和 $b$ 的乘积，这是为了方便描述，一下算法可以直接应用到任意进制的情况。

我们的计算机每次仅可以对一位二进制位进行操作，我们的复杂度也是在这样的机器上进行计算的。

Karatsuba 型算法时期

Karatsuba 算法

前置知识

• 主定理（Master theorem）

Karatsuba 提出了第一个能在低于 $\mathcal O\left(n^2\right)$ 的时间内计算整数乘法的算法去，其复杂度为 $\Theta \left(n^{\log_23}\right)$。

不妨设 $n$ 是偶数，把 $a$ 表示为 $a_0 + a_1 \cdot 2^{n / 2}，$b$ 为 $b_0 + b_1 \cdot 2^{n / 2}$。

而其中 $a_0b_1 + a_1b_0 = \left(a_0 + a_1\right)\left(b_0 + b_1\right) - a_0b_0 - a_1b_1$

于是我们只需要计算 $a_0b_0, \left(a_0 + a_1\right)\left(b_0 + b_1\right), a_1b_1$ 三个乘法即可。

复杂度：$T\left(n\right) = 3T\left(n / 2\right) + \Theta\left(n\right) = n^{\log_23}$。

Toom-Cook 算法

前置知识

• Karatsuba 算法
• 拉格朗日（Lagrange）插值

观察 Karatsuba 算法 的本质：计算二次多项式 $\left(a_0 + a_1x\right)\left(b_0 + b_1x\right)$ 在 $0, 1, \infty$ 这 $3$ 处的点值，然后还原。

根据这个思路，我们可以把 $m$ 写成 $m_0 + m_1x + m_2 x + \ldots + m_kx^k$，那么 $ab$ 就是一个 $2k$ 次多项式，我们需要求出 $2k + 1$ 个点值。

其中 $k^{\mathcal O\left(1\right)}$ 为拉格朗日插值时需要付出的代价。

取 $\log k = \Theta\left(\sqrt{\log n}\right)$，可以做到 $\mathcal O\left(2^{\sqrt{\log^3 n}}\right)$。

快速傅里叶（Fourier）变换时期

Cooley-Tukey 算法

施工中。。。

参考

https://www.cnblogs.com/Elegia/p/18020040/integer-multiplication