1

我想知道关于 Katatsuba 算法的这个问题。当您应用 Karatsuba 时，您基本上必须在每次循环运行时进行 3 次乘法这些是（假设ab和cd分别是带有数字的 2 位数字a, b, c and d）：

X = bd
Y = ac
Z = (a+c)(c+d)

然后我们正在寻找的总和是：

bd = X 
ac = Y 
(bc + ad) = Z - X - Y

我的问题是：假设我们有两个 3 位数字：abc, def. 我发现我们只需要执行 5 次乘法即可。我还发现了这个 Toom-3 算法，但它使用了我无法理解的多项式。有人可以写下这些乘法以及如何计算有趣的总和吗bd + ae, ce+ bf, cd + be + af

4

1 回答 1

3

基本思想是：数字 237 是多项式 p(x)=2x 2 +3x+7 在点 x=10 处求值。所以，我们可以认为每个整数对应一个多项式，其系数是数字的数字。当我们在 x=10 处评估多项式时，我们得到了我们的数字。

有趣的是，要完全指定 2 次多项式，我们只需要它在 3 个不同点上的值。我们需要 5 个值来完全指定 4 次多项式。

所以，如果我们想将两个 3 位数字相乘，我们可以这样做：

  1. 在 5 个不同的点评估相应的多项式。
  2. 将 5 个值相乘。我们现在有 5 个乘积多项式的函数值。
  3. 从我们在步骤 2 中计算的五个值中找到该多项式的系数。

Karatsuba 乘法的工作方式相同，只是我们只需要 3 个不同的点。我们不是在 10 处评估多项式，而是在 0、1 和“无穷大”处评估多项式，这给出了我们b,a+b,a，d,d+c,c并且相乘得到了你的X,Z,Y.

现在，要把这一切写出来，abc而且def是相当复杂的。在Wikipedia article 中，它实际上做得很好：

  1. 在评估部分，多项式被评估以给出例如c,a+b+c,a-b+c,4a+2b+c,a第一个数字。
  2. 在Pointwise products中，每个数字的对应值相乘，得到：
X = cf
Y = (a+b+c)(d+e+f)
Z = (a+b-c)(d-e+f)
U = (4a+2b+c)(4d+2e+f)
V = ad
  1. 在插值部分，这些值被组合起来为您提供产品中的数字。这涉及求解一个 5x5 线性方程组，因此它再次比 Karatsuba 案例复杂一些。
于 2013-12-05T16:15:06.503 回答