TYPE
poly = POINTER TO term;
term = RECORD
coeff: T;
power: INTEGER;
next: poly
END;NIL denotes the zero polynomial. Each power is a nonnegative integer, and the intended sparse representation omits zero coefficients. No sorted-order assumption is needed for the operations below. Coefficients are treated as values with equality to zero, addition and multiplication; mutable coefficient objects would need the corresponding copying discipline.Remove zero nodes while retaining every nonzero node and its order:
PROCEDURE normalise(VAR r: poly);
VAR p,prev: poly;
BEGIN
p := r; prev := NIL;
WHILE p # NIL DO
IF p.coeff = 0 THEN
IF prev = NIL THEN r := p.next
ELSE prev.next := p.next END
ELSE
prev := p
END;
p := p.next
END
END normalise;At each step, the processed prefix contains precisely the nonzero nodes already examined, and
prev is its final node or NIL. Thus removal at the head, consecutive removals and removal of every node are handled. This linked-list deletion pass takes linear time in the original node count. It does not by itself combine duplicate powers.Use a helper whose first argument is a private result list. It adds a coefficient to an existing power, deleting a cancellation, or allocates a new node:
accumulate(VAR r: poly; c: T; e: INTEGER):
if c == 0: return
p = r; prev = NIL
while p != NIL and p.power != e:
prev = p; p = p.next
if p == NIL:
q = new term(c,e,r)
r = q
else:
p.coeff = p.coeff+c
if p.coeff == 0:
if prev == NIL: r = p.next
else: prev.next = p.next
addPoly(x,y):
r = NIL
p = x
while p != NIL:
accumulate(r,p.coeff,p.power)
p = p.next
p = y
while p != NIL:
accumulate(r,p.coeff,p.power)
p = p.next
return rHere
VAR applies to the list variable r; coefficients and powers are value arguments. The helper preserves one node per power and excludes zero coefficients. After each loop iteration, the result represents exactly the processed input terms. Every result node is fresh, so neither input's nodes or links are changed, even if the two inputs alias or share tails. For unsorted inputs of lengths , a simple worst-case bound is for these repeated scans.Distribute every term of one input across every term of the other, using the same private accumulator:
mulPoly(x,y):
r = NIL
p = x
while p != NIL:
q = y
while q != NIL:
accumulate(r,p.coeff*q.coeff,p.power+q.power)
q = q.next
p = p.next
return rThe inner-loop invariant says that the current result contains all products from earlier nodes of
x, plus the current x node multiplied by the processed prefix of y. The outer invariant is the corresponding statement for completed rows of products. The distributive property then proves correctness. Powers add, equal powers combine, zero products and cancellations disappear. Both input lists are only read, and an empty input gives the zero polynomial.There are coefficient products. If at most result nodes are present at a time, the simple unsorted accumulator costs , with ; it is correct without claiming a linear-time multiplication.
The coefficient type is not assumed to be ordered, so do not require a sign or absolute-value operation beyond the supplied output routine. Parenthesize coefficients to keep negative or compound values unambiguous:
OutPoly(p):
first = true
while p != NIL:
if p.coeff != 0:
if not first: Out.String("+")
Out.String("("); OutT(p.coeff); Out.String(")")
if p.power != 0:
Out.String("*x")
if p.power != 1:
Out.String("^"); Out.Int(p.power)
first = false
p = p.next
if first: OutT(0)For example, the representation in the question can print
(-1)+(1)*x^2, which denotes the same polynomial. If additionally provides ordered-real sign operations, cosmetic suppression of +(-...) and unit coefficients can produce -1+x^2. The generic routine already handles the zero polynomial and preserves the represented value without introducing those extra assumptions.Maintaining strictly decreasing powers makes output deterministic and avoids sorting a copy at every print. More significantly, two sorted sparse polynomials can be added by a merge algorithm in time, combining equal powers and dropping cancellations as they are encountered.
The cost is maintaining that order during construction and updates. A linked-list insertion can require a linear search, while initially sorting unsorted terms costs comparisons before combining duplicates. Multiplication still has to generate and combine term products; sorted storage does not make it linear automatically, though it enables merging ordered partial products. Keeping the invariant is attractive when arithmetic and printing are frequent; sorting only when printing can be simpler for infrequently displayed, frequently appended data.
Articles by others on the same topic
There are currently no matching articles.