I came across an article (http://www.dreamsongs.com/10ideas.html) that
mentioned, in passing, a very elegant way to multiply polynomials in
lisp. I tried to implement mult-poly on my own, and it turned out
almost exactly as shown in the article (I didn't peek until after),
but the author says that add-poly can be done in a line or two, and
I'm damned if I can see how, barring just removing line breaks and
making one big line of it. Can anyone see how it would be done?
General comments on my style or lack thereof are also welcome. This
is in PLT scheme.
(define (mult-poly p1 p2)
(define (mult-poly-const c p)
(map (lambda (x) (* c x)) p))
(define (add-poly p1 p2)
(cond ((and (null? p1) (null? p2)) ())
((null? p1) p2)
((null? p2) p1)
(else (cons (+ (car p1) (car p2)) (add-poly (cdr p1) (cdr
p2))))))
(cond ((or (null? p1) (null? p2)) ())
((atom? p1) (mult-poly-const p1 p2))
(else (add-poly
(mult-poly-const
(car p1) p2)
(cons 0 (mult-poly (cdr p1) p2))))))
In article <···························@posting.google.com>,
···········@gmail.com (matt knox) wrote:
> I came across an article (http://www.dreamsongs.com/10ideas.html) that
> mentioned, in passing, a very elegant way to multiply polynomials in
> lisp. I tried to implement mult-poly on my own, and it turned out
> almost exactly as shown in the article (I didn't peek until after),
> but the author says that add-poly can be done in a line or two, and
> I'm damned if I can see how, barring just removing line breaks and
> making one big line of it. Can anyone see how it would be done?
> General comments on my style or lack thereof are also welcome. This
> is in PLT scheme.
>
>
> (define (mult-poly p1 p2)
> (define (mult-poly-const c p)
> (map (lambda (x) (* c x)) p))
> (define (add-poly p1 p2)
> (cond ((and (null? p1) (null? p2)) ())
> ((null? p1) p2)
> ((null? p2) p1)
> (else (cons (+ (car p1) (car p2)) (add-poly (cdr p1) (cdr
> p2))))))
> (cond ((or (null? p1) (null? p2)) ())
> ((atom? p1) (mult-poly-const p1 p2))
> (else (add-poly
> (mult-poly-const
> (car p1) p2)
> (cons 0 (mult-poly (cdr p1) p2))))))
In Common Lisp isn't it just the MAPCAR function?
(mapcar #'+ '(20 10 30) '(10 12 14)) -> ...
"Rainer Joswig" <······@lisp.de> wrote in message
·································@news-50.dca.giganews.com...
>
> In Common Lisp isn't it just the MAPCAR function?
>
> (mapcar #'+ '(20 10 30) '(10 12 14)) -> ...
Don't you need to make sure that the polynomials have the same length?
something like:
(defun add-poly (a b &aux (diff (- (length a) (length b))))
(cond ((> 0 diff) (setf a (append (loop for i from 0 below (abs diff)
collecting 0) a)))
((< 0 diff) (setf b (append (loop for i from 0 below (abs diff)
collecting 0) b)))
(t 'nothing-to-do))
(mapcar #'+ a b))
"Raistlin Magere" <·······@*the-mail-that-burns*.com> wrote in message news:<············@news.ox.ac.uk>...
> "Rainer Joswig" <······@lisp.de> wrote in message
> ·································@news-50.dca.giganews.com...
> >
> > In Common Lisp isn't it just the MAPCAR function?
> >
> > (mapcar #'+ '(20 10 30) '(10 12 14)) -> ...
>
> Don't you need to make sure that the polynomials have the same length?
> something like:
>
> (defun add-poly (a b &aux (diff (- (length a) (length b))))
> (cond ((> 0 diff) (setf a (append (loop for i from 0 below (abs diff)
> collecting 0) a)))
> ((< 0 diff) (setf b (append (loop for i from 0 below (abs diff)
> collecting 0) b)))
> (t 'nothing-to-do))
> (mapcar #'+ a b))
How about this one:
(defun add-poly (a b)
(loop for x = a then (rest x) and y = b then (rest y)
while (or x y)
collect (+ (or (first x) 0) (or (first y) 0))))
CL-USER 3 > (add-poly '(1 2 3) '(1 2 3 4))
(2 4 6 4)
"Rainer Joswig" <······@corporate-world.lisp.de> wrote in message
································@posting.google.com...
> "Raistlin Magere" <·······@*the-mail-that-burns*.com> wrote in message
news:<············@news.ox.ac.uk>...
> >
> > Don't you need to make sure that the polynomials have the same length?
> > something like:
> >
> > (defun add-poly (a b &aux (diff (- (length a) (length b))))
> > (cond ((> 0 diff) (setf a (append (loop for i from 0 below (abs diff)
> > collecting 0) a)))
> > ((< 0 diff) (setf b (append (loop for i from 0 below (abs
diff)
> > collecting 0) b)))
> > (t 'nothing-to-do))
> > (mapcar #'+ a b))
>
> How about this one:
>
> (defun add-poly (a b)
> (loop for x = a then (rest x) and y = b then (rest y)
> while (or x y)
> collect (+ (or (first x) 0) (or (first y) 0))))
>
> CL-USER 3 > (add-poly '(1 2 3) '(1 2 3 4))
> (2 4 6 4)
That is also fine although it depends of what are one's assumption on the
meaning of (1 2 3) i.e. is it 1 + 2*x + 3*x^2 (which seems to be what you
have assumed) or 1 * x^2 + 2 *x + 3 (which is what I have assumed). As my
code would have generated for (add-poly '(1 2 3) '(1 2 3 4)) -> (1 3 5 7)
From: Richard Fateman
Subject: Re: request for style evaluation-multiplying polynomials
Date:
Message-ID: <411FB3AE.20202@sbcglobal.net>
Either way, starting with high degree or not, you need to do some more
checking. In particular,
polynomial addition of (1 2 3 4) and (-1 -2 -3 -4) should be
() rather than (0 0 0 0).
Programs to do polynomial arithmetic usually require a normalization
step.
There is also a question as to whether
one might prefer 0 to (). If you represent constant polynomials as
lisp constants, you benefit in various ways, especially if you allow
multiple variables, e.g. polynomials in x,y,z,w ... which can be done
with remarkably little code, too.
RJF
Raistlin Magere wrote:
> "Rainer Joswig" <······@corporate-world.lisp.de> wrote in message
> ································@posting.google.com...
>
>>"Raistlin Magere" <·······@*the-mail-that-burns*.com> wrote in message
>
> news:<············@news.ox.ac.uk>...
>
>>>Don't you need to make sure that the polynomials have the same length?
>>>something like:
>>>
>>>(defun add-poly (a b &aux (diff (- (length a) (length b))))
>>> (cond ((> 0 diff) (setf a (append (loop for i from 0 below (abs diff)
>>>collecting 0) a)))
>>> ((< 0 diff) (setf b (append (loop for i from 0 below (abs
>
> diff)
>
>>>collecting 0) b)))
>>> (t 'nothing-to-do))
>>> (mapcar #'+ a b))
>>
>>How about this one:
>>
>>(defun add-poly (a b)
>> (loop for x = a then (rest x) and y = b then (rest y)
>> while (or x y)
>> collect (+ (or (first x) 0) (or (first y) 0))))
>>
>>CL-USER 3 > (add-poly '(1 2 3) '(1 2 3 4))
>>(2 4 6 4)
>
>
> That is also fine although it depends of what are one's assumption on the
> meaning of (1 2 3) i.e. is it 1 + 2*x + 3*x^2 (which seems to be what you
> have assumed) or 1 * x^2 + 2 *x + 3 (which is what I have assumed). As my
> code would have generated for (add-poly '(1 2 3) '(1 2 3 4)) -> (1 3 5 7)
>
>
"Richard Fateman" <········@sbcglobal.net> wrote in message
···················@sbcglobal.net...
> Either way, starting with high degree or not, you need to do some more
> checking. In particular,
> polynomial addition of (1 2 3 4) and (-1 -2 -3 -4) should be
> () rather than (0 0 0 0).
> Programs to do polynomial arithmetic usually require a normalization
> step.
I agree that (0 0 0 0) is not the prefered answer (as I actually had thought
of that issue) however the original poster was asking how it was possible to
add two polynomials in a few lines and to include a normalization function
like the following would have increased the length of the code. Furthermore
as you state the need to normalize is a requirement of the whole polynomial
arithmetic and therefore I believe it should be external to just `add-poly'
and within add-poly the mapcar call should be wrapped within (normalize-poly
...)
(defun normalize-poly (poly &key (null-value (list 0)))
(cond ((null poly) null-value)
((= (first poly) 0) (normalize-poly (rest poly) :null-value
null-value))
(t poly)))
>
> There is also a question as to whether
> one might prefer 0 to (). If you represent constant polynomials as
> lisp constants, you benefit in various ways, especially if you allow
> multiple variables, e.g. polynomials in x,y,z,w ... which can be done
> with remarkably little code, too.
>
That is something I had forgotten i.e. polynomials with multiple variables.
Interesting
rm
Rainer Joswig <······@lisp.de> wrote in message news:<····························@news-50.dca.giganews.com>...
> In article <···························@posting.google.com>,
> ···········@gmail.com (matt knox) wrote:
>
> > I came across an article (http://www.dreamsongs.com/10ideas.html) that
> > mentioned, in passing, a very elegant way to multiply polynomials in
> > lisp. I tried to implement mult-poly on my own, and it turned out
> > almost exactly as shown in the article (I didn't peek until after),
> > but the author says that add-poly can be done in a line or two, and
> > I'm damned if I can see how, barring just removing line breaks and
> > making one big line of it. Can anyone see how it would be done?
> > General comments on my style or lack thereof are also welcome. This
> > is in PLT scheme.
> >
> >
> > (define (mult-poly p1 p2)
> > (define (mult-poly-const c p)
> > (map (lambda (x) (* c x)) p))
> > (define (add-poly p1 p2)
> > (cond ((and (null? p1) (null? p2)) ())
> > ((null? p1) p2)
> > ((null? p2) p1)
> > (else (cons (+ (car p1) (car p2)) (add-poly (cdr p1) (cdr
> > p2))))))
> > (cond ((or (null? p1) (null? p2)) ())
> > ((atom? p1) (mult-poly-const p1 p2))
> > (else (add-poly
> > (mult-poly-const
> > (car p1) p2)
> > (cons 0 (mult-poly (cdr p1) p2))))))
>
> In Common Lisp isn't it just the MAPCAR function?
>
> (mapcar #'+ '(20 10 30) '(10 12 14)) -> ...
Duh. Yeah, that'll work.
From: Richard Fateman
Subject: Re: request for style evaluation-multiplying polynomials
Date:
Message-ID: <412812F5.3090204@sbcglobal.net>
matt knox wrote:
>
(re: adding polynomials)
>>In Common Lisp isn't it just the MAPCAR function?
>>
>>(mapcar #'+ '(20 10 30) '(10 12 14)) -> ...
>
>
> Duh. Yeah, that'll work.
Not really. Only if the polynomials are of the same degree.
RJF