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?

Accepted Answer

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.

How to store a polynomial?

Solution

Problem