图姆-库克算法

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

1. 拆分
2. 求值
3. 点乘
4. 插值
5. 重组

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

${\displaystyle m}$	=	${\displaystyle 12}$	${\displaystyle 3456}$	${\displaystyle 7890}$	${\displaystyle 1234}$	${\displaystyle 5678}$	${\displaystyle 9012}$
${\displaystyle n}$	=	${\displaystyle 9}$	${\displaystyle 8765}$	${\displaystyle 4321}$	${\displaystyle 9876}$	${\displaystyle 5432}$	${\displaystyle 1098}$

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

拆分

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

${\displaystyle i=\max \left\{\left\lfloor {\frac {\left\lfloor \log _{b}m\right\rfloor }{k}}\right\rfloor ,\left\lfloor {\frac {\left\lfloor \log _{b}n\right\rfloor }{k}}\right\rfloor \right\}+1.}$ 

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

${\displaystyle {\begin{aligned}m_{2}&{}=123456\\m_{1}&{}=78901234\\m_{0}&{}=56789012\\n_{2}&{}=98765\\n_{1}&{}=43219876\\n_{0}&{}=54321098\end{aligned}}}$ 

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

${\displaystyle p(x)=m_{2}x^{2}+m_{1}x+m_{0}=123456x^{2}+78901234x+56789012\,}$ 

${\displaystyle q(x)=n_{2}x^{2}+n_{1}x+n_{0}=98765x^{2}+43219876x+54321098\,}$ 

定义这些多项式的目的在于：如果计算出它们的乘积${\displaystyle r(x)=p(x)q(x)}$ ，我们的答案就会是${\displaystyle r(B)=m\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 i=\max \left\{\left\lfloor {\frac {\left\lceil \log _{b}m\right\rceil }{k_{m}}}\right\rfloor ,\left\lfloor {\frac {\left\lceil \log _{b}n\right\rceil }{k_{n}}}\right\rfloor \right\}.}$ 

求值

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

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

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

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

${\displaystyle {\begin{array}{lrlrl}p(0)&=&m_{0}+m_{1}(0)+m_{2}(0)^{2}&=&m_{0}\\p(1)&=&m_{0}+m_{1}(1)+m_{2}(1)^{2}&=&m_{0}+m_{1}+m_{2}\\p(-1)&=&m_{0}+m_{1}(-1)+m_{2}(-1)^{2}&=&m_{0}-m_{1}+m_{2}\\p(-2)&=&m_{0}+m_{1}(-2)+m_{2}(-2)^{2}&=&m_{0}-2m_{1}+4m_{2}\\p(\infty )&=&m_{2}&&\end{array}}}$ 

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

${\displaystyle p(0)}$	=	${\displaystyle m_{0}}$	=	${\displaystyle 56789012}$	=	${\displaystyle 56789012}$
${\displaystyle p(1)}$	=	${\displaystyle m_{0}+m_{1}+m_{2}}$	=	${\displaystyle 56789012+78901234+123456}$	=	${\displaystyle 135813702}$
${\displaystyle p(-1)}$	=	${\displaystyle m_{0}-m_{1}+m_{2}}$	=	${\displaystyle 56789012-78901234+123456}$	=	${\displaystyle -21988766}$
${\displaystyle p(-2)}$	=	${\displaystyle m_{0}-2m_{1}+4m_{2}}$	=	${\displaystyle 56789012-2\times 78901234+4\times 123456}$	=	${\displaystyle -100519632}$
${\displaystyle p(\infty )}$	=	${\displaystyle m_{2}}$	=	${\displaystyle 123456}$	=	${\displaystyle 123456}$
${\displaystyle q(0)}$	=	${\displaystyle n_{0}}$	=	${\displaystyle 54321098}$	=	${\displaystyle 54321098}$
${\displaystyle q(1)}$	=	${\displaystyle n_{0}+n_{1}+n_{2}}$	=	${\displaystyle 54321098+43219876+98765}$	=	${\displaystyle 97639739}$
${\displaystyle q(-1)}$	=	${\displaystyle n_{0}-n_{1}+n_{2}}$	=	${\displaystyle 54321098-43219876+98765}$	=	${\displaystyle 11199987}$
${\displaystyle q(-2)}$	=	${\displaystyle n_{0}-2n_{1}+4n_{2}}$	=	${\displaystyle 54321098-2\times 43219876+4\times 98765}$	=	${\displaystyle -31723594}$
${\displaystyle q(\infty )}$	=	${\displaystyle n_{2}}$	=	${\displaystyle 98765}$	=	${\displaystyle 98765}$  .

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

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

