Polynomial Arithmetic in Lisp: How to Begin?

  • MHB
  • Thread starter JamesBwoii
  • Start date
  • Tags
    Polynomials
In summary: Then the constants in each term of the second polynomial are in the order (c1, c2, ..., cn), and the variables are in the order (x, y, ..., xn). You can add the constants together in two ways: $(c1 + c2) or $(cn + c1).
  • #36
Bacterius said:
Looks fine to me, if a bit messy (I would personally first find the first two elements using "let", and then inside that let use these elements to access the variable and exponents for both of them, instead of starting from scratch from p1 every time).

So what's next now, say to get addition done? You need exactly one thing: a function to sort the list based on the variable + exponent, this will require you to read up on Lisp's sorting function. Call this function "sortpoly". Then, addition can be implemented as:
Code:
(defun addpoly (p1 p2)
    (collect-terms(sortpoly(append p1 p2)))
)
Here collect-terms is the function you call "poly", which we have been working on so far. Do you understand why addition can be implemented in this way? If so, implement sortpoly and addpoly.

As a bonus, you might notice that if you use your "addpoly" function on, say, ((1(2 x)) and ((-1(2 x)) you will get ((0(2 x)). This is not technically wrong, but zero times anything is still zero, so see if you can implement a function to remove terms with a zero coefficient from a polynomial. You can use a recursive function in the same spirit as "poly"/"collect-terms" (by taking a look at the first element of the polynomial, checking if its constant is zero or not, discarding it if appropriate, and recursing on the rest of the polynomial).
When you say sort by the variable and exponent you mean sort alphabetically for the variable and say sort from low to high for the exponent?

I assume sorting by the variable is the priority so the whole list would be ordered alphabetically by variable then each group of the same variables would be ordered by exponent.

Then if two polynomials were being added together and had the same variable and exponent they could be added.
 
Technology news on Phys.org
  • #37
JaAnTr said:
When you say sort by the variable and exponent you mean sort alphabetically for the variable and say sort from low to high for the exponent?

I assume sorting by the variable is the priority so the whole list would be ordered alphabetically by variable then each group of the same variables would be ordered by exponent.

Then if two polynomials were being added together and had the same variable and exponent they could be added.

You just need all terms with the same variable AND exponent (remember - you can't add $x$ to $x^2$) to appear next to one another in the list after sorting it. So basically any consistent sorting criteria will do the job. As such, you can simply tell Lisp to sort the list based on the (variable exponent) part of the elements. You can't just call sort directly, because that'll sort the list based on (constant (variable exponent)) which isn't what you want. Check out the built-in sort function, it does let you specify how to carry out the sort; specifically, look at the key parameter.

Also, helpful tip when writing Lisp code: indent it. That tends to make it much easier to follow your own code, especially when writing complex expressions.
 
  • #38
For what it's worth (you've already completed this function, so there's no harm in showing a different approach) this was my implementation of your "poly" function. It's similar to yours, except different naming and two "let" sections:
Code:
(defun collect (l)
    (let ((m1(car l))
          (m2(car(cdr l)))
          (rem(cdr(cdr l))))

        (if (null m2)                                                          ; If the list has less than 2 elements
      	    l                                                                  ; then return the list (nothing to collect)
            (let ((c1(car m1))                                                 ; else, extract (c1, t1), (c2, t2) from m1 and m2
                  (c2(car m2))
                  (t1(car(cdr m1)))
                  (t2(car(cdr m2))))

                (if (equal t1 t2)                                              ; if t1 == t2
                    (collect (append (list (list (+ c1 c2) t1)) rem))          ; then return collect((c1 + c2, t1) + rem)
                    (append (list m1) (collect (append (list m2) rem)))        ; else return (c1, t1) + collect((c2, t2) + rem)
                )
            )
        )
    )
)
Notice that the function is not even aware that the terms (here t1 and t2) contain variables and exponents. It just doesn't care, all it assumes is that they can be compared when it calls "equal" ("equal" on two lists compares the lists element-wise). This is what you are aiming for in a functional implementation, you want the least specific, most general function that will operate on as wide a range of types as possible.
 

Similar threads

Back
Top