我一直在努力想象這個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