Multiplying Polynomials with fewer coefficient multiplications

Question

Not sure how this works! Apparently it can be done in 5-6 multiplications

Show how to multiply two degree 2 polynomials using fewer multiplications of coefficients than the naive algorithm.

Answer 1

I can't find the way using only 5-6, but here is a way to do it in $7$.

Suppose we are multiplying together $ax^2 + bx + c$ and $dx^2 + ex + f$. Compute $(a+b+c)(d+e+f) = ad + ae + af + bd + be + bf + cd + ce + cf$. This takes $1$ multiplication. Now compute $ad,ae,bd,bf,ce,cf$. This brings up up to $7$. The coefficients of the product are simply $ad, ae + bd, be + af + cd, bf + ce, cf$. By straightfoward additions we know $ad, ae + bd, bf + ce, cf$ already. This coefficient $be + af + cd$ can be computed as $(a+b+c)(d+e+f) - ad - ae - bd - bf - ce - cf$, thus we're done and we only need $7$ multiplications.

Answer 2

Elaborating on Dinoboy's answer, there is a way to do it in 6 multiplications:

compute $ad$, $be$, $cf$, and also $(a+b)(d+e), (b+c)(e+f), (a+c)(d+f)$. Then we have the following identities for the coefficients (where $[x^p] E$ denotes the coefficient of $x^p$ in expression $E$):

\begin{align*} [x^0] (ax^2 + bx + c)(dx^2 + ex + f) &= cf; \\ [x^1] (ax^2 + bx + c)(dx^2 + ex + f) &= ce + bf = (b+c)(e+f) - be - cf; \\ [x^2] (ax^2 + bx + c)(dx^2 + ex + f) &= af + be + cd = be + (a+c)(d+f) - ad - cf; \\ [x^3] (ax^2 + bx + c)(dx^2 + ex + f) &= ae + bd = (a+b)(d+e) - ad - be; \\ [x^4] (ax^2 + bx + c)(dx^2 + ex + f) &= ad. \end{align*}

I am not sure it is possible to do it in 5 multiplications, but I'll let the others try.