Polynomial Arithmetic in Lisp: How to Begin?

[JamesBwoii]

Hi, I'm new to lisp and I've been set some coursework in it and I don't really know how to begin. I need to implement polynomial arithmetic so I can add, subtract and multiply polynomials.

So like:

$\left(x + y\right)\left(x + y\right) = \left({x}^{2} + 2xy + {y}^{2}\right)$

It also needs to collect terms so:

$\left(x+y\right)+\left(x\right) = 2x + y$

It needs to all be in a functional style and I can't use the built in loop function or non-functional operators like push, pop, mapcan, set, etc.

How should I begin going about this?

Thanks! :D

 

[Evgeny.Makarov]

Is the set of variables ($x$, $y$, …) fixed or can you consider polynomials in arbitrary variables?

 

[JamesBwoii]

Is the set of variables ($x$, $y$, …) fixed or can you consider polynomials in arbitrary variables?

Yes sorry I should have said, the variables are arbitrary. They can be any letters.

 

[Nono713]

One way to do it is to notice that any polynomial can be rewritten in the generic representation:

poly = CONSTANT * TERM + CONSTANT * TERM + ... + CONSTANT * TERM

Where TERM is of the form:

TERM = variable^exponent * variable^exponent * ... * variable^exponent

For instance, we get:

x + y               =     1 * (x^1) + 1 * (y^1)
x^2 + 2xy + y^2     =     1 * (x^2) + 2 * (x^1 * y^1) + 1 * (y^2)

The reason for separating the constants and variables is it makes implementing addition and subtraction easier, as two distinct terms cannot be added or subtracted (e.g. x^2 + xy cannot be rewritten as a single term, but 2xy + 3xy can) while not making multiplication any harder. In fact for single-variable polynomials this is the canonical internal representation used by most implementations.

You could represent this in Lisp by using a list of (constant, term) pairs, where each term is itself a list of (variable, exponent) pairs. Alternatively, flattening the term representation as a list of variables repeated as many times as they are multiplied may be easier to handle, e.g. x^2 becomes (x, x), xy^2 becomes (x, y, y). This may possibly make it easier to operate on them functionally, though it does take up more space, and you may have to sort them.

Can you see how to implement addition and subtraction using this representation? How about multiplication?​

 

[JamesBwoii]

I think for addition you would need to compare the constant*term of the first polynomial against the each constant*term of the second polynomial. From there you would say that if the variable of the first term is equal to the variable of first term from the second polynomial then add the constant and keep the exponent the same. It would also be the same for subtracting but obviously instead of adding the constant you would take them away.

For multiplication I think you would need to multiply every term from polynomial 1 by every term from polynomial 2. This would mean that you would just multiply the constant from polynomial 1 by polynomial 2 and if the variable was the same then the exponents would be added.

Is that correct?

 

[Nono713]

Yes, that is correct. Now that I think a bit more on it, since you have to be able to collect terms anyway during multiplication, it's easy to see that addition and subtraction are actually trivial to implement given a function that collects terms: simply concatenate both polynomials, and collect terms. For subtraction, just multiply the constant coefficient of each term of the second polynomial by -1 before adding, i.e. $p - q = p + (-q)$. Similarly, multiplication is easy, you just multiply all terms pairwise as you said and then collect terms at the end.

So the key to implementing these functions is really finding how to collect terms. Assuming we have the ability to determine if two terms are equal (we can discuss how to do this later), how would you go about collecting terms? (there is a rather elegant functional algorithm to do it. hint: sort the list of terms)​

 

[JamesBwoii]

I'm not sure how to do it functionally or particularly elegantly, but wouldn't you just go through the expression and if the variable and exponent were equal then add their related constants together? Perhaps you could sort the expression alphabetically based on the variable so all the same variables would be together?

 

[Nono713]

I'm not sure how to do it functionally or particularly elegantly, but wouldn't you just go through the expression and if the variable and exponent were equal then add their related constants together? Perhaps you could sort the expression alphabetically based on the variable so all the same variables would be together?

You're almost there: the real question is how to "add their related constants together" without using a non-functional loop. Suppose you have sorted the polynomial so that all equal terms appear next to one another in the list. Now suppose you look at the first two terms in the list. There are two possibilities: either they are equal, or they are not. So your algorithm looks like this (in pseudocode, I don't actually know Lisp very well):