${\displaystyle \left({\begin{matrix}p(0)\\p(1)\\p(-1)\\p(-2)\\p(\infty )\end{matrix}}\right)=\left({\begin{matrix}0^{0}&0^{1}&0^{2}\\1^{0}&1^{1}&1^{2}\\(-1)^{0}&(-1)^{1}&(-1)^{2}\\(-2)^{0}&(-2)^{1}&(-2)^{2}\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right)=\left({\begin{matrix}1&0&0\\1&1&1\\1&-1&1\\1&-2&4\\0&0&1\end{matrix}}\right)\left({\begin{matrix}m_{0}\\m_{1}\\m_{2}\end{matrix}}\right).}$ 

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}$ 。

更快的求值

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

${\displaystyle p_{0}}$	${\displaystyle \leftarrow }$	${\displaystyle m_{0}+m_{2}}$	=	${\displaystyle 56789012+123456}$	=	${\displaystyle 56912468}$
${\displaystyle p(0)}$	=	${\displaystyle m_{0}}$	=	${\displaystyle 56789012}$	=	${\displaystyle 56789012}$
${\displaystyle p(1)}$	=	${\displaystyle p_{0}+m_{1}}$	=	${\displaystyle 56912468+78901234}$	=	${\displaystyle 135813702}$
${\displaystyle p(-1)}$	=	${\displaystyle p_{0}-m_{1}}$	=	${\displaystyle 56912468-78901234}$	=	${\displaystyle -21988766}$
${\displaystyle p(-2)}$	=	${\displaystyle (p(-1)+m_{2})\times 2-m_{0}}$	=	${\displaystyle (-21988766+123456)\times 2-56789012}$	=	${\displaystyle -100519632}$
${\displaystyle p(\infty )}$	=	${\displaystyle m_{2}}$	=	${\displaystyle 123456}$	=	${\displaystyle 123456}$

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

点乘

与对多项式${\displaystyle p(\cdot )}$ 和${\displaystyle q(\cdot )}$ 所进行的乘法不同，将${\displaystyle p(a)}$  和${\displaystyle q(a)}$ 被求出的值相乘仅涉及整数相乘——这是原始问题的较小实例。我们递归调用我们的乘法过程来使每对已求值的点相乘。在实践中，随着乘数减小，算法将逐渐过渡为教科书长乘法。令${\displaystyle r}$ 为多项式乘积，我们将得到：

${\displaystyle r(0)}$	=	${\displaystyle p(0)q(0)}$	=	${\displaystyle 56789012\times 54321098}$	=	${\displaystyle 3084841486175176}$
${\displaystyle r(1)}$	=	${\displaystyle p(1)q(1)}$	=	${\displaystyle 135813702\times 97639739}$	=	${\displaystyle 13260814415903778}$
${\displaystyle r(-1)}$	=	${\displaystyle p(-1)q(-1)}$	=	${\displaystyle -21988766\times 11199987}$	=	${\displaystyle -246273893346042}$
${\displaystyle r(-2)}$	=	${\displaystyle p(-2)q(-2)}$	=	${\displaystyle -100519632\times -31723594}$	=	${\displaystyle 3188843994597408}$
${\displaystyle r(\infty )}$	=	${\displaystyle p(\infty )q(\infty )}$	=	${\displaystyle 123456\times 98765}$	=	${\displaystyle 12193131840}$

如上所示，这些值也可以是负数。对于足够大的数值，这里是最昂贵的、唯一与${\displaystyle m}$ 、${\displaystyle n}$ 大小不成线性关系的步骤。

插值

这一步最为复杂。与求值相反：给定多项式乘积${\displaystyle r(\cdot )}$ 上的${\displaystyle d}$ 点，我们需要确定其系数。换句话说，我们要在右侧求解其向量的矩阵方程：

${\displaystyle {\begin{aligned}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)&{}=\left({\begin{matrix}0^{0}&0^{1}&0^{2}&0^{3}&0^{4}\\1^{0}&1^{1}&1^{2}&1^{3}&1^{4}\\(-1)^{0}&(-1)^{1}&(-1)^{2}&(-1)^{3}&(-1)^{4}\\(-2)^{0}&(-2)^{1}&(-2)^{2}&(-2)^{3}&(-2)^{4}\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right).\end{aligned}}}$ 

