How to store a polynomial?

Question

Integers can be used to store individual numbers, but not mathematical expressions. For example, lets say I have the expression:

6x^2 + 5x + 3

How would I store the polynomial? I could create my own object, but I don't see how I could represent the polynomial through member data. I do not want to create a function to evaluate a passed in argument because I do not only need to evaluate it, but also need to manipulate the expression.

Is a vector my only option or is there a more apt solution?

Answer 1

A simple yet inefficient way would be to store it as a list of coefficients. For example, the polynomial in the question would look like this:

[6, 5, 3]

If a term is missing, place a zero in its place. For instance, the polynomial 2x^3 - 4x + 7 would be represented like this:

[2, 0, -4, 7]

The degree of the polynomial is given by the length of the list minus one. This representation has one serious disadvantage: for sparse polynomials, the list will contain a lot of zeros.

A more reasonable representation of the term list of a sparse polynomial is as a list of the nonzero terms, where each term is a list containing the order of the term and the coefficient for that order; the degree of the polynomial is given by the order of the first term. For example, the polynomial x^100+2x^2+1 would be represented by this list:

[[100, 1], [2, 2], [0, 1]]

As an example of how useful this representation is, the book SICP builds a simple but very effective symbolic algebra system using the second representation for polynomials described above.

Answer 2

A list is not the only option.

You can use a map (dictionary) mapping the exponent to the corresponding coefficient.

Using a map, your example would be

{2: 6, 1: 5, 0: 3}

A list of (coefficient, exponent) pairs is quite standard. If you know your polynomial is dense, that is, all the exponent positions are small integers in the range 0 to some small maximum exponent, you can use the array, as I see Óscar Lopez just posted. :)