COLLECT_TERMS(poly):
    let (c1, t1) = poly[0]  // c1 = constant coefficient, t1 = term
    let (c2, t2) = poly[1]

    if (t1 and t2 are the same):
        ... do something here
    else:
        ... do something here

Think about a recursive way to compute the COLLECT_TERMS function.

 

[JamesBwoii]

I'm struggling to see how to do it recursively, I'm not particularly good at recursion.

I know that if t1 == t2 then you should do c1+c2 and multiply by t1.

Would you need to add this new, simplified term, to a new list and run the function again over the remainder of the list?

 

[Nono713]

I'm struggling to see how to do it recursively, I'm not particularly good at recursion.

I know that if t1 == t2 then you should do c1+c2 and multiply by t1.

Would you need to add this new, simplified term, to a new list and run the function again over the remainder of the list?

That's almost right: what you need to do is indeed add c1 and c2 to produce a new term (c1 + c2, t1), but then you must recurse over that item PLUS the remainder of the list. The reason is there might still be more t1 terms in the remainder of the list. For instance:
$$1x^2 + 1x^2 + 1x^2 + 1xy$$
We look at the first two elements of the polynomial, $1x^2$ and $1x^2$. The terms ($x^2$ and $x^2$) are the same, so we add them up to get $(1 + 1)x^2 = 2x^2$. And then we recurse over:
$$2x^2 + 1x^2 + 1xy$$
Again, the first two elements have the same term, so add them:
$$3x^2 + 1xy$$
At this point, the first two terms are different ($x^2 \ne xy$). What do we do? Since the list is sorted such that equal terms can only appear next to one another, doesn't that mean that there are no other $x^2$ terms in the list? If so, shouldn't we just leave it alone and start collecting terms in the remainder of the list instead?

Also, you need a base case for the recursion: since we need to look at the first two elements, it stands to reason that the base case is a list with less than two elements. In that case, there is nothing to collect, so we just return the list itself. So far we have:

COLLECT_TERMS(poly):
    if length(poly) < 2:
        return poly

    let (c1, t1) = poly[0]  // c1 = constant coefficient, t1 = term
    let (c2, t2) = poly[1]
    let remainder = poly[2...]  // possibly empty!

    if (t1 and t2 are the same):
        return COLLECT_TERMS((c1 + c2, t1) + remainder)
    else:
        ... do something here

Given this information, can you complete the algorithm for the final case where the first two terms aren't the same?

 

[JamesBwoii]

Is it just that if t1 $\ne$ t2 then all the terms have been collected?

 

[Nono713]

Is it just that if t1 $\ne$ t2 then all the terms have been collected?

Not quite. Consider the list of terms:
$$1x^2 + 1x^2 + 2xy + 1xy + y^2$$
If you apply the algorithm so far, we get:
$$1x^2 + 1x^2 + 2xy + 1xy + y^2$$
$$2x^2 + 2xy + 1xy + y^2$$
And here we are stuck: there are no more $x^2$ terms besides the first one, but there are still terms to be collected in the remainder ($2xy + 1xy + y^2$). But perhaps we can complete the job by recursing on the remainder on the list, and adding back the $2x^2$ term at the end once everything has been collected? What would that give?

 

[JamesBwoii]

Then we'd recurse on the rest of the list and get:

$3xy + {y}^{2}$

Then adding the $2{x}^{2}$ back in we would get:

$2{x}^{2}+3xy + {y}^{2}$

So is the way to do it, once t1 $\ne$ t2 you take out c1 and t1 and recurse the rest of the list?

 

[Nono713]

Then we'd recurse on the rest of the list and get:

$3xy + {y}^{2}$

Then adding the $2{x}^{2}$ back in we would get:

$2{x}^{2}+3xy + {y}^{2}$

So is the way to do it, once t1 $\ne$ t2 you take out c1 and t1 and recurse the rest of the list?

Yup, exactly. Which can be implemented recursively in a natural way, completing our algorithm:

COLLECT_TERMS(poly):
    if length(poly) < 2:
        return poly

    let (c1, t1) = poly[0]
    let (c2, t2) = poly[1]
    let remainder = poly[2...]

    if (t1 and t2 are the same):
        return COLLECT_TERMS((c1 + c2, t1) + remainder)
    else:
        return (c1, t1) + COLLECT_TERMS((c2, t2) + remainder)

