Adding polynomials

Two polynomials as chains of terms, largest exponent first. Watch them merge into one chain, with two pairs of terms cancelling out.

⋯39struct pnode *poly_add(struct pnode *a, struct pnode *b)40{41    struct pnode dummy;42    struct pnode *tail = &dummy;43    while (a != NULL && b != NULL) {44        if (a->exp > b->exp) {45            tail->next = a;46            tail = a;47            a = a->next;48        } else if (b->exp > a->exp) {49            tail->next = b;50            tail = b;51            b = b->next;52        } else {53            struct pnode *na = a->next;54            struct pnode *nb = b->next;55            a->coeff += b->coeff;56            free(b);57            if (a->coeff == 0.0) {58                free(a);59            } else {60                tail->next = a;61                tail = a;62            }63            a = na;64            b = nb;65        }66    }67    tail->next = (a != NULL) ? a : b;68    return dummy.next;69}⋯79int main(void)80{81    const struct term ta[4] = { { 5, 4 }, { 3, 2 }, { -2, 1 }, { 1, 0 } };82    const struct term tb[4] = { { 2, 3 }, { -3, 2 }, { 4, 1 }, { -1, 0 } };83    struct pnode *a = from_terms(ta, 4);84    struct pnode *b = from_terms(tb, 4);85    print_poly("A", a);86    print_poly("B", b);87    struct pnode *s = poly_add(a, b);88    print_poly("A + B", s);89    free_poly(s);90    return 0;91}

A merge by exponent

A = 5x⁴ + 3x² − 2x + 1 and B = 2x³ − 3x² + 4x − 1 are stored as lists of term nodes, as in storing a polynomial, largest exponent first:

A: +5x^4 +3x^2 -2x^1 +1x^0
B: +2x^3 -3x^2 +4x^1 -1x^0

Adding them is the merge of merging lists, ordered by falling exponent, with a third case: when the two exponents are equal, the terms are like terms and their coefficients add.

The code and its cost

The merge

poly_add builds the sum on a node dummy on the stack, with tail on the last node so far. While both lists have terms, the term with the larger exponent goes next:

if (a->exp > b->exp) {
    tail->next = a;
    tail = a;
    a = a->next;
} else if (b->exp > a->exp) {
    tail->next = b;
    tail = b;
    b = b->next;
}

No new node is made: the sum reuses the nodes of A and B, so after the call a and b must not be used again.

Equal exponents

Otherwise both nodes hold the same power of x:

struct pnode *na = a->next;
struct pnode *nb = b->next;
a->coeff += b->coeff;
free(b);
if (a->coeff == 0.0) {
    free(a);
} else {
    tail->next = a;
    tail = a;
}
a = na;
b = nb;

A’s node takes the sum and B’s node is freed. If the sum is 0, A’s node is freed too, and nothing is linked. Keeping a term with coefficient 0 would not change the polynomial’s value, but the list would stop being the polynomial’s terms, and every later sum or product would walk past it. na and nb keep the next nodes, since a freed node’s next must not be read.

The coefficients here are small whole numbers, so a->coeff == 0.0 is exact. With measured coefficients, a program treats a sum within a small tolerance of 0 as 0.

The rounds

Both lists are then empty, so tail->next = (a != NULL) ? a : b; attaches NULL, and the sum is

A + B: +5x^4 +2x^3 +2x^1

Three nodes of eight are left; five were freed.

Why the lists must be sorted

Like terms meet only because both lists are in the same order. If B’s x² term came after its x term, the merge would pass A’s 3x² before seeing B’s −3x², and the sum would hold two x² terms.

The cost

Each round moves past at least one term, and the loop stops while one list still has a term, unless the last round used up both at once. So lists of m and n terms take at most m + n − 1 rounds, and no new nodes. A version that must keep A and B intact would allocate a new node for each term of the sum instead, and leave the inputs alone.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic polyadd.c -o polyadd
./polyadd

Worked example

One node left. (x² + 1) + (−x² + 1): the x² terms cancel, and the constants make 2. The sum is the single node 2x⁰.

A polynomial plus its negative. Every pair cancels, every node is freed, and poly_add returns NULL: the zero polynomial, an empty list.

No common exponents. Adding 3 terms to 5 terms with no exponent in common takes at most 3 + 5 − 1 = 7 rounds, when the exponents interleave. If all of A’s exponents are larger than B’s, it takes 3: once A is used up, the rest of B is attached in one step.

Two checks. Which node of A survives as 2x? (A’s −2x node, its coefficient changed to 2.) What does poly_add return for two empty lists? (NULL.)

Where it’s used

Computer algebra. Adding polynomials with many terms is the basic step of symbolic computation.

Error-correcting codes. Decoders add and combine polynomials whose coefficients are bits or bytes.

Filters. Two filters in parallel have the sum of their transfer functions as theirs, and that sum is worked out with polynomial products and additions.

Reference card

Next, multiplying polynomials takes every term times every term.

Platform: C11, gcc on x86-64 Linux: int 4 bytes, double 8, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.