本节将讨论对于任意给定 值, Toom- 究竟是如何运作的,这是马可·波德拉托对图姆-库克多项式乘法的简化描述[6]。这个算法包括五个主要步骤:
- 拆分
- 求值
- 点乘
- 插值
- 重组
在典型的大整数实现中,每个整数都表示为 进制的数字序列( 通常取较大的数)。在此示例中, ,因此每个数字序列对应一组十进制数字(在实践中, 通常取 的幂)。设要相乘的两个大整数 、 分别是:
|
= |
|
|
|
|
|
|
|
=
|
|
|
|
|
|
|
这对乘数实际上比图姆-库克算法通常要处理的数据小很多,在此使用学校里学习的普通乘法可能会更快,但这个示例仍有助于说明图姆-库克算法的工作原理。
拆分
第一步是选择基数 ,使得两个数字 和 可以分成 段大小不超过 的数字(例如在Toom-3算法中,拆分段数应至多为3)。 常常根据如下公式求得:
-
我们的示例将演绎Toom-3算法的运算过程,因此确定 ,接着把 和 拆分为3段,即 和 ,则有:
-
然后,我们把这些数作为 阶多项式 和 的系数,with the property that and :
-
-
定义这些多项式的目的在于:如果计算出它们的乘积 ,我们的答案就会是 。
如果乘数位数不同,对于 、 分别取不同的 值十分有用,我们将其称为 和 。例如,算法“Toom-2.5”是指 且 时的图姆-库克算法。这时 中的 通常被确定为:
-
求值
图姆-库克算法包含一种常用的方法,来计算多项式 、 的乘积。注意,次数为 的多项式可以通过 个空间中的点确定(例如一次多项式是一条直线,它由两个点确定)。这个方法是在各个点上求值 和 ,然后把这些点相乘以获得多项式乘积上的点,最后进行插值以找到其系数。
由于 ,我们将需要 个点来确定最终结果 。在Toom-3的情况下, 。无论选择什么点,该算法都可以工作(有一些小例外,请参阅插值中的矩阵可逆性约束),但为了简化算法,最好选择较小的整数值,例如 、 、 和 。
无穷大是一个常被使用的不寻常点,其记作 或 。求多项式 在无穷大时的值,实际上意味着令 的上限为 且趋向无穷大。因此, 总是其高阶系数的值( 是上文中的系数)。
在我们的Toom-3示例中,我们将使用点 、 、 、 和 ,这些选择简化了求值,如下式子:
-
对于 也是如此。在示例中,我们得到的值是:
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
.
|
如上所示,这些值可以包括负值。
为了下文的阐述,把这个求值过程视作矩阵向量乘法较为有用。其中,矩阵的每一行都包含求值点之一的幂,且向量包含多项式的系数:
-
The dimensions of the matrix are by for and by for 。除最后一列的 以外,无穷大的行总是 。
更快的求值
与上述公式相比,多点求值可能会减少基本运算(加、减)的次数,更快获得需要的结果。波德拉托[6] 为Toom-3给出的序列如下所示,它是在运行示例的第一个操作数(多项式 上进行的):
|
|
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
此序列需要进行五次加/减运算,比简单求值少一次,同时节省了在计算 时乘以 的开销。
点乘
与对多项式 和 所进行的乘法不同,将 和 被求出的值相乘仅涉及整数相乘——这是原始问题的较小实例。我们递归调用我们的乘法过程来使每对已求值的点相乘。在实践中,随着乘数减小,算法将逐渐过渡为教科书长乘法。令 为多项式乘积,我们将得到:
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
|
= |
|
= |
|
= |
|
如上所示,这些值也可以是负数。对于足够大的数值,这里是最昂贵的、唯一与 、 大小不成线性关系的步骤。
插值
这一步最为复杂。与求值相反:给定多项式乘积 上的 点,我们需要确定其系数。换句话说,我们要在右侧求解其向量的矩阵方程:
-
此矩阵的构造与求值步骤中的矩阵相同,不过它是 的。我们可以用高斯消元法来求出方程的解,但这样非常昂贵。根据以下事实:只要求值点的选择合适,这个矩阵就是可逆的。因此我们有:
-
接下来即要求得该矩阵的向量积。尽管矩阵中包含分数,但所得的系数却是整数——因此所有这些都可以在整数算术中完成,仅仅是与小常数进行加减乘除。图姆-库克设计时面临的一个困难挑战就是找到有效的操作顺序来计算该乘积。下面是波德拉托为Toom-3找到的一组顺序,通过上面的示例演示:
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
|
|
|
= |
|
现在我们知道多项式乘积 :
-
如果我们使用不同的 、 或求值点,矩阵和我们的插值将改变。但是它不依赖于输入,因此可以对任何给定的参数集进行硬编码。
重组
最后,我们将求出 的值以获得最终结果。很显然,由于 是 的幂,因此对 的幂的乘法同样也可以应用于所有以 为底数的数值。在这个示例中, 且 。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
这实际上是 与 的乘积。
这里我们给出了几种 和 取常见较小值的插值矩阵。
Toom-1
Toom-1( )需要一个求值点,这里选择 。它退化为长乘法,并且使用恒等矩阵的插值矩阵。
-
Toom-1.5
Toom-1.5( )需要两个求值点,这里选择 和 ,且其插值矩阵就是恒等矩阵。
-
这里亦退化为长乘法:一个因数的两个系数都乘以另一个因数的两个系数。
Toom-2
Toom-2( )需要三个求值点,这里选择 、 和 。它与 Karatsuba 算法相同,其插值矩阵为:
-
Toom-2.5
Toom-2.5( )需要四个求值点,这里选择 、 、 和 。它的插值矩阵为:
-