Univariate polynomials.

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

Expression trees.

All arithmetic operations are in $\cal {O}$(1) mathend000#. 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) mathend000# where n mathend000# is the degree of the polynomial. Even worst the equality-test is $\cal {O}$(n²) mathend000# (for non-balanced trees).

Arrays of coefficients.

The polynomial

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

is coded by a record consisting of

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

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

List of terms.

The polynomial

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

is coded by the list L mathend000# of records [a_i, i] mathend000# where a_i mathend000# is a nonzero coefficient and such that L mathend000# is sorted decreasingly w.r.t. i mathend000#. This representation is said sparse, since only the nonzero a_i mathend000# are coded. This representation is also canonical. Hence operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in $\cal {O}$(1) mathend000#. 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) mathend000# and multiplication is in $\cal {O}$(n²) mathend000#. This representation is especially good when the ring of coefficients is itself a ring of sparse polynomials.