Use an Oberon record containing an active coefficient count and a bounded array of coefficients in ascending power order. A count of zero represents the zero polynomial; a count represents . Trailing zero coefficients are allowed, so the count need not be the degree of a polynomial plus one.
CONST Capacity = 1024;
TYPE Polynomial = RECORD
len: INTEGER;
coeff: ARRAY Capacity OF REAL
END;
PROCEDURE Horner(VAR p: Polynomial; x: REAL): REAL;
VAR i: INTEGER; value: REAL;
BEGIN
i := p.len; value := 0.0;
WHILE i > 0 DO
i := i-1;
value := p.coeff[i] + x*value
END;
RETURN value
END Horner;The representation invariant is , with only indices below
len significant. The parameter is passed by reference to avoid a full record copy; the procedure does not modify it.Let be the original coefficient count. At each guard test the loop invariant isThe empty sum is zero initially. If the old index is , after decrementing and updating,which preserves the loop invariant. The loop variant is , decreasing by one until zero. At exit,This is exactly the right-to-left nesting of Horner's method, matching the supplied right fold. It uses arithmetic operations and additional scalar storage.
REAL gives ordinary floating-point evaluation; the displayed identities specify the ideal arithmetic calculation, with the usual rounding in an actual floating-point implementation.Add polynomials by adding equal-power coefficients, interpreting a missing coefficient as zero. Compute into a local record before assigning the output, so the result may safely be the same actual record as either input.
PROCEDURE Add(VAR p, q, result: Polynomial);
VAR t: Polynomial; i: INTEGER; u, v: REAL;
BEGIN
t.len := p.len;
IF q.len > t.len THEN t.len := q.len END;
i := 0;
WHILE i < t.len DO
u := 0.0; v := 0.0;
IF i < p.len THEN u := p.coeff[i] END;
IF i < q.len THEN v := q.coeff[i] END;
t.coeff[i] := u+v;
i := i+1
END;
result := t
END Add;With , the loop invariant is and, for ,
t.coeff[k] is the sum of the two extended input coefficients at . The loop variant is . The inputs remain unchanged throughout the loop, and at exit every active coefficient is correct. The time complexity is for the active arithmetic; assigning the fixed-capacity record can additionally copy its full capacity.For the product, each pair of input terms contributes . Initialize the active result to zero, then accumulate these pairwise contributions:
PROCEDURE Multiply(VAR p, q, result: Polynomial);
VAR t: Polynomial; i, j, k: INTEGER;
BEGIN
t.len := 0;
IF (p.len > 0) & (q.len > 0) THEN
t.len := p.len + q.len - 1
END;
(* Precondition: t.len <= Capacity. *)
k := 0;
WHILE k < t.len DO
t.coeff[k] := 0.0; k := k+1
END;
IF t.len > 0 THEN
i := 0;
WHILE i < p.len DO
j := 0;
WHILE j < q.len DO
t.coeff[i+j] := t.coeff[i+j]
+ p.coeff[i]*q.coeff[j];
j := j+1
END;
i := i+1
END
END;
result := t
END Multiply;The input representation invariants and the capacity precondition are assumed. No coefficient is accessed when either input is the zero polynomial. The initialization loop invariant says coefficients below are zero; its loop variant is
t.len-k.For positive input lengths , the outer loop invariant says that and each coefficient equalsThe inner loop invariant adds the contributions with and to that sum, while . The update adds exactly the next missing term at index , preserving the inner loop invariant. The loop variants are for the outer loop and for the inner loop. On exit all pairs have contributed, yieldingThe product uses arithmetic operations and a temporary coefficient array of capacity
Capacity. Both operations allow trailing zeros; no extra normalization loop is required. Only the active coefficients are meaningful, so inactive record entries are never read by these operations. As in part (a), floating-point coefficients implement these formulas subject to rounding. Articles by others on the same topic
There are currently no matching articles.