You can verify that the algorithm will always terminate successfully: at each recursion, one element of the list is removed from the recursion one way or the other; in one case, the first two elements are merged into one, and in the other case, the first element is pulled out of the recursion. This also shows the algorithm to collect terms runs in linear time (but recall we have to sort the list of terms before anyway). Make sure to try it out step by step on a few polynomials, such as $1x^2 + 2xy + 3xy + y^2 + 2y^2 + 3z$ to be clear on why it works.

Now that you know how to collect terms, I would suggest implementing this algorithm above in Lisp and using it to implement addition and subtraction first. Then verify they work, and have a go at multiplication. Do not forget that the COLLECT_TERMS algorithm depends on the terms being grouped together! They don't *need* to be sorted, just being grouped such that equal terms are adjacent is sufficient, but sorting gets the job done.

 

[JamesBwoii]

I'm trying to write it in Lisp but I'm really struggling. So here's the algorithm that you said to use.

COLLECT_TERMS(poly):
if length(poly) < 2:
return poly

let (c1, t1) = poly[0]
let (c2, t2) = poly[1]
let remainder = poly[2...]

if (t1 and t2 are the same):
return COLLECT_TERMS((c1 + c2, t1) + remainder)
else:
return (c1, t1) + COLLECT_TERMS((c2, t2) + remainder)[/CODE]

There's a few bits that I don't understand how to do.

So the function needs to be able to take a polynomial, for example let's use:

$$1x^2 + 1x^2 + 2xy + 1xy + y^2$$

What I don't get how to do is this part mainly:

let (c1, t1) = poly[0]
let (c2, t2) = poly[1]
let remainder = poly[2...]

For a start wouldn't that set c1 and t1 equal to the exact same thing? Also I'm confused as to what

poly[0]

represents. Obviously if it was an array it would represent the first element but in our case is it supposed to represent $1x^2$?

Essentially what I think I am struggling with is splitting the polynomial up into its component and term so I can access them.

Thanks!EDIT: I've done some more work on it and decided that the best way to pass a polynomial into a function such as $5x^2$ would be like:

(5(x 2))

 

[JamesBwoii]

I've written something that kind of works for certain things.

Here's the code:

