= Solution
Allocate a fresh coefficient <array>, add matching <polynomial coefficients>, and normalize to remove any cancellation of leading terms.
``
PROCEDURE Add(VAR sum: Poly; a, b: Poly);
VAR result: Poly; d, cap, i: INTEGER;
BEGIN
d := a.degree;
IF b.degree > d THEN d := b.degree END;
cap := d+1; IF cap < 1 THEN cap := 1 END;
result.degree := d; NEW(result.coeff, cap);
result.coeff[0] := 0.0;
FOR i := 0 TO d DO
result.coeff[i] := 0.0;
IF i <= a.degree THEN
result.coeff[i] := result.coeff[i] + a.coeff[i]
END;
IF i <= b.degree THEN
result.coeff[i] := result.coeff[i] + b.coeff[i]
END
END;
Normalize(result); sum := result
END Add;
``
The <loop invariant> says that every completed coefficient equals the corresponding coefficient of $a+b$, treating missing coefficients as zero. `Normalize` changes no represented <polynomial>, and can reduce the result to the <zero polynomial>.
$$
\boxed{(a+b)_i=a_i+b_i;\quad\text{time }O(1+\max(\deg a,\deg b)).}
$$
Neither input coefficient <array> is changed. Output variables are separate from input record variables; the fresh result also remains safe when the two inputs share a coefficient <array>.
Back to article page
