多项式乘法复杂度降低
我已经想了三天了，但一无所获。我必须实现多项式乘法（乘以 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)。
I have been trying to figure tis ou for 3 days and have not gotten anywhere. I have to implement polynomial multiplication (multiply 2 quadratic equations). They look like:
( a1 x^2 + b1 x + c1 ) * ( a2 x^2 + b2 x + c2 );
But the trickier part is to implement it in 5 coefficient multplications. I have reduced it to 6. For eg, a1 * b1, ( a1 + a2 ) * ( b1 + b2 ) count as one multiplication. But (a1 x + a2 ) * ( b1 x + b2 ) count as 4 (a1 b1, a1 b2, a2 b1, a2 b2).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可能想看看多精度乘法中使用的 Toom-3 算法。参考：Toom-Cook 乘法。
基本上，您仅使用加法和移位来计算 x=-2,-1,0,+1,无穷大处的每个多项式，然后将这 5 个值相乘以获得 x=-2,-1,0 处的乘积值， +1，无穷大。最后一步是返回结果的系数。
对于 P(X) = A*X^2 + B*X + C，x=-2,-1,0,+1,无穷大处的值为：
乘积
R( X) = T*X^4 + U*X^3 + V*X^2 + W*X + K，其值为：您知道值
R(x) = P( x)*Q(x)对于 x=-2,-1,0,+1,无穷大，您必须求解这个线性系统以获得系数 T,U,V,W,K。You may want to have a look at the Toom-3 algorithm used in multiprecision multiplication. Ref: Toom-Cook multiplication.
Basically, you eval each polynomial at x=-2,-1,0,+1,infinity using only additions and shifts, then multiply these 5 values to get the values of the product at x=-2,-1,0,+1,infinity. The final step is to get back to the coefficients of the result.
For
P(X) = A*X^2 + B*X + Cthe values at x=-2,-1,0,+1,infinity are:The product
R(X) = T*X^4 + U*X^3 + V*X^2 + W*X + K, and the values are:You know the values
R(x) = P(x)*Q(x)for x=-2,-1,0,+1,infinity, and you have to solve this linear system to get coefficients T,U,V,W,K.嗯，我想我找到了答案。
将其替换为 ( x * ( A1*x + b1 ) + c1 ) * ( x *( a2 * x + b2 ) + c2 );
这样你就得到了 5 次乘法。
抱歉，此内容已被编辑，我的第一个答案是错误的，并且确实有 9 次乘法。
Hmm I think I found the answer.
you replace it to ( x * ( A1*x + b1 ) + c1 ) * ( x *( a2 * x + b2 ) + c2 );
and there you have it 5 multiplications .
Sorry this was edited , my first answer was wrong and had 9 multiplications indeed.
我还找到了一个6乘法的解决方案，可以帮助你自己或其他人解决。
然后给出：
I have also found a 6 multiplication solution, which could help yourself or others solve.
This then gives :