Represent the zero polynomial by ThusThe sentinel is a representation convention, not an assertion that the mathematical degree of the zero polynomial is an ordinary integer. In parts (b)–(e), algebraic correctness uses exact arithmetic on real numbers; ordinary floating-point arithmetic introduces rounding and needs an additional numerical policy if exact zero tests are to be replaced.
degree = -1, with an allocated one-element array whose element is zero. Its coefficient prefix is empty; the spare cell is merely convenient storage. For every nonzero polynomial, require degree >= 0, sufficient allocated capacity, and a nonzero leading polynomial coefficient.PROCEDURE Zero(VAR p: Poly);
BEGIN
p.degree := -1; NEW(p.coeff, 1); p.coeff[0] := 0.0
END Zero;
PROCEDURE Normalize(VAR p: Poly);
BEGIN
WHILE p.degree >= 0 DO
IF p.coeff[p.degree] # 0.0 THEN RETURN END;
DEC(p.degree)
END
END Normalize;Allocate a fresh coefficient array, add matching polynomial coefficients, and normalize to remove any cancellation of leading terms.The loop invariant says that every completed coefficient equals the corresponding coefficient of , treating missing coefficients as zero.
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;Normalize changes no represented polynomial, and can reduce the result to the zero polynomial.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.Use polynomial convolution. If either input is the zero polynomial, return the zero polynomial immediately.Each pair of terms contributes , so the final polynomial coefficient of isWith exact arithmetic on real numbers, the product of the leading nonzero polynomial coefficients is nonzero, giving degree . The nested loops implement precisely this sum, preserve the input coefficient arrays, and take time for nonzero inputs.
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;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 .
Scan the polynomial coefficients from highest degree downward. Omit zero terms, omit coefficient magnitude one on nonconstant terms, print The representation invariant ensures a nonzero polynomial prints at least one term. Constant and retain their coefficients, whereas and omit magnitude one. Thus the requested example printsDifferent
- for negative terms, and print + only before a positive term after the first. A helper prints small integral magnitudes without a decimal suffix; other real numbers use Out.Real.PROCEDURE OutMagnitude(c: REAL);
VAR n: INTEGER;
BEGIN
IF c < MAX(INTEGER) THEN
n := ENTIER(c);
IF c = n THEN Out.Int(n, 0) ELSE Out.Real(c, 0) END
ELSE
Out.Real(c, 0)
END
END OutMagnitude;
PROCEDURE OutPoly(p: Poly);
VAR i: INTEGER; c, magnitude: REAL; first: BOOLEAN;
BEGIN
IF p.degree < 0 THEN Out.String("0"); RETURN END;
first := TRUE; i := p.degree;
WHILE i >= 0 DO
c := p.coeff[i];
IF c # 0.0 THEN
IF c < 0.0 THEN Out.Char("-")
ELSIF ~first THEN Out.Char("+")
END;
magnitude := ABS(c);
IF (i = 0) OR (magnitude # 1.0) THEN
OutMagnitude(magnitude)
END;
IF i > 0 THEN
Out.Char("x");
IF i > 1 THEN Out.Char("^"); Out.Int(i, 0) END
END;
first := FALSE
END;
DEC(i)
END
END OutPoly;Out.Real implementations may use decimal or scientific notation for nonintegral coefficients; either denotes the appropriate real number. The number of coefficient inspections is linear in the stored polynomial degree. Articles by others on the same topic
There are currently no matching articles.