编程时写整数乘法，通常我们不会太关心底层细节。a * b 写起来非常自然，好像一条语句就能瞬间完成。
对固定宽度整数来说，比如 32 位或 64 位整数，乘法通常确实可以由少量机器指令完成，成本可以近似看成常数。但如果是两个几千位、几万位甚至更大的整数相乘，情况就不一样了。此时 * 背后不再是一条简单的 CPU 乘法指令，而是一整套大整数乘法算法。
这篇文章要讲的，就是大整数乘法中的一个经典算法：Toom-Cook 算法。
当数值远超一个机器字或寄存器能表示的范围时，就不能再把一次整数乘法视作 \(O(1)\) 操作了。
为了简化讨论，下面把 \(n\) 理解成大整数被拆成的“单元数量”。每个单元可以是一个机器字，也可以是一段固定长度的二进制位，可以快速相乘。
小时候学过的竖式乘法，本质上就是普通乘法。如果两个整数各有 \(n\) 个单元，那么普通乘法大概要做 \(n^2\) 级别的单元乘法。
对于特别大的整数，\(n^2\) 会很快变得昂贵。
Karatsuba 算法是第一个非常经典的优化。它把一个大整数拆成两半，本来需要 4 次子乘法，但通过代数变形，只需要 3 次子乘法。它的复杂度大约是：
\[O(n^{\log_2 3}) \approx O(n^{1.585}) \]
这已经比普通乘法好不少。
而 Toom-Cook 可以看成是 Karatsuba 的推广：Karatsuba 是拆成 2 块，Toom-Cook 可以拆成 3 块、4 块、5 块甚至更多块。
讨论大数乘法问题时，很多不同类型的“乘法”成本并不一样。这个首先要明确。
机器字乘法：如果两个数都能放进一个机器字，比如 32 位或 64 位整数，那么一次乘法通常可以看成 \(O(1)\)。这是我们平时写固定宽度整数乘法时最接近的情况。
大整数乘法：如果两个数都有很多个单元，那么 A * B 就不是一次 \(O(1)\) 操作，而是一个规模随整数长度增长的计算问题。普通竖式乘法、Karatsuba、Toom-Cook 优化的都是这一层的乘法。
大整乘小常数：比如 \( 2a_1 \)，这里的 2 和 4 是固定小常数。它们通常可以通过移位和加法完成。从单个机器字的角度看，每一步很便宜；但如果整个大整数有 \(n\) 个单元，扫完整个数组仍然需要 \(O(n)\) 时间。
乘以 \(\beta\) 或 \(\beta^i\)：后面我们会把大整数写成：
\[A = a_0 + a_1\beta + a_2\beta^2 \]
这里的 \(\beta\) 是分块基数。乘以 \(\beta\)、\(\beta^2\) 只需要移位、搬移和进位处理，而不是普通意义上的大整数乘法。
所以，当我们说 Toom-Cook 把 9 次乘法减少到 5 次乘法时，减少的是第 2 类：真正昂贵的大整数子乘法。
假设我们要计算两个大整数 \(A\) 和 \(B\) 的乘积。要先把它们拆成若干块。
比如把 \(A\) 拆成 3 块：
\[A = a_0 + a_1\beta + a_2\beta^2 \]
这里的 \(\beta\) 可以理解成一个很大的进制基数。例如一个大整数内部用数组存储，每个数组元素存一段二进制位，那么 \(\beta\) 就对应一块的进位单位。
A = [a2][a1][a0]
假如 \(\beta = 10\)，这就等价于个十百千万了（而实际上基数也可以取大得多的数）。同理 \( B = b_0 + b_1\beta + b_2\beta^2 \)
接下来，不再把 \(A\) 和 \(B\) 仅仅看成整数，而是看成两个多项式在 \(x = \beta\) 时的取值。
也就是：
\[A(x) = a_0 + a_1x + a_2x^2 \]
\[B(x) = b_0 + b_1x + b_2x^2 \]
原来的整数 \(A\) 和 \(B\)，就是 \(A(\beta)\) 和 \(B(\beta)\)，也就是函数 \(C(x)=A(x)B(x)\)，在 \(x = \beta\) 的值
Toom-Cook 的流程可以概括成三步：
取值 evaluation
逐点相乘 pointwise multiplication
插值 interpolation
下面以 Toom-3 为例说明。就是把整数拆成 3 块。
此时 \(A(x)\) 和 \(B(x)\) 都是二次多项式。两个二次多项式相乘，结果是一个四次多项式：
\[C(x) = A(x)B(x) \]
四次多项式有 5 个系数：
\[C(x) = c_0 + c_1x + c_2x^2 + c_3x^3 + c_4x^4 \]
所以，只要知道它在 5 个不同点上的值，就能恢复出整个多项式。
Toom-3 常用的取值点是：
0, 1, -1, 2, infinity
这里的 infinity 不是真的无穷大，也不是要带入极限。它只是一个记号，表示取最高次项系数。
对于：
\[A(x) = a_0 + a_1x + a_2x^2 \]
有：
A(infinity) = a2
其他几个点也很直观：
A(0) = a0
A(1) = a0 + a1 + a2
A(-1) = a0 - a1 + a2
A(2) = a0 + 2a1 + 4a2
\(B(x)\) 也做同样的事情：
B(0) = b0
B(1) = b0 + b1 + b2
B(-1) = b0 - b1 + b2
B(2) = b0 + 2b1 + 4b2
B(infinity) = b2
注意，取值过程里虽然出现了 \(2a_1\)、\(4a_2\) 这样的写法，但这不是递归意义上的“大整数乘法”。因为 2 和 4 是固定小常数，它们通常可以通过移位和加法完成。
求完值之后，我们得到若干组点值。然后在相同点上分别相乘：
C(0) = A(0) * B(0)
C(1) = A(1) * B(1)
C(-1) = A(-1) * B(-1)
C(2) = A(2) * B(2)
C(infinity) = A(infinity) * B(infinity)
这里一共做了 5 次乘法。
需要特别注意的是，这里的“乘法”不是 CPU 的单条机器乘法指令，而是 5 次规模更小的大整数乘法。每个参与相乘的数，长度大约是原来的三分之一，再加上一点由求值带来的常数级增长。
如果直接拆成 3 块做普通分块乘法，本来需要 9 次块乘法：
a0*b0, a0*b1, a0*b2
a1*b0, a1*b1, a1*b2
a2*b0, a2*b1, a2*b2
Toom-3 的关键是：用加减、移位、乘以小常数和插值，换掉其中一部分昂贵的大整数乘法，把 9 次子乘法压缩成 5 次子乘法。
对于大整数来说，乘法通常比加减法贵得多。所以用更多线性级别的操作，换更少的递归乘法，通常是划算的。
经过逐点相乘之后，我们知道了 \(C(x)\) 在几个点上的值。
但是最终需要的是 \(C(x)\) 的系数，也就是要恢复：
\[C(x) = c_0 + c_1x + c_2x^2 + c_3x^3 + c_4x^4 \]
这个过程就是插值。
四次多项式可以由 5 个不同点上的取值唯一确定，所以我们可以从：
C(0), C(1), C(-1), C(2), C(infinity)
恢复出：
c0, c1, c2, c3, c4
恢复出这些系数之后，再把 \(x = \beta\) 代回去：
\[AB = c_0 + c_1\beta + c_2\beta^2 + c_3\beta^3 + c_4\beta^4 \]
这样就得到了原来两个大整数的乘积。
这里的乘以 \(\beta^i\) 主要对应把系数块放到正确的位置上，并做进位归一化，也不是重新做几次普通意义上的大整数乘法。
如果把上面的流程写成伪代码，大致是这样：
toom3_mul(A, B):
split A into a0, a1, a2
split B into b0, b1, b2
evaluate:
p0 = a0
p1 = a0 + a1 + a2
pm1 = a0 - a1 + a2
p2 = a0 + 2a1 + 4a2
pinf = a2
q0 = b0
q1 = b0 + b1 + b2
qm1 = b0 - b1 + b2
q2 = b0 + 2b1 + 4b2
qinf = b2
pointwise multiply:
r0 = p0 * q0
r1 = p1 * q1
rm1 = pm1 * qm1
r2 = p2 * q2
rinf = pinf * qinf
interpolate:
recover c0, c1, c2, c3, c4 from r0, r1, rm1, r2, rinf
recombine:
return c0 + c1*beta + c2*beta^2 + c3*beta^3 + c4*beta^4
上面伪代码里，真正昂贵的递归大整数乘法，主要是这 5 行：
r0 = p0 * q0
r1 = p1 * q1
rm1 = pm1 * qm1
r2 = p2 * q2
rinf = pinf * qinf
更一般地，如果把整数拆成 \(k\) 块，那么对应的多项式次数是 \(k - 1\)。
两个 \(k-1\) 次多项式相乘，乘积多项式的最高次数是：
\[2k - 2 \]
因此，它一共有：
\[2k - 1 \]
个系数。
为了恢复这个乘积多项式，我们需要 \(2k - 1\) 个取值点，也就需要做 \(2k - 1\) 次规模更小的子乘法。
在 \(k\) 固定，并且取值、插值、搬移、进位等额外操作都近似为线性级别的前提下，可以粗略写出递推式：
\[T(n) = (2k - 1)T(n/k) + O(n) \]
根据主定理，它的复杂度约为：
\[O(n^{\log_k(2k-1)}) \]
几个常见算法可以粗略对比如下：
普通乘法：O(n^2)
Karatsuba：拆成 2 块，做 3 次子乘法，指数约 1.585
Toom-3：拆成 3 块，做 5 次子乘法，指数约 1.465
Toom-4：拆成 4 块，做 7 次子乘法，指数约 1.404
从理论上看，\(k\) 越大，复杂度指数越低。
但是，\(k\) 变大之后，取值点更多，插值更复杂，中间结果也更多，常数开销会明显增加。因此真实的大整数库不会盲目使用很大的 \(k\)，而是会根据整数规模在普通乘法、Karatsuba、Toom-Cook、FFT 或 NTT 类算法之间切换。
Toom-Cook 的整体思路可以概括为：
大整数太长，直接乘很慢
|
v
把大整数按 beta 拆成几块
|
v
把这些块看成多项式系数
|
v
在几个简单点上求值
|
v
在相同点上逐点相乘
|
v
通过插值恢复乘积多项式
|
v
把 x = beta 代回去，得到最终整数结果
其中最关键的洞察是：大整数乘法可以转化成多项式乘法，而多项式乘法可以通过“取值 + 逐点相乘 + 插值”来完成。
Toom-Cook 并不是让乘法消失，而是把许多直接的分块乘法，变成更少次数的子问题乘法。
它付出的代价是更多加减法、移位、乘以小常数、插值和进位处理。由于这些操作通常比同规模的大整数乘法便宜，所以在数字足够大时，这种交换是划算的。
从这个角度看，Toom-Cook 和 FFT 乘法确实有某种共同精神：它们都不是直接在系数上硬乘，而是换一个表示空间，让乘法在新的表示中更容易完成。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。