close
Warning:
Can't synchronize with repository "(default)" (The repository directory has changed, you should resynchronize the repository with: trac-admin $ENV repository resync '(default)'). Look in the Trac log for more information.
Rev | Line | |
---|
[4495] | 1 | (in-package :polynomial)
|
---|
| 2 |
|
---|
| 3 | (defun f-add (p q order-fn add-fn)
|
---|
| 4 | "Add two polynomials, P and Q, represented as lists of terms.
|
---|
| 5 | The operation is destructive to both polynomials, as the terms
|
---|
| 6 | of both lists are combined into the result. The operation does not
|
---|
| 7 | create any new instance of TERM."
|
---|
| 8 | (do (r)
|
---|
| 9 | ((or (endp p) (endp q))
|
---|
| 10 | ;; NOTE: R contains the result in reverse order. Can it
|
---|
| 11 | ;; be more efficient to produce the terms in correct order?
|
---|
| 12 | (unless (endp q)
|
---|
| 13 | (setf r (nreconc r q)))
|
---|
| 14 | (unless (endp p)
|
---|
| 15 | (setf r (nreconc r p)))
|
---|
| 16 | r)
|
---|
| 17 | (multiple-value-bind
|
---|
| 18 | (greater-p equal-p)
|
---|
| 19 | (funcall order-fn (car p) (car q))
|
---|
| 20 | (cond
|
---|
| 21 | (greater-p
|
---|
| 22 | (rotatef (cdr p) r p)
|
---|
| 23 | )
|
---|
| 24 | (equal-p
|
---|
| 25 | (let ((s (funcall add-fn (lc p) (lc q))))
|
---|
| 26 | (cond
|
---|
| 27 | ((universal-zerop s)
|
---|
| 28 | (setf p (cdr p))
|
---|
| 29 | )
|
---|
| 30 | (t
|
---|
| 31 | (setf (lc p) s)
|
---|
| 32 | (rotatef (cdr p) r p))))
|
---|
| 33 | (setf q (cdr q))
|
---|
| 34 | )
|
---|
| 35 | (t
|
---|
| 36 | (rotatef (cdr q) r q))))))
|
---|
[4537] | 37 |
|
---|
| 38 | (defun s-add (p q order-fn add-fn &aux result)
|
---|
[4538] | 39 | "Non-recursive version of SLOW-ADD. This version uses auxillary variable
|
---|
| 40 | RESULT which serves as a stack for the terms of the sum of P and Q."
|
---|
[4537] | 41 | (loop
|
---|
| 42 | (cond
|
---|
| 43 | ((endp p) (return-from s-add (nreconc result q)))
|
---|
| 44 | ((endp q) (return-from s-add (nreconc result p)))
|
---|
| 45 | (t
|
---|
| 46 | (multiple-value-bind
|
---|
| 47 | (greater-p equal-p)
|
---|
| 48 | (funcall order-fn (car p) (car q))
|
---|
| 49 | (cond
|
---|
| 50 | (greater-p ; (> (car p) (car q))
|
---|
| 51 | (push (pop p) result)
|
---|
| 52 | )
|
---|
| 53 | (equal-p ; (= (car p)) (car q))
|
---|
| 54 | (let ((s (funcall add-fn (lc p) (lc q))))
|
---|
| 55 | (cond
|
---|
| 56 | ((universal-zerop s)
|
---|
| 57 | (pop p))
|
---|
| 58 | (t
|
---|
| 59 | ;; Adjust the lc of p
|
---|
| 60 | (setf (lc p) s)
|
---|
| 61 | (push (pop p) result)
|
---|
| 62 | )
|
---|
| 63 | ))
|
---|
| 64 | (pop q)
|
---|
| 65 | )
|
---|
| 66 | (t ;(< (car p) (car q))
|
---|
| 67 | (push (pop q) result)
|
---|
| 68 | )
|
---|
| 69 | ))))))
|
---|
Note:
See
TracBrowser
for help on using the repository browser.
Download in other formats: