图姆-库克算法

图姆-库克算法（英语：Toom–Cook），有时也被称为Toom-3算法，由安德鲁·图姆命名，他提出了这种算法的基本原理，而斯蒂芬·库克则最先用简洁的形式描述并改进了这种算法，将其作为大整数的乘法算法。

图姆-库克算法的原理是：对于给定的两个大整数${\displaystyle a}$和${\displaystyle b}$ ，将${\displaystyle a}$和${\displaystyle b}$分成${\displaystyle k}$个较小的部分，每个部分的长度为${\displaystyle l}$ ，并对这些部分执行运算。随着${\displaystyle k}$的增长，可以组合许多乘法子运算，从而降低算法的整体复杂度，然后再次使用图姆-库克算法递归计算乘法子运算，依此类推。Toom-3和图姆-库克两个术语有时会被错误的混用，但事实上Toom-3只是图姆-库克算法在${\displaystyle k=3}$时的特例。

Toom-3将9次乘法降低至仅需5次，使其在${\displaystyle \mathrm{\Theta <!--\; \Theta \; -->}(n^{\log <!--\; \; -->(5)/\log <!--\; \; -->(3)})\approx <!--\; \approx \; -->\mathrm{\Theta <!--\; \Theta \; -->}(n^{1.46})}$的时间里运行。通常，Toom-${\displaystyle k}$的时间复杂度为${\displaystyle \mathrm{\Theta <!--\; \Theta \; -->}(c(k)n^e)}$ ，其中${\displaystyle e=\log <!--\; \; -->(2k-<!--\; -\; -->1)/\log <!--\; \; -->(k)}$。${\displaystyle n^e}$是在乘法子运算上花费的时间，${\displaystyle c}$则是花费在对小常数进行的加法和乘法运算上的时间。著名的Karatsuba算法实际上是图姆-库克算法的特例，在Karatsuba算法中，原始乘数被拆分成两个较小的数，而原本的4次乘法运算缩减为3次，使之在${\displaystyle \mathrm{\Theta <!--\; \Theta \; -->}(n^{\log <!--\; \; -->(3)/\log <!--\; \; -->(2)})\approx <!--\; \approx \; -->\mathrm{\Theta <!--\; \Theta \; -->}(n^{1.58})}$的时间内完成运算。Toom-1等价于普通的长乘法，具有${\displaystyle \mathrm{\Theta <!--\; \Theta \; -->}(n^2)}$的复杂度。

尽管可以通过增加${\displaystyle k}$来使指数${\displaystyle e}$任意接近1，但函数${\displaystyle c}$增长速度非常快。混合级别图姆-库克算法的增长率直到2005年仍然是一个广为研究的开放性问题。根据高德纳所描述算法的一种实现，其复杂度可降低至${\displaystyle \mathrm{\Theta <!--\; \Theta \; -->}(n{2}^{\sqrt{2\log <!--\; \; -->n}}\log <!--\; \; -->n)}$。

由于工作时的开销，当乘数包括较小的数时，图姆-库克算法会比长乘法更慢，因此它适用于中等规模的乘法。对于更大规模的数据，则有渐进更快的史恩哈格·施特拉森算法（复杂度为${\displaystyle \mathrm{\Theta <!--\; \Theta \; -->}(n\log <!--\; \; -->n\log <!--\; \; -->\log <!--\; \; -->n)}$）。

这一算法由安德鲁·图姆1963年首次描述，并在斯蒂芬·库克1966年的博士学位论文中得到渐进等效的改进。

本节将讨论对于任意给定 ${\displaystyle k}$ 值， Toom-${\displaystyle k}$究竟是如何运作的，这是马可·波德拉托对图姆-库克多项式乘法的简化描述。这个算法包括五个主要步骤：

在典型的大整数实现中，每个整数都表示为${\displaystyle b}$进制的数字序列（${\displaystyle b}$通常取较大的数）。在此示例中，${\displaystyle b=10000}$，因此每个数字序列对应一组十进制数字（在实践中，${\displaystyle b}$通常取${\displaystyle 2}$的幂）。设要相乘的两个大整数${\displaystyle m}$ 、 ${\displaystyle n}$分别是：

这对乘数实际上比图姆-库克算法通常要处理的数据小很多，在此使用学校里学习的普通乘法可能会更快，但这个示例仍有助于说明图姆-库克算法的工作原理。

第一步是选择基数${\displaystyle B=b^i}$，使得两个数字${\displaystyle m}$和${\displaystyle n}$可以分成${\displaystyle k}$段大小不超过${\displaystyle B}$的数字（例如在Toom-3算法中，拆分段数应至多为3）。${\displaystyle i}$常常根据如下公式求得：

我们的示例将演绎Toom-3算法的运算过程，因此确定${\displaystyle B=b^2={10}^8}$，接着把${\displaystyle m}$和${\displaystyle n}$拆分为3段，即${\displaystyle m_i}$和${\displaystyle n_i}$，则有：

然后，我们把这些数作为${\displaystyle (k-<!--\; -\; -->1)}$阶多项式${\displaystyle p}$和${\displaystyle q}$的系数，with the property that ${\displaystyle p(B)=m}$ and ${\displaystyle q(B)=n}$：

定义这些多项式的目的在于：如果计算出它们的乘积${\displaystyle r(x)=p(x)q(x)}$，我们的答案就会是${\displaystyle r(B)=m\times <!--\; \times \; -->n}$。

如果乘数位数不同，对于${\displaystyle m}$、${\displaystyle n}$分别取不同的${\displaystyle k}$值十分有用，我们将其称为${\displaystyle k_m}$和${\displaystyle k_n}$。例如，算法“Toom-2.5”是指${\displaystyle k_m=3}$且${\displaystyle k_n=2}$时的图姆-库克算法。这时${\displaystyle B=b^i}$中的${\displaystyle i}$通常被确定为：

图姆-库克算法包含一种常用的方法，来计算多项式${\displaystyle p(x)}$、${\displaystyle q(x)}$的乘积。注意，次数为${\displaystyle d}$的多项式可以通过${\displaystyle d+1}$个空间中的点确定（例如一次多项式是一条直线，它由两个点确定）。这个方法是在各个点上求值${\displaystyle p(\cdot <!--\; \cdot \; -->)}$和${\displaystyle q(\cdot <!--\; \cdot \; -->)}$，然后把这些点相乘以获得多项式乘积上的点，最后进行插值以找到其系数。

由于${\displaystyle \mathrm{deg}<!--\; \; -->(pq)=\mathrm{deg}<!--\; \; -->(p)+\mathrm{deg}<!--\; \; -->(q)}$，我们将需要${\displaystyle \mathrm{deg}<!--\; \; -->(p)+\mathrm{deg}<!--\; \; -->(q)+1=k_m+k_n-<!--\; -\; -->1}$个点来确定最终结果${\displaystyle d}$。在Toom-3的情况下，${\displaystyle d=5}$。无论选择什么点，该算法都可以工作（有一些小例外，请参阅插值中的矩阵可逆性约束），但为了简化算法，最好选择较小的整数值，例如${\displaystyle 0}$ 、${\displaystyle 1}$ 、${\displaystyle -<!--\; -\; -->1}$和${\displaystyle -<!--\; -\; -->2}$。

无穷大是一个常被使用的不寻常点，其记作${\displaystyle \mathrm{\infty <!--\; \infty \; -->}}$或${\displaystyle 1/0}$。求多项式${\displaystyle p}$在无穷大时的值，实际上意味着令${\displaystyle p(x)/x^{\mathrm{deg}<!--\; \; -->p}}$的上限为${\displaystyle x}$ 且趋向无穷大。因此，${\displaystyle p(\mathrm{\infty <!--\; \infty \; -->})}$总是其高阶系数的值（${\displaystyle m_2}$是上文中的系数）。

在我们的Toom-3示例中，我们将使用点${\displaystyle 0}$ 、 ${\displaystyle 1}$ 、 ${\displaystyle -<!--\; -\; -->1}$ 、 ${\displaystyle -<!--\; -\; -->2}$和${\displaystyle \mathrm{\infty <!--\; \infty \; -->}}$，这些选择简化了求值，如下式子：

对于${\displaystyle q}$也是如此。在示例中，我们得到的值是：

如上所示，这些值可以包括负值。

为了下文的阐述，把这个求值过程视作矩阵向量乘法较为有用。其中，矩阵的每一行都包含求值点之一的幂，且向量包含多项式的系数：

The dimensions of the matrix are  ${\displaystyle d}$ by  ${\displaystyle k_m}$ for  ${\displaystyle p}$ and  ${\displaystyle d}$ by  ${\displaystyle k_n}$ for  ${\displaystyle q}$。除最后一列的 ${\displaystyle 1}$ 以外，无穷大的行总是${\displaystyle 0}$。

与上述公式相比，多点求值可能会减少基本运算（加、减）的次数，更快获得需要的结果。波德拉托 为Toom-3给出的序列如下所示，它是在运行示例的第一个操作数（多项式${\displaystyle p}$上进行的）：

此序列需要进行五次加/减运算，比简单求值少一次，同时节省了在计算${\displaystyle p(-<!--\; -\; -->2)}$时乘以${\displaystyle 4}$的开销。

与对多项式${\displaystyle p(\cdot <!--\; \cdot \; -->)}$和