Polynomial multiplication complexity reduction

Question

I have been trying to figure tis ou for 3 days and have not gotten anywhere. I have to implement polynomial multiplication (multiply 2 quadratic equations). They look like:

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

But the trickier part is to implement it in 5 coefficient multplications. I have reduced it to 6. For eg, a1 * b1, ( a1 + a2 ) * ( b1 + b2 ) count as one multiplication. But (a1 x + a2 ) * ( b1 x + b2 ) count as 4 (a1 b1, a1 b2, a2 b1, a2 b2).

Answer 1

You may want to have a look at the Toom-3 algorithm used in multiprecision multiplication. Ref: Toom-Cook multiplication.

Basically, you eval each polynomial at x=-2,-1,0,+1,infinity using only additions and shifts, then multiply these 5 values to get the values of the product at x=-2,-1,0,+1,infinity. The final step is to get back to the coefficients of the result.

For P(X) = A*X^2 + B*X + C the values at x=-2,-1,0,+1,infinity are:

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

The product R(X) = T*X^4 + U*X^3 + V*X^2 + W*X + K, and the values are:

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

You know the values R(x) = P(x)*Q(x) for x=-2,-1,0,+1,infinity, and you have to solve this linear system to get coefficients T,U,V,W,K.

Answer 2

Hmm I think I found the answer.

you replace it to ( x * ( A1*x + b1 ) + c1 ) * ( x *( a2 * x + b2 ) + c2 );

and there you have it 5 multiplications .

Sorry this was edited , my first answer was wrong and had 9 multiplications indeed.