间完成。

对固定宽度整数来说，比如 32 位或 64 位整数，乘法通常确实可以由少量机器指令完成，成本可以近似看成常数。但如果是两个几千位、几万位甚至更大的整数相乘，情况就不一样了。此时*背后不再是一条简单的 CPU 乘法指令，而是一整套大整数乘法算法。

这篇文章要讲的，就是大整数乘法中的一个经典算法：Toom-Cook 算法。

从普通乘法说起

当数值远超一个机器字或寄存器能表示的范围时，就不能再把一次整数乘法视作 �(1)O(1) 操作了。

为了简化讨论，下面把 �n 理解成大整数被拆成的“单元数量”。每个单元可以是一个机器字，也可以是一段固定长度的二进制位，可以快速相乘。

小时候学过的竖式乘法，本质上就是普通乘法。如果两个整数各有 �n 个单元，那么普通乘法大概要做 �2n2 级别的单元乘法。

对于特别大的整数，�2n2 会很快变得昂贵。

Karatsuba 算法是第一个非常经典的优化。它把一个大整数拆成两半，本来需要 4 次子乘法，但通过代数变形，只需要 3 次子乘法。它的复杂度大约是：

�(�log⁡23)≈�(�1.585)O(nlog2​3)≈O(n1.585)

这已经比普通乘法好不少。

而 Toom-Cook 可以看成是 Karatsuba 的推广：Karatsuba 是拆成 2 块，Toom-Cook 可以拆成 3 块、4 块、5 块甚至更多块。

不同种类的乘法

讨论大数乘法问题时，很多不同类型的“乘法”成本并不一样。这个首先要明确。

1. 机器字乘法：如果两个数都能放进一个机器字，比如 32 位或 64 位整数，那么一次乘法通常可以看成 �(1)O(1)。这是我们平时写固定宽度整数乘法时最接近的情况。

2. 大整数乘法：如果两个数都有很多个单元，那么A * B就不是一次 �(1)O(1) 操作，而是一个规模随整数长度增长的计算问题。普通竖式乘法、Karatsuba、Toom-Cook 优化的都是这一层的乘法。

3. 大整乘小常数：比如 2�12a1​，这里的 2 和 4 是固定小常数。它们通常可以通过移位和加法完成。从单个机器字的角度看，每一步很便宜；但如果整个大整数有 �n 个单元，扫完整个数组仍然需要 �(�)O(n) 时间。

4. 乘以 �β 或 ��βi：后面我们会把大整数写成：

�=�0+�1�+�2�2A=a0​+a1​β+a2​β2

这里的 �β 是分块基数。乘以 �β、�2β2 只需要移位、搬移和进位处理，而不是普通意义上的大整数乘法。

所以，当我们说 Toom-Cook 把 9 次乘法减少到 5 次乘法时，减少的是第 2 类：真正昂贵的大整数子乘法。

大整数如何拆成多项式

假设我们要计算两个大整数 �A 和 �B 的乘积。要先把它们拆成若干块。

比如把 �A 拆成 3 块：

�=�0+�1�+�2�2A=a0​+a1​β+a2​β2

这里的 �β 可以理解成一个很大的进制基数。例如一个大整数内部用数组存储，每个数组元素存一段二进制位，那么 �β 就对应一块的进位单位。

假如 �=10β=10，这就等价于个十百千万了（而实际上基数也可以取大得多的数）。同理 �=�0+�1�+�2�2B=b0​+b1​β+b2​β2

接下来，不再把 �A 和 �B 仅仅看成整数，而是看成两个多项式在 �=�x=β 时的取值。

也就是：

�(�)=�0+�1�+�2�2A(x)=a0​+a1​x+a2​x2

�(�)=�0+�1�+�2�2B(x)=b0​+b1​x+b2​x2

原来的整数 �A 和 �B，就是 �(�)A(β) 和 �(�)B(β)，也就是函数 �(�)=�(�)�(�)C(x)=A(x)B(x)，在 �=�x=β 的值

Toom-Cook 的核心三步

Toom-Cook 的流程可以概括成三步：

下面以 Toom-3 为例说明。就是把整数拆成 3 块。

此时 �(�)A(x) 和 �(�)B(x) 都是二次多项式。两个二次多项式相乘，结果是一个四次多项式：

