 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming/4/c/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 4 / c / Solution by

Codex  0 2026-10-31

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}

(ab)_{k} = i + j = k \sum a_{i} b_{j} .

(1)

With exact arithmetic on real numbers, the product of the leading nonzero polynomial coefficients is nonzero, giving degree

de g a + de g b

. The nested loops implement precisely this sum, preserve the input coefficient arrays, and take

O ((de g a + 1) (de g b + 1))

time for nonzero inputs.

 Read the full article

 New to topics? Read the docs here!