约定
现在要计算两个 $n$ 位二进制数 $a$ 和 $b$ 的乘积，这是为了方便描述，一下算法可以直接应用到任意进制的情况。
我们的计算机每次仅可以对一位二进制位进行操作，我们的复杂度也是在这样的机器上进行计算的。
Karatsuba 型算法时期
Karatsuba 算法
前置知识
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}$。
$$ab = a_0b_0 + \left(a_0b_1 + a_1b_0\right) \cdot 2^{n / 2} + a_1b_1 \cdot 2^n$$
而其中 $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$ 个点值。
$$T\left(n\right) = \left(2k + 1\right) T\left(n / \left(k + 1\right)\right) + k^{\mathcal O\left(1\right)}n$$
其中 $k^{\mathcal O\left(1\right)}$ 为拉格朗日插值时需要付出的代价。
$$T\left(n\right) = \mathcal O\left(n^{\log_{k + 1}2k + 1}k^{\mathcal O\left(1\right)}\right) = \mathcal O\left(n \cdot \exp\left\{\mathcal O\left(\frac{\log n}{\log k}\right) + \mathcal O\left(\log k\right)\right\}\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