�(�)=�(�)�(�)C(x)=A(x)B(x)

四次多项式有 5 个系数：

�(�)=�0+�1�+�2�2+�3�3+�4�4C(x)=c0​+c1​x+c2​x2+c3​x3+c4​x4

所以，只要知道它在 5 个不同点上的值，就能恢复出整个多项式。

第一步：取值

Toom-3 常用的取值点是：

这里的infinity不是真的无穷大，也不是要带入极限。它只是一个记号，表示取最高次项系数。

对于：

�(�)=�0+�1�+�2�2A(x)=a0​+a1​x+a2​x2

有：

其他几个点也很直观：

�(�)B(x) 也做同样的事情：

注意，取值过程里虽然出现了 2�12a1​、4�24a2​ 这样的写法，但这不是递归意义上的“大整数乘法”。因为 2 和 4 是固定小常数，它们通常可以通过移位和加法完成。

第二步：逐点相乘

求完值之后，我们得到若干组点值。然后在相同点上分别相乘：

这里一共做了 5 次乘法。

需要特别注意的是，这里的“乘法”不是 CPU 的单条机器乘法指令，而是 5 次规模更小的大整数乘法。每个参与相乘的数，长度大约是原来的三分之一，再加上一点由求值带来的常数级增长。

如果直接拆成 3 块做普通分块乘法，本来需要 9 次块乘法：

Toom-3 的关键是：用加减、移位、乘以小常数和插值，换掉其中一部分昂贵的大整数乘法，把 9 次子乘法压缩成 5 次子乘法。

对于大整数来说，乘法通常比加减法贵得多。所以用更多线性级别的操作，换更少的递归乘法，通常是划算的。

第三步：插值

经过逐点相乘之后，我们知道了 �(�)C(x) 在几个点上的值。

但是最终需要的是 �(�)C(x) 的系数，也就是要恢复：

�(�)=�0+�1�+�2�2+�3�3+�4�4C(x)=c0​+c1​x+c2​x2+c3​x3+c4​x4

这个过程就是插值。

四次多项式可以由 5 个不同点上的取值唯一确定，所以我们可以从：

恢复出：

恢复出这些系数之后，再把 �=�x=β 代回去：

��=�0+�1�+�2�2+�3�3+�4�4AB=c0​+c1​β+c2​β2+c3​β3+c4​β4

这样就得到了原来两个大整数的乘积。

这里的乘以 ��βi 主要对应把系数块放到正确的位置上，并做进位归一化，也不是重新做几次普通意义上的大整数乘法。

伪代码

如果把上面的流程写成伪代码，大致是这样：

上面伪代码里，真正昂贵的递归大整数乘法，主要是这 5 行：

Toom-k 的一般形式

更一般地，如果把整数拆成 �k 块，那么对应的多项式次数是 �−1k−1。

两个 �−1k−1 次多项式相乘，乘积多项式的最高次数是：

2�−22k−2

因此，它一共有：

2�−12k−1

个系数。

为了恢复这个乘积多项式，我们需要 2�−12k−1 个取值点，也就需要做 2�−12k−1 次规模更小的子乘法。

在 �k 固定，并且取值、插值、搬移、进位等额外操作都近似为线性级别的前提下，可以粗略写出递推式：

�(�)=(2�−1)�(�/�)+�(�)T(n)=(2k−1)T(n/k)+O(n)

根据主定理，它的复杂度约为：

�(�log⁡�(2�−1))O(nlogk​(2k−1))

几个常见算法可以粗略对比如下：

从理论上看，�k 越大，复杂度指数越低。

但是，�k 变大之后，取值点更多，插值更复杂，中间结果也更多，常数开销会明显增加。因此真实的大整数库不会盲目使用很大的 �k，而是会根据整数规模在普通乘法、Karatsuba、Toom-Cook、FFT 或 NTT 类算法之间切换。

总结

Toom-Cook 的整体思路可以概括为：

其中最关键的洞察是：大整数乘法可以转化成多项式乘法，而多项式乘法可以通过“取值 + 逐点相乘 + 插值”来完成。

Toom-Cook 并不是让乘法消失，而是把许多直接的分块乘法，变成更少次数的子问题乘法。