(defun poly (p1)
  (let((x1(car(car(cdr(car p1))))) (x2(car(car(cdr(car(cdr p1))))))
       (e1(car(cdr(car(cdr(car p1)))))) (e2(car(cdr(car(cdr(car(cdr p1)))))))
       (c1(car(car p1))) (c2(car(car(cdr p1)))))

    (format t "Variable x1 is ~a, variable x2 is ~a, exponent 1 is ~a and exponent 2 is ~a,
constant 1 is ~a, constant 2 is ~a~%" x1 x2 e1 e2 c1 c2)
    (let ((list (if(and (equal x1 x2)
			(equal e1 e1))
		   (list(+ c1 c2)))))
		        

      (format t "plist is ~a~%" list))))

Given an input:

(multp '((5(x 2))(3(x 2))))

The output is:

Variable x1 is X, variable x2 is X, exponent 1 is 2 and exponent 2 is 2,
constant 1 is 5, constant 2 is 3
plist is (8)

Obviously ideally I want the result printed like:

(8(x 2))

However, I'm struggling to add variables to a list, I was wondering if you know how?

At the moment I've got (list(+ c1 c2)) which works perfectly, but if I try and add another list inside it with (list(x1 e1)) it won't let me do that.

Basically what I am asking is how do I add x1 and e1 to the list?

Thanks!

 

[Evgeny.Makarov]

At the moment I've got (list(+ c1 c2)) which works perfectly, but if I try and add another list inside it with (list(x1 e1)) it won't let me do that.

[m](list (x1 e1))[/m] tries first to run [m]x1[/m] on [m]e1[/m]. To form [m](8 (x 2))[/m] use something like [m](list (+ c1 c2) (list x1 e1))[/m].

Basically what I am asking is how do I add x1 and e1 to the list?

"Add" is not the best word to talk about lists. You can use the phrases "concatenate" or "create a list with the first element x, second element y, ...", which have precise meaning.

 

[Nono713]

I'm trying to write it in Lisp but I'm really struggling. So here's the algorithm that you said to use.
There's a few bits that I don't understand how to do.

So the function needs to be able to take a polynomial, for example let's use:

$$1x^2 + 1x^2 + 2xy + 1xy + y^2$$

What I don't get how to do is this part mainly:

let (c1, t1) = poly[0]
let (c2, t2) = poly[1]
let remainder = poly[2...]

For a start wouldn't that set c1 and t1 equal to the exact same thing? Also I'm confused as to what

poly[0]

represents. Obviously if it was an array it would represent the first element but in our case is it supposed to represent $1x^2$?

Here I am using the representation where a polynomial is a list of (constant, term) pairs. Note a pair can be represented as a list with two elements. So poly here is a list of two-element lists, and "let (c1, t1) = poly[0]" is just pseudocode to say "get the first element of the polynomial, which is a two-element list, and decompose it into the constant coefficient - first element - and the term - second element". Does that make it clearer?

So here I think of $1x^2 + 1x^2 + 2xy + 1xy + y^2$ as:

((1, x^2), (1, x^2), (2, xy), (1, xy), (1, y^2))

(the terms x^2, xy, etc.. also need to be represented, but for now I suggest just letting them be simple strings, as you only really need to modify them for multiplication)

 

[JamesBwoii]

Will there be any advantages to doing it your way further on as the way I am doing it seems to work decently?

Here's the code I've got at the moment:

(defun poly (p1)
  (let((x1(car(car(cdr(car p1))))) (x2(car(car(cdr(car(cdr p1))))))
       (e1(car(cdr(car(cdr(car p1)))))) (e2(car(cdr(car(cdr(car(cdr p1)))))))
       (c1(car(car p1))) (c2(car(car(cdr p1)))))

    (format t "Variable x1 is ~a, variable x2 is ~a, exponent 1 is ~a and exponent 2 is ~a,
constant 1 is ~a, constant 2 is ~a~%" x1 x2 e1 e2 c1 c2)
    (let ((list (if(and (equal x1 x2)
			(equal e1 e1))
		   (list(+ c1 c2)
			(list x1 e1)))))
		        
      (format t "list is ~a~%" list))))

So given an input of:

(poly '((5(x 2))(3(x 2))))

I now get:

Variable x1 is X, variable x2 is X, exponent 1 is 2 and exponent 2 is 2,
constant 1 is 5, constant 2 is 3
list is (8 (X 2))
NIL

I guess what I'm asking is should I change how I represent a polynomial from:

((5(x 2))(3(x 2)))

to

((1, x^2), (1, x^2), (2, xy), (1, xy), (1, y^2))

 

[Nono713]

Will there be any advantages to doing it your way further on as the way I am doing it seems to work decently?

Here's the code I've got at the moment:

(defun poly (p1)
  (let((x1(car(car(cdr(car p1))))) (x2(car(car(cdr(car(cdr p1))))))
       (e1(car(cdr(car(cdr(car p1)))))) (e2(car(cdr(car(cdr(car(cdr p1)))))))
       (c1(car(car p1))) (c2(car(car(cdr p1)))))

    (format t "Variable x1 is ~a, variable x2 is ~a, exponent 1 is ~a and exponent 2 is ~a,
constant 1 is ~a, constant 2 is ~a~%" x1 x2 e1 e2 c1 c2)
    (let ((list (if(and (equal x1 x2)
			(equal e1 e1))
		   (list(+ c1 c2)
			(list x1 e1)))))
		        
      (format t "list is ~a~%" list))))

So given an input of:

(poly '((5(x 2))(3(x 2))))

I now get:

Variable x1 is X, variable x2 is X, exponent 1 is 2 and exponent 2 is 2,
constant 1 is 5, constant 2 is 3
list is (8 (X 2))
NIL

I guess what I'm asking is should I change how I represent a polynomial from:

((5(x 2))(3(x 2)))

to

((1, x^2), (1, x^2), (2, xy), (1, xy), (1, y^2))

Your representation is fine. I am just using generic "mathematical" list notation here, you can use whatever representation you feel is appropriate/easiest as long as it contains the same information. Once parsed, it's all lists anyway (they don't call it Lisp for nothing!)

 

[JamesBwoii]

Mine at the moment only deals with simplifying two polynomials and I am trying to work out how to do with any number. I originally thought I would have to calculate how many polynomials were in the input before I started but using the algorithm you gave me I wouldn't have to would I?

x1,e1, and c1 would represent all things in the first polynomial and the same goes for x2, e2 and c1.

From there I would create a remainder list using

(cdr(cdr

to get everything in the list after the first two lists. Then from there I can compare, collect if they're the same and recursively do the same again.

Is that correct?

 

[Nono713]

Mine at the moment only deals with simplifying two polynomials and I am trying to work out how to do with any number. I originally thought I would have to calculate how many polynomials were in the input before I started but using the algorithm you gave me I wouldn't have to would I?

x1,e1, and c1 would represent all things in the first polynomial and the same goes for x2, e2 and c1.

From there I would create a remainder list using

(cdr(cdr

to get everything in the list after the first two lists. Then from there I can compare, collect if they're the same and recursively do the same again.

Is that correct?

Yes, that is right. You don't need to know how many elements are in the polynomial to use the algorithm: it will go through the polynomial on its own, and stop when it's done collecting all the terms. So indeed all you need is to implement the algorithm in Lisp, and it seems you're on the right track with your post. Recall the algorithm needs the elements to be sorted, but don't worry too much about that, you can do this part later, for now just make sure the polynomials you are testing with are sorted.

I would also give a more descriptive name to the function, something like "collect". The name "poly" is a bit misleading, if anything I would expect a "poly" function to parse a string and return the corresponding polynomial that can then be used in "add", "subtract" and "multiply" functions.

I am just about out of time for today but if you still need help I should have more time tomorrow to go through the problem with you.

 

[JamesBwoii]

Oh yeah just realized it's midnight in New Zealand! I'll work on it all day today, and post again if/when I run into any issues.

Thanks so much for all the help so far!

 

[JamesBwoii]

I've had a go at finishing the algorithm in Lisp but it's not working properly. Here it is:

(defun poly (p1)
  (let((x1(car(car(cdr(car p1))))) (x2(car(car(cdr(car(cdr p1))))))
       (e1(car(cdr(car(cdr(car p1)))))) (e2(car(cdr(car(cdr(car(cdr p1)))))))
       (c1(car(car p1))) (c2(car(car(cdr p1))))
       (remainder(cdr(cdr p1))))

    (format t "Variable x1 is ~a, variable x2 is ~a, exponent 1 is ~a and exponent 2 is ~a,
constant 1 is ~a, constant 2 is ~a,
remainder is ~a~%" x1 x2 e1 e2 c1 c2 remainder)
    (if(and(equal x1 x2)
	   (equal e1 e2))
       (poly(list
	(list(+ c1 c2)(list x1 e1))remainder)))))

Given the input:

(poly '((5(x 2))(3(x 2))(10(x 2))(15(x 2))(20(x 2))))

The output is

(poly '((5(x 2))(3(x 2))(10(x 2))(15(x 2))(20(x 2))))
Variable x1 is X, variable x2 is X, exponent 1 is 2 and exponent 2 is 2,
constant 1 is 5, constant 2 is 3,
remainder is ((10 (X 2)) (15 (X 2)) (20 (X 2)))
Variable x1 is X, variable x2 is 15, exponent 1 is 2 and exponent 2 is (X 2),
constant 1 is 8, constant 2 is (10 (X 2)),
remainder is NIL
NIL

I'm not sure where I'm going wrong. Obviously my cdr's and car's aren't working correctly but I don't know how to fix it.

EDIT:

I think it's because the remainder has an extra set of brackets around it but I can't get rid of them!

 

[Nono713]

Okay, I'm back, I guess. The issue here is that you are creating more nested lists than you should. In that final line:

(poly(list(list(+ c1 c2)(list x1 e1))remainder)))))

Notice that you are trying to make a list out of the new element and the remainder. But the remainder is already a list! So that is going to create a new list that contains the first element and then another list of remaining elements, which is not what you want. What you want is to insert the new element at the beginning of the remainder, or, thought of differently, make a 1-element list out of the new element and concatenate it with the remainder. Hence what you are missing here is the concatenation step. In Lisp, this is done using the "append" function. That is:

(poly(append (list(list(+ c1 c2)(list x1 e1))) remainder)))))

With this modification it will now print:

Variable x1 is X, variable x2 is X, exponent 1 is 2 and exponent 2 is 2,
constant 1 is 5, constant 2 is 3,
remainder is ((10 (X 2)) (15 (X 2)) (20 (X 2)))
Variable x1 is X, variable x2 is X, exponent 1 is 2 and exponent 2 is 2,
constant 1 is 8, constant 2 is 10,
remainder is ((15 (X 2)) (20 (X 2)))
Variable x1 is X, variable x2 is X, exponent 1 is 2 and exponent 2 is 2,
constant 1 is 18, constant 2 is 15,
remainder is ((20 (X 2)))
Variable x1 is X, variable x2 is X, exponent 1 is 2 and exponent 2 is 2,
constant 1 is 33, constant 2 is 20,
remainder is NIL
Variable x1 is X, variable x2 is NIL, exponent 1 is 2 and exponent 2 is NIL,
constant 1 is 53, constant 2 is NIL,
remainder is NIL

(and then die because the base case is missing, but that's easy to add). Notice that it successfully collected all of the $x^2$ terms, 53 in total, so that part works at least. Now you need to add the base case (return properly when there's less than 2 elements left) and handle the case where the two elements have different variables. Then afterwards we can focus on handling an arbitrary number of variables and exponents, and (finally) implementing addition and subtraction using this function.

 

[Nono713]

Okay, I've implemented my own collect-terms function in Lisp to have a reference. Also, perhaps you have noticed, but we can be a little bit cleverer with our polynomial representation: if we switch from representing the terms as a list of (variable, exponent) but instead as a list of (exponent, variable), we can actually reuse the collect-terms function to multiply terms, because the exponents will add as well when multiplying terms together! As you can see, it's not a big change, but it will help us considerably for implementing multiplication.

As you can see, in some sense the collect-terms function becomes a generic "grouping" function that aggregates nearby list elements together, and it can then be used for a variety of purposes including its original use to collect like terms in a polynomial. Does that make sense?

 

[JamesBwoii]

Okay, I've implemented my own collect-terms function in Lisp to have a reference. Also, perhaps you have noticed, but we can be a little bit cleverer with our polynomial representation: if we switch from representing the terms as a list of (variable, exponent) but instead as a list of (exponent, variable), we can actually reuse the collect-terms function to multiply terms, because the exponents will add as well when multiplying terms together! As you can see, it's not a big change, but it will help us considerably for implementing multiplication.

As you can see, in some sense the collect-terms function becomes a generic "grouping" function that aggregates nearby list elements together, and it can then be used for a variety of purposes including its original use to collect like terms in a polynomial. Does that make sense?

I can see how we could reuse the function to multiply terms together but I don't see why we need to swap the order of the variable and exponent?

 

[Nono713]

I can see how we could reuse the function to multiply terms together but I don't see why we need to swap the order of the variable and exponent?

Well you have to tell the function which part of the element is the "constant" (to add together). For polynomial terms we defined it to be the first part in (constant, term). For exponents we "defined" it to be the second part in (variable, exponent). So we can't directly use the same function in that case. But switching around to (exponent, variable) costs us nothing since we haven't begun to operate on variables and exponents yet.

- - - Updated - - -

Here the idea is to think of the function no longer as simply "collecting terms" but being a generic function that operates on a list of elements of the form (number, data) where consecutive elements with the same data are aggregated by summing up their respective number values. So inputting ((1 abc)(2 abc)(4 xyz)) into the function would return ((3 abc)(4 xyz)). From there we can use it in two ways: for collecting polynomial terms by setting "number" to be the constant associated with that term, and "data" the term itself, but we can also use it for simplifying terms after multiplying them by setting "number" to be the exponent of a variable and "data" the variable itself. Makes sense?

 

[JamesBwoii]

Well you have to tell the function which part of the element is the "constant" (to add together). For polynomial terms we defined it to be the first part in (constant, term). For exponents we "defined" it to be the second part in (variable, exponent). So we can't directly use the same function in that case. But switching around to (exponent, variable) costs us nothing since we haven't begun to operate on variables and exponents yet.

- - - Updated - - -

Here the idea is to think of the function no longer as simply "collecting terms" but being a generic function that operates on a list of elements of the form (number, data) where consecutive elements with the same data are aggregated by summing up their respective number values. So inputting ((1 abc)(2 abc)(4 xyz)) into the function would return ((3 abc)(4 xyz)). From there we can use it in two ways: for collecting polynomial terms by setting "number" to be the constant associated with that term, and "data" the term itself, but we can also use it for simplifying terms after multiplying them by setting "number" to be the exponent of a variable and "data" the variable itself. Makes sense?

Still slightly confused. Are you saying that $5x^2$ should now be represented as (5(2 x)) as opposed to the old way (5(x 2))?

Thanks!

 

[Nono713]

Still slightly confused. Are you saying that $5x^2$ should now be represented as (5(2 x)) as opposed to the old way (5(x 2))?

Thanks!

Yes. That would make it consistent with the function's operation.

 

[Nono713]

Ok, that makes sense and I've changed it now to represent the new way. I'm having a bit of an issue with some Lisp syntax for the base case. I know the logic behind what I want to do. I think the best way is to say when the remainder, the variable that holds everything after the first two polynomials is empty, return the polynomial.

In code:

    (if(eq nil remainder)
       (p1))

I get a warning saying that P1 is an undefined function. This is probably a stupid question but I just can't seem to get it working.

Actually that's not quite right (your logic). If the remainder is nil, there could still be 2 elements in the list, so they should still be collected. What you need to check for is when there are less than 2 elements, and that happens if (and only if) the second element is nil. So this is the element you should check against for the base case. (you're getting there!)

As for your second question, I used the "null" function to check for nil:

(if (null yourvar)
    ; ...
)

 

[JamesBwoii]

Actually that's not quite right (your logic). If the remainder is nil, there could still be 2 elements in the list, so they should still be collected. What you need to check for is when there are less than 2 elements, and that happens if (and only if) the second element is nil. So this is the element you should check against for the base case. (you're getting there!)

As for your second question, I used the "null" function to check for nil:

(if (null yourvar)
    ; ...
)

Of course, obvious now you've said it! I've created a new variable that holds the second element of the list:

       (second-element(car(cdr p1))))

and then this is my base case:

    (if(null second-element )
       p1)

Not sure if it's working though, when running it I still end up with NIL being the last thing printed to the console.

 

[Nono713]

Of course, obvious now you've said it! I've created a new variable that holds the second element of the list:

       (second-element(car(cdr p1))))

and then this is my base case:

    (if(null second-element )
       p1)

Not sure if it's working though, when running it I still end up with NIL being the last thing printed to the console.

Well, there's two things I can think of. One, are you actually printing the result of the function? Like this at the end:

(print(poly ...))

Also, perhaps the "p1" here in your code doesn't act as a "return" like in imperative languages. I must confess my Lisp is not good enough to answer that question, but in my implementation I used an if/else so that if the second element is not null, then the function continues with the logic and checks if the two elements are equal and so on... you could try this (to be honest it seems it should work that way, as a functional language)

 

[JamesBwoii]

I couldn't seem to get the 'if else' code working in Lisp so I just left it as two separate ifs. I think it's working as it should now.

Here's the code:

(defun poly (p1)
  (let((e1(car(car(cdr(car p1))))) (e2(car(car(cdr(car(cdr p1))))))
       (x1(car(cdr(car(cdr(car p1)))))) (x2(car(cdr(car(cdr(car(cdr p1)))))))
       (c1(car(car p1))) (c2(car(car(cdr p1))))
       (remainder(cdr(cdr p1)))
       (second-element (car(cdr p1))))
    
    (if(null second-element)
      (format t "~a~%" p1)

    (if(and(equal x1 x2)(equal e1 e2))
      (poly(append (list(list(+ c1 c2)(list e1 x1))) remainder))
      (format t "~a~%" p1)))))

Given input:

(poly '((5(2 x))(3(2 x))(10(2 x))(15(2 x))(20(2 x))))

Output is:

((53 (2 X)))
NIL

And input with a Y variable on the end.

(poly '((5(2 x))(3(2 x))(10(2 x))(15(2 x))(20(2 y))))

gives

((33 (2 X)) (20 (2 Y)))
NIL

 

[Nono713]

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:

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