Reducción de la complejidad de la multiplicación polinómica

Question

He estado tratando de figurarlo durante 3 días y no he llegado a ninguna parte. Tengo que implementar la multiplicación polinómica (multiplicar 2 ecuaciones cuadráticas). Se ven como:

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

Pero la parte más complicada es implementarlo en 5 coeficientes múltiples. Lo he reducido a 6. Por ejemplo, a1 * b1, (a1 + a2) * (b1 + b2) cuentan como una multiplicación. Pero (a1 x + a2) * (b1 x + b2) cuenta como 4 (a1 b1, a1 b2, a2 ​​b1, a2 b2).

Answer 1

Es posible que desee echar un vistazo al algoritmo de Toom-3 utilizado en multiprecision multiplicación. Ref: Toom-Cook multiplication.

Básicamente, evalúa cada polinomio en x = -2, -1,0, + 1, infinito usando solo adiciones y cambios, luego multiplique estos 5 valores para obtener los valores del producto en x = -2, - 1,0, + 1, infinito. El último paso es volver a los coeficientes del resultado.

Para P(X) = A*X^2 + B*X + C los valores en x = -2, -1,0, + 1, infinito son:

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 

El producto R(X) = T*X^4 + U*X^3 + V*X^2 + W*X + K, y los valores son:

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 

Usted sabe los valores R(x) = P(x)*Q(x) para x = -2, -1,0, + 1, infinito, y debe resolver este sistema lineal para obtener los coeficientes T, U, V, W, K.

Answer 2

Hmm Creo que encontré la respuesta.

lo reemplaza a (x * (A1 * x + b1) + c1) * (x * (a2 * x + b2) + c2);

y ahí lo tienes 5 multiplicaciones.

Lo siento, esto fue editado, mi primera respuesta fue incorrecta y tenía 9 multiplicaciones de hecho.

Answer 3

También encontré una solución de multiplicación de 6, que podría ayudarte a ti oa otros a resolver.

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

Esto da a continuación:

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