sreejithmvarma.in

PCCST303 · Module 1: Basic Concepts of Data Structures

Polynomial Representation

A polynomial is just a sum of terms, each with a coefficient and a power of x, and here's how to hold those terms in an array so a program can work with them.

Breaking a term into two numbers

Take:

5x⁴ + 3x² + 7

Every term is fully described by two numbers:

coefficient, exponent

In 5x⁴, the coefficient is 5 and the exponent is 4. Once a program can store (coefficient, exponent) pairs for every term, it has everything it needs to represent, add, or evaluate the polynomial.

Simple representation: one array indexed by exponent

The most direct approach uses a single array where the index is the exponent and the value stored there is the coefficient.

For 5x⁴ + 3x² + 7:

Value (coefficient)Index (exponent)
x⁴
x³
x²
x¹
x⁰
5
0
3
0
7
43210

Each box holds a coefficient. The label above it is the exponent that term belongs to, and the number below is the array index, which is always the same number as the exponent here, that's the whole trick behind this representation. So A[4] = 5, A[3] = 0, A[2] = 3, A[1] = 0, A[0] = 7. The highlighted boxes are the non-zero terms; the dimmed ones (x³ and x¹) are exponents missing from the polynomial, which simply default to a coefficient of 0.

Key Idea

This works because the array index itself encodes the exponent, so you never need to store the exponent separately, you just read it off the position. The tradeoff is that the array's size must match the highest exponent plus one, whether or not most of those positions are actually used.

Why a different representation may be needed

That tradeoff becomes a real problem for a polynomial with a large degree but very few non-zero terms, for example:

1000000x⁵⁰⁰⁰⁰⁰ + 7x² + 3

Only 3 terms are non-zero, but the simple representation above would need an array of size 500001, almost all of it storing zeros. Such a polynomial is called sparse.

Definition

A sparse polynomial is a polynomial in which the number of zero-coefficient terms is much larger than the number of non-zero terms.

Two-array method for sparse polynomials

Instead of one array indexed by exponent, sparse polynomials are stored using two parallel arrays that record only the non-zero terms:

  • Coefficient array: the coefficient of each non-zero term
  • Exponent array: the exponent of each non-zero term

Both arrays are indexed together, so coefficient[i] goes with exponent[i].

Example

For 1000000x⁵⁰⁰⁰⁰⁰ + 7x² + 3:

Coefficient arrayExponent arrayIndex
1000000
7
3
500000
2
0
012

Reading them together:

  • Index 0: coefficient 1000000, exponent 500000 → 1000000x⁵⁰⁰⁰⁰⁰
  • Index 1: coefficient 7, exponent 2 → 7x²
  • Index 2: coefficient 3, exponent 0 → 3

This uses only 3 x 2 = 6 storage units, instead of 500001 units for the full array, a difference that only grows as the degree grows further while the number of actual terms stays small.

Note

This two-array idea, storing only the non-zero entries alongside enough information to place them correctly, is the same principle behind sparse matrix representation, covered next. There, each non-zero entry needs a row and a column instead of just an exponent, but the motivation, most positions are zero and not worth storing, is identical.

Note

The two parallel arrays can also be combined into a single 2D array, where each row is one term: poly[i][0] holds the coefficient and poly[i][1] holds the exponent. It stores exactly the same information as coefficient[] and exponent[] side by side, just packed into one structure instead of two. This row-per-term layout is also a preview of the tuple representation used for sparse matrices, coming up next, where each row instead holds (row, column, value).

When to use the sparse representation

  • The polynomial has few non-zero terms relative to its degree
  • The degree is large, so a full coefficient array would be mostly zeros
  • Faster access to just the non-zero terms is useful, since there is nothing else to skip over

Quick recall

  • Simple representation: one array indexed by exponent, coefficient stored at that index. Wastes space when most exponents are absent.
  • Sparse representation: two parallel arrays, one for coefficients and one for exponents, storing only the non-zero terms.
  • Choose the sparse form when the degree is large but the number of actual terms is small.