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?

Alyosha

I suppose you could approach it as a string parsing problem, but a list/vector really seems to be the most appropriate and efficient representation. – Impedimenta

In formal mathematics, polynomials can be seen as a vector space, therefore I'd consider that a good solution. – Jamboree

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.

Procambium

Actually I had followed other way. I used [3, 5, 6], so that for (i=0; i<n; i++) sum += array[i]*x^i. – Dichotomy

@Jinxed It could easily be extended to a multidimensional version for multivariate polynomials. – Keramic

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. :)

Resonate

Answer 3

You can represent expressions as Expression Trees. See for example .NET Expression Trees.

This allows for much more complex expressions than simple polynomials and those expressions can also use multiple variables.

In .NET you can manipulate the expression tree as a tree AND you can evaluate it as a function.

        Expression<Func<double,double>> polynomial = x => (x * x + 2 * x - 1);
        double result = polynomial.Compile()(23.0);

Abuzz

Answer 4

An object-oriented approach would say that a Polynomial is a collection of Monomials, and a Monomial encapsulates a coefficient and exponent together.

This approach works when when you have a polynomial like this:

y(x) = x^1000 + 1

An approach that tied a data structure to a polynomial order would be terribly wasteful for this pathological case.

Maidel

Answer 5

Vector/array is obvious choice. Depending on type of expressions you may consider some sort of sparse vector type (custom made, i.e. based on dictionary or even linked list if you expressions have 2-3 non-zero coefficients 5x^100+x ).

In either case exposing through custom class/interface would be beneficial as you can replace implementation later. You would likely want to provide standard operations (+, -, *, equals) if you plan to write a lot of expression manipulation code.

Knothole

Answer 6

You need to store two things:

1. The degree of your polynomial (e.g. "3")
2. A list containing each coefficient (e.g. "{3, 0, 2}")

In standard C++, "std::vector<>" and "std::list<>" can do both.

Incongruity

Why do you need to store the degree when it can be obtained from the list length? Or are you allowing for negative powers as well? – Setting

Answer 7

Just store the coefficients in an array or vector. For example, in C++ if you are only using integer coefficients, you could use std::vector<int>, or for real numbers, std::vector<double>. Then you just push the coefficients in order and access them by variable exponent number.

For example (again in C++), to store 5*x^3 + 9*x - 2 you might do:

   std::vector<int> poly;
   poly.push_back(-2); // x^0, acceesed with poly[0]
   poly.push_back(9);  // x^1, accessed with poly[1]
   poly.push_back(0);  // x^2, etc
   poly.push_back(5);  // x^3, etc

If you have large, sparse, polynomials, then maybe you'd want to use a map instead of a vector. If you have fixed sized lengths, then you'd perhaps use an fixed length array instead of a vector.

I've used C++ for examples, but this same scheme can be used in any language.

Empathic

Answer 8

You can also transform it into reverse Polish notation:

6x^2 + 5x + 3 -> x 2 ^ 6 * x 5 * + 3 +

Where x and numbers are "pushed" onto a stack and operations (^,*,+) take the two top-most values from the stack and replace them with the result of the operation. In the end you get the resultant value on the stack.

In this form it's easy to calculate arbitrarily complex expressions.

This representation is also close to tree representation of expressions where non-leaf tree nodes represent operations and functions and leaf nodes are for constants and variables.

What's good about trees is that you can also easily evaluate expressions and you can also do things like symbolic differentiation on them. Both have recursive nature.

Ambroid

Just wondering: how easy is it to evaluate equality on the RPN representation? Division in the ring of polynomials? My instinct is "tricky", so don't use that representation if you need those operations. But I suppose if you know your RPN expression is a polynomial, you can always canonicalize it as a separate step, and hence extract the coefficients exactly as if you'd store it that way all along. – Testicle

What kind of equality are you talking about? Sorry, not familiar with rings. – Ambroid

well, suppose I have an RPN expression "x 2 ^ 6 * x 5 * + 3 +", and another one "3 x 2 ^ 6 * x 5 * + +". It's a certain amount of effort to determine that those are in fact different representations of the same polynomial. It's totally obvious how to compare polynomials for equality if they're stored as sorted sequences of coefficients. Rings are an abstract mathematical structure (en.wikipedia.org/wiki/Ring_%28mathematics%29), if you don't know what one is then you're unlikely to find yourself unexpectedly doing polynomial division, so probably don't need to worry :-) – Testicle

@SteveJessop: Ah, that, in that case trees might be a little bit more friendly. But even with trees it may be more complex than just comparing left subtrees with right subtrees, because, for example, what if it's a binary tree and you're doing A+B+C with it? There are more than 2 ways of representing an equivalent expression with a binary tree. – Ambroid