此矩阵的构造与求值步骤中的矩阵相同，不过它是${\displaystyle d\times d}$ 的。我们可以用高斯消元法来求出方程的解，但这样非常昂贵。根据以下事实：只要求值点的选择合适，这个矩阵就是可逆的。因此我们有：

${\displaystyle {\begin{aligned}\left({\begin{matrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{matrix}}\right)&{}=\left({\begin{matrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&-2&4&-8&16\\0&0&0&0&1\end{matrix}}\right)^{-1}\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right)\\&{}=\left({\begin{matrix}1&0&0&0&0\\{\tfrac {1}{2}}&{\tfrac {1}{3}}&-1&{\tfrac {1}{6}}&-2\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0&-1\\-{\tfrac {1}{2}}&{\tfrac {1}{6}}&{\tfrac {1}{2}}&-{\tfrac {1}{6}}&2\\0&0&0&0&1\end{matrix}}\right)\left({\begin{matrix}r(0)\\r(1)\\r(-1)\\r(-2)\\r(\infty )\end{matrix}}\right).\end{aligned}}}$ 

接下来即要求得该矩阵的向量积。尽管矩阵中包含分数，但所得的系数却是整数——因此所有这些都可以在整数算术中完成，仅仅是与小常数进行加减乘除。图姆-库克设计时面临的一个困难挑战就是找到有效的操作顺序来计算该乘积。下面是波德拉托为Toom-3找到的一组顺序，通过上面的示例演示：

${\displaystyle r_{0}}$	${\displaystyle \leftarrow }$	${\displaystyle r(0)}$	=	${\displaystyle 3084841486175176}$
${\displaystyle r_{4}}$	${\displaystyle \leftarrow }$	${\displaystyle r(\infty )}$	=	${\displaystyle 12193131840}$
${\displaystyle r_{3}}$	${\displaystyle \leftarrow }$	${\displaystyle (r(-2)-r(1))/3}$	=	${\displaystyle (3188843994597408-13260814415903778)/3}$
			=	${\displaystyle -3357323473768790}$
${\displaystyle r_{1}}$	${\displaystyle \leftarrow }$	${\displaystyle (r(1)-r(-1))/2}$	=	${\displaystyle (13260814415903778-(-246273893346042))/2}$
			=	${\displaystyle 6753544154624910}$
${\displaystyle r_{2}}$	${\displaystyle \leftarrow }$	${\displaystyle r(-1)-r(0)}$	=	${\displaystyle -246273893346042-3084841486175176}$
			=	${\displaystyle -3331115379521218}$
${\displaystyle r_{3}}$	${\displaystyle \leftarrow }$	${\displaystyle (r_{2}-r_{3})/2+2r(\infty )}$	=	${\displaystyle (-3331115379521218-(-3357323473768790))/2+2\times 12193131840}$
			=	${\displaystyle 13128433387466}$
${\displaystyle r_{2}}$	${\displaystyle \leftarrow }$	${\displaystyle r_{2}+r_{1}-r_{4}}$	=	${\displaystyle -3331115379521218+6753544154624910-12193131840}$
			=	${\displaystyle 3422416581971852}$
${\displaystyle r_{1}}$	${\displaystyle \leftarrow }$	${\displaystyle r_{1}-r_{3}}$	=	${\displaystyle 6753544154624910-13128433387466}$
			=	${\displaystyle 6740415721237444.}$

现在我们知道多项式乘积${\displaystyle r}$ ：

${\displaystyle {\begin{array}{rrr}r(x)=&{}&3084841486175176\\&+&6740415721237444x\\&+&3422416581971852x^{2}\\&+&13128433387466x^{3}\\&+&12193131840x^{4}\end{array}}}$ 

如果我们使用不同的${\displaystyle k_{m}}$ 、${\displaystyle k_{n}}$ 或求值点，矩阵和我们的插值将改变。但是它不依赖于输入，因此可以对任何给定的参数集进行硬编码。

重组

最后，我们将求出${\displaystyle r(B)}$ 的值以获得最终结果。很显然，由于${\displaystyle B}$ 是${\displaystyle b}$ 的幂，因此对${\displaystyle B}$ 的幂的乘法同样也可以应用于所有以${\displaystyle b}$ 为底数的数值。在这个示例中，${\displaystyle b=10^{4}}$ 且${\displaystyle B=b^{2}=10^{8}}$ 。

								${\displaystyle 3084}$	${\displaystyle 8414}$	${\displaystyle 8617}$	${\displaystyle 5176}$
						${\displaystyle 6740}$	${\displaystyle 4157}$	${\displaystyle 2123}$	${\displaystyle 7444}$
				${\displaystyle 3422}$	${\displaystyle 4165}$	${\displaystyle 8197}$	${\displaystyle 1852}$
		${\displaystyle 13}$	${\displaystyle 1284}$	${\displaystyle 3338}$	${\displaystyle 7466}$
${\displaystyle +}$	${\displaystyle 121}$	${\displaystyle 9313}$	${\displaystyle 1840}$
	${\displaystyle 121}$	${\displaystyle 9326}$	${\displaystyle 3124}$	${\displaystyle 6761}$	${\displaystyle 1632}$	${\displaystyle 4937}$	${\displaystyle 6009}$	${\displaystyle 5208}$	${\displaystyle 5858}$	${\displaystyle 8617}$	${\displaystyle 5176}$

这实际上是${\displaystyle 1234567890123456789012}$ 与${\displaystyle 987654321987654321098}$ 的乘积。

这里我们给出了几种${\displaystyle k_{m}}$ 和${\displaystyle k_{n}}$ 取常见较小值的插值矩阵。

Toom-1

Toom-1（${\displaystyle k_{m}=k_{n}=1}$ ）需要一个求值点，这里选择${\displaystyle 0}$ 。它退化为长乘法，并且使用恒等矩阵的插值矩阵。

${\displaystyle \left({\begin{matrix}1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1\end{matrix}}\right).}$ 

Toom-1.5

Toom-1.5（${\displaystyle k_{m}=2,k_{n}=1}$ ）需要两个求值点，这里选择${\displaystyle 0}$ 和${\displaystyle \infty }$ ，且其插值矩阵就是恒等矩阵。

${\displaystyle \left({\begin{matrix}1&0\\0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0\\0&1\end{matrix}}\right).}$ 

这里亦退化为长乘法：一个因数的两个系数都乘以另一个因数的两个系数。

Toom-2

Toom-2（${\displaystyle k_{m}=2,k_{n}=2}$ ）需要三个求值点，这里选择${\displaystyle 0}$ 、${\displaystyle 1}$ 和${\displaystyle \infty }$ 。它与 Karatsuba 算法相同，其插值矩阵为：

${\displaystyle \left({\begin{matrix}1&0&0\\1&1&1\\0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0\\-1&1&-1\\0&0&1\end{matrix}}\right).}$ 

Toom-2.5

Toom-2.5（${\displaystyle k_{m}=3,k_{n}=2}$ ）需要四个求值点，这里选择${\displaystyle 0}$ 、${\displaystyle 1}$ 、${\displaystyle -1}$ 和${\displaystyle \infty }$ 。它的插值矩阵为：

${\displaystyle \left({\begin{matrix}1&0&0&0\\1&1&1&1\\1&-1&1&-1\\0&0&0&1\end{matrix}}\right)^{-1}=\left({\begin{matrix}1&0&0&0\\0&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&-1\\-1&{\tfrac {1}{2}}&{\tfrac {1}{2}}&0\\0&0&0&1\end{matrix}}\right).}$ 

• 乘法算法
• 任意精度整数
• 长乘法
• Karatsuba 算法
• 施特拉森算法
• 富尔算法

1. ^ ^{1.0 1.1} Knuth, p. 296
2. ^ Crandall & Pomerance, p. 474
3. ^ Crandall & Pomerance, p. 536
4. ^ Knuth, p. 302
5. ^ [http：//cr.yp.to/bib/1966/cook.html Positive Results], chapter III of Stephen A. Cook: On the Minimum Computation Time of Functions.
6. ^ ^{6.0 6.1} Marco Bodrato. Towards Optimal Toom-Cook Algorithms for Univariate and Multivariate Polynomials in Characteristic 2 and 0. In WAIFI'07 proceedings, volume 4547 of LNCS, pages 116–133. June 21–22, 2007. [http：//bodrato.it/papers/#WAIFI2007 author website]

• D. Knuth. The Art of Computer Programming, Volume 2. Third Edition, Addison-Wesley, 1997. Section 4.3.3.A： Digital methods, pg.294.
• R. Crandall & C. Pomerance. Prime Numbers – A Computational Perspective. Second Edition, Springer, 2005. Section 9.5.1： Karatsuba and Toom–Cook methods, pg.473.
• M. Bodrato. Toward Optimal Toom-Cook （页面存档备份，存于互联网档案馆）. In WAIFI'07, Springer, 2007.

• http://gmplib.org/manual/Toom-3_002dWay-Multiplication.html（页面存档备份，存于互联网档案馆）