= Solution
Use <polynomial convolution>. If either input is the <zero polynomial>, return the <zero polynomial> immediately.
``
PROCEDURE Mul(VAR prod: Poly; a, b: Poly);
VAR result: Poly; d, i, j: INTEGER;
BEGIN
IF (a.degree < 0) OR (b.degree < 0) THEN
Zero(result)
ELSE
d := a.degree+b.degree;
result.degree := d; NEW(result.coeff, d+1);
FOR i := 0 TO d DO result.coeff[i] := 0.0 END;
FOR i := 0 TO a.degree DO
FOR j := 0 TO b.degree DO
result.coeff[i+j] := result.coeff[i+j]
+ a.coeff[i]*b.coeff[j]
END
END;
Normalize(result)
END;
prod := result
END Mul;
``
Each pair of terms contributes $a_i b_j x^{i+j}$, so the final <polynomial coefficient> of $x^k$ is
$$
\boxed{(ab)_k=\sum_{i+j=k}a_i b_j.}
$$
With exact arithmetic on <real numbers>, the product of the leading nonzero <polynomial coefficients> is nonzero, giving degree $\deg a+\deg b$. The nested loops implement precisely this sum, preserve the input coefficient <arrays>, and take $O((\deg a+1)(\deg b+1))$ time for nonzero inputs.
Back to article page
