algorithm - toom-cook 第 3 部分分辨率多项式

Question

今天，我来求助于一道小数学题。 我提出了一个程序，该程序计算具有任意长度数字的方程式。 https://bitbucket.org/Dermenslof/bistro 在优化方面，我正在为两个操作数超过 10,000 位的运算集成乘法算法。 这个算法是 toom-cook 第 3 部分。 以下是原则: 我们要进行如下操作:123 456 789 * 987 654 321 我们将把这两个数字分成三部分:

-------------------           ------------------
| 123 | 456 | 789 |           | x2  | x1  | x0 |
-------------------     =     ------------------
| 987 | 654 | 321 |           | y2  | y1  | y0 |
-------------------           ------------------

我们被告知:

the result P(X) = A(X) * B(X)

A(X) = x2 * X² + x1 * X + x0
B(X) = y2 * X² + y1 * X + y0

P(X) = p4 * X⁴ + p3 * X³ + p2 * X² + p1 * X¹ + p0

由此我们可以得到:

X = -2   A = 369      B = 2961      A * B = AB(2)   = 1092609      = (4 * x2 + 2 * x1 + x0) * (4 * y2 + 2 * y1 + y0)
X = -1   A = 456      B = 654       A * B = AB(-1)  = 298224       = (x2 - x1 + x0) * (y2 - y1 + y0)
X = 0    A = 789      B = 321       A * B = AB(0)   = 253269       = x0 * y0 (gives us directly p0)
X = 1    A = 1368     B = 1962      A * B = AB(1)   = 2684016      = (x2 + 2 * x1 + x0) * (y2 + 2 * y2 + y0)
X = 2    A = 2193     B = 5577      A * B = AB(2)   = 12230361     = (4 * x2 + 2 * x1 + x0) * (4 * y2 + 2 * y1 + y0)
X = inf  A = 123      B = 987       B * B = AB(inf) = 121401       = x2 * y2 (gives us directly p4)

我们推断:

AB(-2) = 16 * p4 - 8 * p3 + 4 * p2 + 2 * p1 + p0
AB(-1) = p4 - p3 + p2 - p1 + p0
AB(0)  = p0
AB(1)  = p4 + p3 + p2 + p1 + p0
AB(2)  = 16 * p4 + 8 * p3 + 4 * p2 + 2 * p1 + p0

我们现在必须隔离 p3、p2 和 p1

p3 = (2 * AB(-1) + AB(2) - 18p4 - 6p2 - 3p0) / 6
p2 = (AB(1-) + AB(1) - 2 * p4 - 2 * p0) / 2
p1 = AB(-1) - p4 - p3 - p2 - p0

我的结果是:

  121 401 000 000 000 000
+ 000 530 514 000 000 000
+ 000 001 116 450 000 000
+ 000 000 000 662 382 000
+ 000 000 000 000 253 269
-------------------------
  121 932 631 112 635 269

一切正常。 现在让我烦恼的是:

p3 = (2 * AB(-1) + AB(2) - 18 * p4 - 6 * p2 - 3 * p0) / 6

由于技术原因，我们发现除法的计算速度非常慢。除以 2 或除以基数的幂不是问题。 但是将一个可能非常大的数字除以 6 是一个巨大的数字。 所以你必须找到 X 的不同值，或者这个多项式的另一种形式以获得更合适的方程。

我得到了一些信息，显然以下方程式更合适: ( https://stuff.mit.edu/afs/athena/astaff/source/src-9.0/third/gmp/doc/multiplication )

AB(0)            = p0
16 * AB(1/2)     = p4 + 2 * p3 + 4 * p2 + 8 * p1 + 16 * p0
AB(1)            = p4 + p3 + p2 + p1 + p0
AB(2)            = 16 * p4 + 8 * p3 + 4 * p2 + 2 * p1 + p0
AB(inf)          = p4

这就是我请求你帮助的地方，我无法从这些等式中分离出 p3、p2 和 p1 预先感谢那些对这个问题感兴趣的人

Answer 1

我无法从这些[方程式中分离出] p3、p2 和 p1
我开始编辑你的问题以修复奇数符号错误(不是唯一的一个；参见AB(-2))，继续对齐“ps”(发现结果与您链接的旧 GMP 文档中的表格非常相似):

  AB(0)   =                            p0
16AB(1/2) =   p4 + 2p3 + 4p2 + 8p1 + 16p0
  AB(1)   =   p4 +  p3 +  p2 +  p1 +   p0
  AB(2)   = 16p4 + 8p3 + 4p2 + 2p1 +   p0
  AB(inf) =   p4

“显然，我们可以”减去第一行和最后一行的适当倍数得到

h = 2p3 + 4p2 + 8p1
u =  p3 +  p2 +  p1
d = 8p3 + 4p2 + 2p1

类似地，10u -h-d 给出 6p2，2h-12u+ d 6p1，并且对称地 h-12u+2d 6p3.
这仍然需要至少除以 6(或三，如果你认为/2 “免费”) - 据我所知，它是 state of the art截至 17 年底。