LispForum

Posted: **Mon Sep 13, 2010 10:49 pm**

I want to make a function to add two polynomials that are in the form of (factor power). The problem I am having is how to implement the recursion call to add a polynomial with more than one term. This is my function I have now and three small functions supporting it -

Code: Select all

(defun findfactor (term) 
  (car term))

(defun findpower (term)
  (cadr term))

(defun maketerm(factor power)
  (list factor power))

(defun add-poly (poly1 poly2)

  (if (null poly1) poly2
    (if (null poly2) poly1
  (let ( (term1 (car poly1)) (term2 (car poly2)) )
    (if (= (findpower term1) (findpower term2)) 
        (maketerm (+ (findfactor term1) (findfactor term2)) (findpower term1))
      (if (> (findpower term1) (findpower term2))
          (append poly1 poly2) (append poly2 poly1)))
    (add-poly (cadr poly1) (cadr poly2))))))

Whenever I call it with two polynomials with one term each, I get nil. For example -
(add-poly `( (2 2) ) `( (2 1) )) returns nil

With one two-term polynomial and one one-term polynomial -
(add-poly `( (2 2) (2 1)) `( (2 2) )) returns the second term of (2 1)

With two two-term polynomials -
(add-poly `( (5 2) (3 1)) `( (8 2) (9 1) )) gets an error that says "Cannot take CDR of 3"

All of these scenarios really confuse me. If I take the recursive call at the end away and just try to add two one-term polynomials, it works fine. So I know the if statement is right...I just can't seem to get how to correctly call this again to work for polynomials that have more than one term. Any help is appreciated, thanks.

Posted: **Mon Sep 13, 2010 10:59 pm**

Also, if I change the recursive line to

(add-poly (rest poly1) (rest poly2))))))

And input two two-term polynomials, I get nil...

Posted: **Mon Sep 13, 2010 11:02 pm**

Another update to code adding a recursive call to the first if condition (if the powers are equal) -

Code: Select all

(defun add-poly (poly1 poly2)

  (if (null poly1) poly2
    (if (null poly2) poly1
  (let ( (term1 (car poly1)) (term2 (car poly2)) )
    (if (= (findpower term1) (findpower term2)) 

      (append  (maketerm (+ (findfactor term1) (findfactor term2)) (findpower term1)) (add-poly (rest poly1) (rest poly2)))

      (if (> (findpower term1) (findpower term2))
          (append poly1 poly2) (append poly2 poly1)))
    (add-poly (rest poly1) (rest poly2))))))

This gives me the same results.

Posted: **Tue Sep 14, 2010 5:08 am**

The last example was actually quite close, but the innermost clause stopped making sense. First thing, don't use nested IFs, use COND, it makes the logic much clearer. Also, CAR of NIL is defined to be NIL, which means you can actually pull the terms outside the chain, and then reduce the whole thing to a single COND:

Code: Select all

(defun add-poly (poly1 poly2) ;; still wrong
  (let ((term1 (car poly1))
        (term2 (car poly2)))
    (cond ((null term1) poly2)
          ((null term2) poly1)
          ((= (findpower term1) (findpower term2))
              (append (maketerm (+ (findfactor term1) (findfactor term2)) (findpower term1))
                      (add-poly (rest poly1) (rest poly2))))
          ((> (findpower term1) (findpower term2))
           (append poly1 poly2))
          (t
           (append poly2 poly1)
           (add-poly (rest poly1) (rest poly2))))))

This makes it clear that the second to last branch is wrong, and the last branch makes no sense. Assuming that the polynomials are properly ordered what you want to do in the case powers are different is append the higher power term to the sum of the rest of the polynomial with the higher power and the whole of the polynomial with lower power:

Code: Select all

(defun add-poly (poly1 poly2) ;; hopefully right
  (let ((term1 (car poly1))
        (term2 (car poly2)))
    (cond ((null term1) poly2)
          ((null term2) poly1)
          ((= (findpower term1) (findpower term2))
              (cons (maketerm (+ (findfactor term1) (findfactor term2)) (findpower term1))
                    (add-poly (rest poly1) (rest poly2))))
          ((> (findpower term1) (findpower term2))
           (cons term1 (add-poly (rest poly1) poly2)))
          ((< (findpower term1) (findpower term2))
           (cons term2 (add-poly poly1 (rest poly2)))))))

Note the use of CONS in recursive branches to CONStruct a list from an element and a tail. Note how each branch except base cases ends in a recursive call which reduces the order of at least one argument by one, which guarantees termination. Reducing a problem to base cases and induction cases is crucial for implementing any recursive solution.

LispForum

Adding two Polynomials

Adding two Polynomials

Re: Adding two Polynomials

Re: Adding two Polynomials

Re: Adding two Polynomials