Engineering / Mathematics — Polynomial Algorithms
Basic Polynomial Arithmetic
Representation of polynomials, addition, multiplication and division costs, and the dense versus sparse choice.
Executive summary
Polynomial arithmetic mirrors integer arithmetic with degree replacing length, and without carries — which makes it simpler.
The representation choice between dense coefficient arrays and sparse term lists is the main implementation decision and depends on the expected density.
Learning objectives
- Compare dense and sparse representations.
- State the costs of the basic operations.
- Identify where polynomial arithmetic is simpler than integer arithmetic.
01Representation
| Representation | Storage | Best for |
|---|---|---|
| Dense array | deg + 1 coefficients | Most coefficients non-zero |
| Sparse term list | Pairs of exponent and coefficient | Few non-zero terms, high degree |
| Bit vector over F₂ | One bit per coefficient | Binary fields; word-parallel operations |
Dense is the default and is what the cost bounds below assume. Sparse representations win when the number of terms is much smaller than the degree, as in the sparse interpolation problems arising in computer algebra.
02Operation costs
- Addition, subtraction
O(n)Coefficientwise; no carries - Multiplication, schoolbook
O(mn)Every coefficient pair - Multiplication, Karatsuba
O(n^1.585)Same recursion as for integers - Division with remainder
O((m−n+1)n)Requires invertible leading coefficient - Evaluation at a point
O(n)Horner's rule - Multipoint evaluation
O(n log² n)Subproduct tree; far better than n evaluations
The absence of carries makes polynomial arithmetic genuinely simpler than integer arithmetic. Coefficients do not interact across positions, so multiplication is a clean convolution and the algorithms have no propagation logic.
03Horner's rule and evaluation
Horner evaluation
coefficients a₀..a_n, point xf(x)- Set r = a_n, the leading coefficient.
- For i from n−1 down to 0:
- Set r = r · x + aᵢ.
- Return r.
n multiplications and n additionsHorner's rule is optimal for evaluating a single dense polynomial at a single point — no method uses fewer multiplications in general. It also has the useful property of computing the quotient by X − x as a by-product, since the intermediate values are exactly the quotient coefficients.
04Frequently asked questions
Why is polynomial multiplication easier than integer multiplication?
Because there are no carries. Coefficients can grow without affecting neighbouring positions, so the convolution is exact and no propagation pass is needed. The same asymptotic methods apply to both.
When does sparse representation pay off?
When the term count is much smaller than the degree — a polynomial like X^{1000} + 1 has two terms and would waste 999 slots dense. Sparse multiplication cost depends on the term counts rather than the degrees.
Is Horner's rule numerically stable?
Over the reals it is the standard choice and reasonably well behaved. Over finite fields the question does not arise, since arithmetic is exact.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 398-401.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.