algorithm - 多项式乘法复杂度降低

Question

我一直试图弄清楚 tis ou 3 天，但没有得到任何地方。我必须实现多项式乘法（乘以 2 个二次方程）。他们看着像是：

( a1 x^2 + b1 x + c1 ) * ( a2 x^2 + b2 x + c2 );

但更棘手的部分是在 5 个系数乘法中实现它。我已将其减少到 6。例如，a1 * b1, ( a1 + a2 ) * ( b1 + b2 ) 算作一次乘法。但是 (a1 x + a2 ) * ( b1 x + b2 ) 算作 4 (a1 b1, a1 b2, a2 b1, a2 b2)。

score 3 · Accepted Answer

嗯，我想我找到了答案。

您将其替换为 ( x * ( A1*x + b1 ) + c1 ) * ( x *( a2 * x + b2 ) + c2 );

那里有 5 次乘法。

抱歉，这是经过编辑的，我的第一个答案是错误的，确实有 9 次乘法。

score 3 · Accepted Answer

您可能想查看多精度乘法中使用的 Toom-3 算法。参考：Toom-Cook 乘法。

基本上，您只使用加法和移位来评估 x=-2,-1,0,+1,infinity 处的每个多项式，然后将这 5 个值相乘以获得 x=-2,-1,0 处的乘积值， +1，无穷大。最后一步是返回结果的系数。

对于P(X) = A*X^2 + B*X + Cx=-2,-1,0,+1,infinity 处的值是：

P(-2) = 4*A - 2*B + C  (the products here are bit shifts)
P(-1) = A - B + C
P( 0) = C
P(+1) = A + B + C
P(oo) = A

产品R(X) = T*X^4 + U*X^3 + V*X^2 + W*X + K，其值为：

R(-2) = 16*T - 8*U + 4*V - 2*W + K
R(-1) = T - U + V - W + K
R( 0) = K
R(+1) = T + U + V + W + K
R(oo) = T

你知道R(x) = P(x)*Q(x)x=-2,-1,0,+1,infinity 的值，你必须求解这个线性系统才能得到系数 T,U,V,W,K。

score 0 · Accepted Answer

我还找到了一个 6 乘法解决方案，可以帮助自己或其他人解决。

M1 := (a1 + b1)*(a2 + b2)  
M2 := (a1 + c1)*(a2 + c2)  
M3 := (b1 + c1)*(b2 + c2)  
M4 := a1 * a2  
M5 := b1 * b2  
M6 := c1 * c2

然后给出：

M4 * x^4 + 
(M1 - M4 - M5) * x^3 + 
(M2 - M4 - M6 + M5) * x^2 +
(M3 - M5 - M6) * x +
M6

3 回答 3