 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming/4/d/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 / d / Solution by

Codex  0 2026-10-31

Require a nonzero divisor. Polynomial long division repeatedly subtracts the multiple of

b

that cancels the leading term of the current polynomial remainder. Use fresh arrays for both outputs.

PROCEDURE DivMod(VAR div, mod: Poly; a, b: Poly);
VAR q, r: Poly; cap, i, j, k, old: INTEGER; t: REAL;
BEGIN
  ASSERT(b.degree >= 0);
  cap := a.degree+1; IF cap < 1 THEN cap := 1 END;
  r.degree := a.degree; NEW(r.coeff, cap);
  r.coeff[0] := 0.0;
  FOR i := 0 TO a.degree DO r.coeff[i] := a.coeff[i] END;
  IF a.degree < b.degree THEN
    Zero(q)
  ELSE
    q.degree := a.degree-b.degree;
    NEW(q.coeff, q.degree+1);
    FOR i := 0 TO q.degree DO q.coeff[i] := 0.0 END;
    WHILE r.degree >= b.degree DO
      old := r.degree; k := old-b.degree;
      t := r.coeff[old]/b.coeff[b.degree];
      q.coeff[k] := q.coeff[k]+t;
      FOR j := 0 TO b.degree-1 DO
        r.coeff[k+j] := r.coeff[k+j]-t*b.coeff[j]
      END;
      r.coeff[old] := 0.0;
      DEC(r.degree); Normalize(r)
    END;
    Normalize(q)
  END;
  div := q; mod := r
END DivMod;

The loop invariant is the polynomial identity

a = q b + r

. Setting

t = r_{old} / b_{d e g b}

and

k = old - de g b

replaces

q

q + t x^{k}

and

r

r - t x^{k} b

, preserving this identity. The leading coefficient of that difference is exactly zero, so setting its stored value to zero and decreasing degree implements its exact cancellation. Each iteration strictly decreases the degree of the polynomial remainder.

At termination,

a = div b + mod, mod = 0 or de g mod < de g b .

(1)

The zero polynomial dividend, a lower-degree dividend, and a constant divisor are all covered. Division by the zero polynomial is undefined. The two output record variables must be distinct and separate from the input record variables; no input coefficient array is written. For

de g a \geq de g b

, the work is

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

 Read the full article

 New to topics? Read the docs here!