我一直在努力想象这个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）。
你可能想看看在多倍乘用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，无穷是：
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，无穷大，值为R(x) = P(x)*Q(x)，并且您必须求解该线性系统以获得系数T，U，V，W，K。
嗯我想我找到了答案。
您将其替换为（x *（A1 * x + b1）+ c1）*（x *（a2 * x + b2）+ c2）;
并且你有5次乘法。
对不起，这是编辑，我的第一个答案是错误的，并有9次乘法的确。
我认为他算作9次乘法。 – ThomasMcLeod 2011-02-16 06:35:18
是这是9次乘法。如果你要我指定，我会去做。但它很明显。 – Brahadeesh 2011-02-16 06:36:56
@Brahadeesh这并不明显。该公式中有五个乘法。你已经将问题标记为最佳，但你似乎坚持扩展你的方程。当你想要一些不太理想的东西时，就是这样做的。 – 2011-02-16 07:02:30
我也找到了一个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
你可以发布你减少6次乘法吗？ – threenplusone 2011-02-16 07:18:32