Require a nonzero divisor. Polynomial long division repeatedly subtracts the multiple of that cancels the leading term of the current polynomial remainder. Use fresh arrays for both outputs.The loop invariant is the polynomial identity . Setting and replaces by and by , preserving this identity. The leading coefficient of that difference is exactly zero, so setting its stored value to zero and decreasing
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;degree implements its exact cancellation. Each iteration strictly decreases the degree of the polynomial remainder.At termination,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 , the work is .
Articles by others on the same topic
There are currently no matching articles.