Hi, I am new here. I am taking a class for my senior year for my BS. Our last project is to create a Polynomial calculator in CLISP. I am having trouble with one aspect of it.
Polynomials are represented as lists of lists ex: 7x^2  3x + 4 would be '((7 X 2) (3 X 1) (4 X 0))
So I need to make a function that adds two polynomials
ex:
(addpoly '((6 X 7) (3 X 1) (4 X 0)) '((2 X 2) (3 X 1) (3 X 0)))
would give me: ((6 X 7) (2 X 2) (7 X 0))
I am not sure how to start on this. I have tried a few things but nothing seems to work. Any advice?
Can someone give me some ideas on how to solve this problem?
Re: Can someone give me some ideas on how to solve this problem?
Okay, so you are given the structure the data is given to you. Your two main options here are use it as is, or convert it to another form for your use, and then convert back.
Either way, it may be useful to break down the problem of adding two polynomials by defining a function, say addtermtopoly, and then use it in writing addpoly; if you define such a function, addpoly can be as simple as (for example):
You can of course write it in another style if you want.
If you don't convert to another data structure, addpoly should be easily doable in O(m*n) time (with m and n being the lengths of the two polynomials).
As a hint, take a look at FIND and its :KEY argument. Alternatively, you could do addtermtopoly in a recursive manner (which would work assuming the polynomial is not too long).
Either way, it may be useful to break down the problem of adding two polynomials by defining a function, say addtermtopoly, and then use it in writing addpoly; if you define such a function, addpoly can be as simple as (for example):
Code: Select all
(defun addpoly (poly1 poly2)
(dolist (term poly1)
(setf ploy2 (addtermtopoly term poly2)))
poly2)
If you don't convert to another data structure, addpoly should be easily doable in O(m*n) time (with m and n being the lengths of the two polynomials).
As a hint, take a look at FIND and its :KEY argument. Alternatively, you could do addtermtopoly in a recursive manner (which would work assuming the polynomial is not too long).

 Posts: 148
 Joined: Wed Jul 30, 2008 11:26 pm
Re: Can someone give me some ideas on how to solve this problem?
Do you mean you have to use the CLISP implementation of Common Lisp, or did you mean to write "CL"?mscheaf wrote:I am not sure how to start on this. I have tried a few things but nothing seems to work. Any advice?
I would start by defining a few functions, such as ADDTERMS to add terms with like exponents and POW> and POW= to compare the exponents in two terms. Once I had those, it would be simple to iterate over the two, adding like terms where appropriate and combining the two polynomials otherwise. Since the input is certain to be short, you could even write it as a nontailrecursive function.
Another approach would be to fill in the zero terms to make both the same length, making the actual addition loop less complicated. Or you could write a function that takes a single term and fits it into another polynomial in the appropriate place, then fit the second polynomials terms into the first one by one. Any of the above would work, so pick the one you think is the best algorithm. Just break down your approach into small chunks that you know how to do.