Best way to store multi variable polynomials in Lisp

Question

I need to store polynomials in my lisp program for adding, subtracting and multiplying. But cannot find an easy way of storing one.

I've considered the following way

(2x^3 + 2x + 4y^3 - 2z) in a list of lists where each list is a list of the amount of each power

= ( (0 2 0 2) (0 0 0 4) (0 2) )

But the uncertain lengths of each list and potential length could become a problem.

Is there a generally accepted way to store them in lisp which could make it as easy as possible to add, subtract and multiply them together?

Answer 1

Assuming you know the number of possible variables beforehand, you could express each term like this: (constant x-exponent y-exponent z-exponent ...). Then 5xy^2 would be (5 1 2 0), and a full expression would just be a list of those terms.

If you want to be able to handle any number of arbitrary variables, you would need to do an associative list along the lines of ((constant 5) (a 0) (b 3) (z 23) (apple 13)).

Either way, if you start with individual terms, it's easy to build more complex expressions and this way you don't need to mess with multiple dimensions.

Answer 2

There are several ways of representing polynomials. As usual the choice of representation is a tradeoff.

One way is an association list from order to coefficient usually sorted after according to order.

12x^2 + 11x + 10 ((2 . 12) (11 . 1) (10 . 0))

If you need to compute with sparse polynomials, then this representation is space efficient. x^200 is just ((200 . 1)).

If your calculations consists mostly of non-sparse polynomals a vector representation is more space efficient:

12x^2 11x + 10 (vector 10 11 12)

The length of the vector minus one gives the order of the polynomial.

If you need polynomials of more than one variable there are variations of the representations. In particular you can look a the representation in Maxima:

http://maxima.sourceforge.net/docs/manual/maxima_14.html

If you happen to have "Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP" by Peter Norvig, there is a nice chapter on polynomials.

Answer 3

May be this idea will help you partly. You can represent polynomial as vector, when index will be a power and an element - a coefficient, and first element - your variable. I mean 5*x^3 + 10*x^2 + 40x + 50 will look like #(50 40 10 5). Working with such representation easy, but it looks like not very optimal for big powers like x^100.

Multivariable polynomial may be represented as N-dimensional array where N - number of variables.