5

私は 3 日間これを理解しようとしてきましたが、どこにも行きませんでした。多項式の乗算 (2 つの二次方程式の乗算) を実装する必要があります。それらは次のようになります。

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

しかし、よりトリッキーな部分は、5 つの係数乗算で実装することです。これを 6 に減らしました。たとえば、a1 * b1、( a1 + a2 ) * ( b1 + b2 ) は 1 つの乗算としてカウントされます。ただし、(a1 x + a2 ) * ( b1 x + b2 ) は 4 (a1 b1、a1 b2、a2 b1、a2 b2) としてカウントされます。

4

3 に答える 3

3

倍精度乗算で使用される Too-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

productR(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 を取得する必要があります。

于 2011-02-16T08:26:49.573 に答える
3

うーん、私は答えを見つけたと思います。

これを ( x * ( A1*x + b1 ) + c1 ) * ( x *( a2 * x + b2 ) + c2 ) に置き換えます。

5 つの乗算があります。

申し訳ありませんが、これは編集されました。私の最初の答えは間違っていて、実際には9回の乗算がありました。

于 2011-02-16T06:29:09.037 に答える
0

また、自分自身や他の人が解決するのに役立つ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
于 2011-02-16T07:53:54.190 に答える