Réduction de la complexité de la multiplication polynomiale

Question

J'ai essayé de vous comprendre pendant 3 jours et je n'ai obtenu aucun résultat. Je dois implémenter la multiplication polynomiale (multiplier 2 équations quadratiques). Ils ressemblent à:

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

Mais la partie la plus délicate est de l'implémenter dans 5 multplications de coefficient. Je l'ai réduit à 6. Par exemple, a1 * b1, (a1 + a2) * (b1 + b2) compte comme une multiplication. Mais (a1 x + a2) * (b1 x + b2) compte comme 4 (a1 b1, a1 b2, a2 ​​b1, a2 b2).

Answer 1

Vous pouvez jeter un oeil à l'algorithme Toom-3 utilisé dans Multiprécision multiplication. Réf: Toom-Cook multiplication. Fondamentalement, vous évaluez chaque polynôme à x = -2, -1,0, + 1, infini en utilisant seulement des additions et des décalages, puis multipliez ces 5 valeurs pour obtenir les valeurs du produit à x = -2, - 1,0, + 1, l'infini. La dernière étape consiste à revenir aux coefficients du résultat.

Pour P(X) = A*X^2 + B*X + C les valeurs à x = -2, -1,0, + 1, l'infini sont:

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 

Le produit R(X) = T*X^4 + U*X^3 + V*X^2 + W*X + K, et les valeurs sont:

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 

Vous savez les valeurs R(x) = P(x)*Q(x) pour x = -2, -1,0, + 1, infini, et vous devez résoudre ce système linéaire pour obtenir les coefficients T, U, V, W, K.

Answer 2

Hmm Je pense avoir trouvé la réponse. Vous le remplacez par (x * (A1 * x + b1) + c1) * (x * (a2 * x + b2) + c2);

et là vous l'avez 5 multiplications.

Désolé cela a été édité, ma première réponse était erronée et avait 9 multiplications en effet.

Answer 3

J'ai également trouvé une solution de multiplication de 6, qui pourrait aider vous-même ou d'autres résolvent.

M1 := (a1 + b1)*(a2 + b2) 
M2 := (a1 + c1)*(a2 + c2) 
M3 := (b1 + c1)*(b2 + c2) 
M4 := a1 * a2 
M5 := b1 * b2 
M6 := c1 * c2 

Cela donne alors:

M4 * x^4 + 
(M1 - M4 - M5) * x^3 + 
(M2 - M4 - M6 + M5) * x^2 + 
(M3 - M5 - M6) * x + 
M6