Multiplying Polynomials, and What the Representation Costs
Chapter Twenty-Five
Syllabus topic Module 1, "Linked Structures: applications of linked list like polynomial equation"
Pages 74 to 76 of 411
In one line
Multiplying two polynomials means multiplying every term of one by every term of the other and collecting the terms that share an exponent, which the ordered list makes awkward in a way addition did not.
The arithmetic
To multiply, take each term of P against each term of Q. Coefficients multiply; exponents add.
(5x^4) x (2x^3) = 10x^7
(5x^4) x (1x^0) = 5x^4
So P with m terms and Q with n terms produces m times n partial products. Those partial products then have to be collected, because many of them will share an exponent.
Why this is harder than addition
Addition walked both lists once and the answer came out already in order. Multiplication does not have that luxury:
The partial products arrive out of order. Taking P's terms outer and Q's inner gives exponents 7, 4, then 6, 3, and so on. Nothing is sorted.
Many share an exponent and must be combined. 5x^4 times 2x^0 and 5x^2 times 2x^2 both land on x^4.
So multiplication is m times n multiplications followed by a collection step, and the collection is where the representation makes you work.
Built and run
The approach here is the one to write in an examination: multiply one term of P into a running answer using the addition of chapter 24, which keeps the answer ordered and collected at every step.
class Term:
def __init__(self, coefficient, exponent, next_term=None):
self.coefficient = coefficient
self.exponent = exponent
self.next = next_term
class Polynomial:
def __init__(self, terms=()):
self.head = None
for coefficient, exponent in sorted(terms, key=lambda t: t[1]):
if coefficient != 0:
self.head = Term(coefficient, exponent, self.head)
def terms(self):
out, walk = [], self.head
while walk is not None:
out.append((walk.coefficient, walk.exponent))
walk = walk.next
return out
def evaluate(self, x):
total, walk = 0, self.head
while walk is not None:
total += walk.coefficient * (x ** walk.exponent)
walk = walk.next
return total
def __str__(self):
if self.head is None:
return "0"
parts, walk = [], self.head
while walk is not None:
c, e = walk.coefficient, walk.exponent
parts.append("%d" % c if e == 0 else
("%dx" % c if e == 1 else "%dx^%d" % (c, e)))
walk = walk.next
return " + ".join(parts).replace("+ -", "- ")
def add(p, q):
result, tail = Polynomial(), None
a, b = p.head, q.head
def attach(coefficient, exponent):
nonlocal tail
node = Term(coefficient, exponent)
if tail is None:
result.head = node
else:
tail.next = node
tail = node
while a is not None and b is not None:
if a.exponent > b.exponent:
attach(a.coefficient, a.exponent)
a = a.next
elif b.exponent > a.exponent:
attach(b.coefficient, b.exponent)
b = b.next
else:
total = a.coefficient + b.coefficient
if total != 0:
attach(total, a.exponent)
a, b = a.next, b.next
for walk in (a, b):
while walk is not None:
attach(walk.coefficient, walk.exponent)
walk = walk.next
return result
def multiply(p, q):
"""Multiply, counting the term multiplications performed."""
answer, products = Polynomial(), 0
a = p.head
while a is not None:
row, b = [], q.head
while b is not None:
row.append((a.coefficient * b.coefficient, a.exponent + b.exponent))
products += 1
b = b.next
answer = add(answer, Polynomial(row))
a = a.next
return answer, products
p = Polynomial([(5, 2), (3, 0)])
q = Polynomial([(2, 1), (4, 0)])
product, products = multiply(p, q)
print("P(x) =", p)
print("Q(x) =", q)
print("P x Q =", product)
print("term multiplications:", products)
print()
print("independent check at x = 3:")
print(" P(3) x Q(3) =", p.evaluate(3), "x", q.evaluate(3), "=", p.evaluate(3) * q.evaluate(3))
print(" the product polynomial at 3 gives", product.evaluate(3))
print(" they agree:", p.evaluate(3) * q.evaluate(3) == product.evaluate(3))
print()
big_p = Polynomial([(1, 4), (1, 3), (1, 2), (1, 1), (1, 0)])
big_q = Polynomial([(1, 2), (1, 1), (1, 0)])
big, big_products = multiply(big_p, big_q)
print("(%s) x (%s)" % (big_p, big_q))
print(" =", big)
print(" term multiplications:", big_products, "= 5 x 3")
print(" terms in the answer :", len(big.terms()))Multiplying Polynomials, and What the Representation Costs
P(x) = 5x^2 + 3
Q(x) = 2x + 4
P x Q = 10x^3 + 20x^2 + 6x + 12
term multiplications: 4
independent check at x = 3:
P(3) x Q(3) = 48 x 10 = 480
the product polynomial at 3 gives 480
they agree: True
(1x^4 + 1x^3 + 1x^2 + 1x + 1) x (1x^2 + 1x + 1)
= 1x^6 + 2x^5 + 3x^4 + 3x^3 + 3x^2 + 2x + 1
term multiplications: 15 = 5 x 3
terms in the answer : 7The small product can be checked by hand: (5x^2 + 3)(2x + 4) is 10x^3 + 20x^2 + 6x + 12. The program agrees, and the evaluation check at x = 3 agrees independently.
The larger one shows the shape: 5 terms times 3 terms is 15 multiplications, and the answer has 7 terms, because the 15 partial products collapsed onto 7 distinct exponents.
The cost, and the honest verdict
Multiplication is O(m n) multiplications, and that is unavoidable: every pair of terms contributes.
But the collection costs more than it should here. Each row of partial products is merged into the answer, and the answer grows, so the merging is roughly O(m n) again in the best arrangement and worse in a careless one. Written naively, appending every partial product and then sorting and collecting, it is O(m n log(m n)).
Now compare the array representation, indexed by exponent. Multiplication there is:
for each i, for each j: result[i + j] = result[i + j] + p[i] x q[j]
Two loops, no merging, no ordering to maintain, no cancellation to check. It is simpler and faster for a dense polynomial, because the array's index does the collecting for free.
Multiplying Polynomials, and What the Representation Costs
So the honest verdict, and the one worth writing in an answer:
| Operation | Linked list | Array |
|---|---|---|
| Storage, sparse | excellent | terrible |
| Storage, dense | wasteful (an address per term) | excellent |
| Addition | O(m + n), natural | O(larger degree) |
| Multiplication | O(m n) plus awkward collection | O(m n), trivially simple |
| Evaluation | O(terms) | O(degree) |
The linked representation is chosen for sparse polynomials and for addition. It is not chosen because it is better at everything, and multiplication is where it shows.
That is the pattern this whole paper keeps repeating. A structure is a bargain, and part of knowing it is knowing what you paid.
Quick revision
- Multiplying: coefficients multiply, exponents add. m terms times n terms gives m n partial products.
- The partial products arrive out of order and many share an exponent, so they must be collected.
- The clean method is to multiply one term of P into a running answer using polynomial addition, which
keeps the answer ordered and collected throughout.
- Cost is O(m n) multiplications, plus collection; a naive approach adds a sort and becomes
O(m n log(m n)).
- The array representation multiplies with two loops and
result[i + j] += p[i] * q[j], with the index doing the collecting for free, so it is simpler and faster for dense polynomials. - The linked representation is chosen for sparseness and for addition, not because it is better at everything.
Test yourself
1. What happens to coefficients and exponents when two terms are multiplied? The coefficients multiply and the exponents add.
2. How many partial products does multiplying an m term by an n term polynomial give? m times n.
3. Why is multiplication harder on a linked list than addition was? The partial products come out unordered and many share an exponent, so they must be collected, whereas addition's single merge produced an already ordered, already collected answer.
4. Describe the clean method used in this chapter. Multiply each term of P by the whole of Q to make a row, and add that row into a running answer using polynomial addition, which keeps the answer ordered and collected at every step.
5. Write the array version of polynomial multiplication in one line, and say why it is simpler. result[i + j] = result[i + j] + p[i] * q[j] over all i and j. The index collects terms of equal exponent automatically, so there is no merging, no ordering and no cancellation check.
6. State the honest verdict on the two representations. The linked list is for sparse polynomials and for addition; the array is better for dense polynomials and for multiplication. The linked representation is a bargain, not an improvement in every direction.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.