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

Question

我已经想了 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)。

Answer 1

您可能想看看多精度乘法中使用的 Toom-3 算法。引用:Toom-Cook multiplication .

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

对于 P(X) = A*X^2 + B*X + C，x=-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

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