Univariate polynomials.

Let R be a ring. The univariate polynomial ring R[x] can be implemented using different data types.

Expression trees.

All arithmetic operations are in $\cal {O}$(1). But the representation is not canonical: two different expression trees can encode the same polynomial. Therefore operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in $\cal {O}$(n) where n is the degree of the polynomial. Even worst the equality-test is $\cal {O}$(n²) (for non-balanced trees).

Arrays of coefficients.

The polynomial

p(x)  =   a_nxⁿ + ^... + a₁x + a₀ (33)

is coded by a record consisting of

• a single integer s,
• a single integer d $\leq$ s + 1,
• an array of size s such that a₀ + ... + a_nxⁿ is represented by [a₀,..., a_n,...] and d = n.

This representation is said dense becasue all a_i are coded, even those which are null. This representation is canonical. Hence operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in $\cal {O}$(1). Addition and equality-test are in $\cal {O}$(n) and multiplication is in $\cal {O}$(n²). This representation is especially good when the ring of coefficients is a small prime field, i.e. $\mbox{${\mathbb Z}$}$/p$\mbox{${\mathbb Z}$}$ with p prime and in the range [2, 2^N - 1].

List of terms.

The polynomial

p(x)  =   a_nxⁿ + ^... + a₁x + a₀ (34)

is coded by the list L of records [a_i, i] where a_i is a nonzero coefficient and such that L is sorted decreasingly w.r.t. i. This representation is said sparse, since only the nonzero a_i are coded. This representation is also canonical. Hence operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in $\cal {O}$(1). Moreover the operation REDUCTUM does not require coefficient duplication (on the contrary of the previous representation). Addition and equality-test are in $\cal {O}$(n) and multiplication is in $\cal {O}$(n²). This representation is especially good when the ring of coefficients is itself a ring of sparse polynomials.