1 | ;;; -*- Mode: Lisp -*-
|
---|
2 | ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
---|
3 | ;;;
|
---|
4 | ;;; Copyright (C) 1999, 2002, 2009, 2015 Marek Rychlik <rychlik@u.arizona.edu>
|
---|
5 | ;;;
|
---|
6 | ;;; This program is free software; you can redistribute it and/or modify
|
---|
7 | ;;; it under the terms of the GNU General Public License as published by
|
---|
8 | ;;; the Free Software Foundation; either version 2 of the License, or
|
---|
9 | ;;; (at your option) any later version.
|
---|
10 | ;;;
|
---|
11 | ;;; This program is distributed in the hope that it will be useful,
|
---|
12 | ;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
13 | ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
14 | ;;; GNU General Public License for more details.
|
---|
15 | ;;;
|
---|
16 | ;;; You should have received a copy of the GNU General Public License
|
---|
17 | ;;; along with this program; if not, write to the Free Software
|
---|
18 | ;;; Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
|
---|
19 | ;;;
|
---|
20 | ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
---|
21 |
|
---|
22 | (defpackage "TERMLIST"
|
---|
23 | (:use :cl :monom :ring :ring-and-order :term)
|
---|
24 | (:export "TERMLIST-SUGAR"
|
---|
25 | "TERMLIST-CONTRACT"
|
---|
26 | "TERMLIST-EXTEND"
|
---|
27 | "TERMLIST-ADD-VARIABLES"
|
---|
28 | "TERMLIST-LT"
|
---|
29 | "TERMLIST-LM"
|
---|
30 | "TERMLIST-LC"
|
---|
31 | "SCALAR-MUL"
|
---|
32 | "SCALAR-TIMES-TERMLIST"
|
---|
33 | "TERM-MUL-LST"
|
---|
34 | "TERMLIST-TIMES-TERM"
|
---|
35 | "TERM-TIMES-TERMLIST"
|
---|
36 | "MONOM-TIMES-TERM"
|
---|
37 | "MONOM-TIMES-TERMLIST"
|
---|
38 | "TERMLIST-UMINUS"
|
---|
39 | "TERMLIST-ADD"
|
---|
40 | "TERMLIST-SUB"
|
---|
41 | "TERMLIST-MUL"
|
---|
42 | "TERMLIST-UNIT"
|
---|
43 | "TERMLIST-EXPT"))
|
---|
44 |
|
---|
45 | (in-package :termlist)
|
---|
46 |
|
---|
47 | (defun termlist-sugar (p &aux (sugar -1))
|
---|
48 | (declare (fixnum sugar))
|
---|
49 | (dolist (term p sugar)
|
---|
50 | (setf sugar (max sugar (term-sugar term)))))
|
---|
51 |
|
---|
52 | (defun termlist-contract (p &optional (k 1))
|
---|
53 | "Eliminate first K variables from a polynomial P."
|
---|
54 | (mapcar #'(lambda (term) (make-term :monom (monom-contract (term-monom term) k)
|
---|
55 | :coeff (term-coeff term)))
|
---|
56 | p))
|
---|
57 |
|
---|
58 | (defun termlist-extend (p &optional (m (make-monom :dimension 1)))
|
---|
59 | "Extend every monomial in a polynomial P by inserting at the
|
---|
60 | beginning of every monomial the list of powers M."
|
---|
61 | (mapcar #'(lambda (term) (make-term :monom (monom-append m (term-monom term))
|
---|
62 | :coeff (term-coeff term)))
|
---|
63 | p))
|
---|
64 |
|
---|
65 | (defun termlist-add-variables (p n)
|
---|
66 | "Add N variables to a polynomial P by inserting zero powers
|
---|
67 | at the beginning of each monomial."
|
---|
68 | (declare (fixnum n))
|
---|
69 | (mapcar #'(lambda (term)
|
---|
70 | (make-term (monom-append (make-monom :dimension n)
|
---|
71 | (term-monom term))
|
---|
72 | (term-coeff term)))
|
---|
73 | p))
|
---|
74 |
|
---|
75 |
|
---|
76 | ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
---|
77 | ;;
|
---|
78 | ;; Low-level polynomial arithmetic done on
|
---|
79 | ;; lists of terms
|
---|
80 | ;;
|
---|
81 | ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
---|
82 |
|
---|
83 | (defmacro termlist-lt (p) `(car ,p))
|
---|
84 | (defun termlist-lm (p) (term-monom (termlist-lt p)))
|
---|
85 | (defun termlist-lc (p) (term-coeff (termlist-lt p)))
|
---|
86 |
|
---|
87 | (define-modify-macro scalar-mul (c) coeff-mul)
|
---|
88 |
|
---|
89 | (defun scalar-times-termlist (ring c p)
|
---|
90 | "Multiply scalar C by a polynomial P. This function works
|
---|
91 | even if there are divisors of 0."
|
---|
92 | (declare (ring ring))
|
---|
93 | (mapcan
|
---|
94 | #'(lambda (term)
|
---|
95 | (let ((c1 (funcall (ring-mul ring) c (term-coeff term))))
|
---|
96 | (unless (funcall (ring-zerop ring) c1)
|
---|
97 | (list (make-term (term-monom term) c1)))))
|
---|
98 | p))
|
---|
99 |
|
---|
100 |
|
---|
101 | (defun term-mul-lst (ring term1 term2)
|
---|
102 | "A special version of term multiplication. Returns (LIST TERM) where
|
---|
103 | TERM is the product of the terms TERM1 TERM2, or NIL when the product
|
---|
104 | is 0. This definition takes care of divisors of 0 in the coefficient
|
---|
105 | ring."
|
---|
106 | (declare (ring ring))
|
---|
107 | (let ((c (funcall (ring-mul ring) (term-coeff term1) (term-coeff term2))))
|
---|
108 | (unless (funcall (ring-zerop ring) c)
|
---|
109 | (list (make-term (monom-mul (term-monom term1) (term-monom term2)) c)))))
|
---|
110 |
|
---|
111 | (defun term-times-termlist (ring term f)
|
---|
112 | (declare (type ring ring))
|
---|
113 | (mapcan #'(lambda (term-f) (term-mul-lst ring term term-f)) f))
|
---|
114 |
|
---|
115 | (defun termlist-times-term (ring f term)
|
---|
116 | (declare (ring ring))
|
---|
117 | (mapcan #'(lambda (term-f) (term-mul-lst ring term-f term)) f))
|
---|
118 |
|
---|
119 | (defun monom-times-term (m term)
|
---|
120 | (make-term (monom-mul m (term-monom term)) (term-coeff term)))
|
---|
121 |
|
---|
122 | (defun monom-times-termlist (m f)
|
---|
123 | (cond
|
---|
124 | ((null f) nil)
|
---|
125 | (t
|
---|
126 | (mapcar #'(lambda (x) (monom-times-term m x)) f))))
|
---|
127 |
|
---|
128 | (defun termlist-uminus (ring f)
|
---|
129 | (declare (ring ring))
|
---|
130 | (mapcar #'(lambda (x)
|
---|
131 | (make-term (term-monom x) (funcall (ring-uminus ring) (term-coeff x))))
|
---|
132 | f))
|
---|
133 |
|
---|
134 | (defun termlist-add (ring-and-order p q
|
---|
135 | &aux
|
---|
136 | (ring (ro-ring ring-and-order))
|
---|
137 | (order (ro-order ring-and-order)))
|
---|
138 | (declare (type list p q) (ring-and-order ring-and-order))
|
---|
139 | (do (r)
|
---|
140 | ((cond
|
---|
141 | ((endp p)
|
---|
142 | (setf r (revappend r q)) t)
|
---|
143 | ((endp q)
|
---|
144 | (setf r (revappend r p)) t)
|
---|
145 | (t
|
---|
146 | (multiple-value-bind
|
---|
147 | (lm-greater lm-equal)
|
---|
148 | (funcall order (termlist-lm p) (termlist-lm q))
|
---|
149 | (cond
|
---|
150 | (lm-equal
|
---|
151 | (let ((s (funcall (ring-add ring) (termlist-lc p) (termlist-lc q))))
|
---|
152 | (unless (funcall (ring-zerop ring) s) ;check for cancellation
|
---|
153 | (setf r (cons (make-term (termlist-lm p) s) r)))
|
---|
154 | (setf p (cdr p) q (cdr q))))
|
---|
155 | (lm-greater
|
---|
156 | (setf r (cons (car p) r)
|
---|
157 | p (cdr p)))
|
---|
158 | (t (setf r (cons (car q) r)
|
---|
159 | q (cdr q)))))
|
---|
160 | nil))
|
---|
161 | r)))
|
---|
162 |
|
---|
163 | (defun termlist-sub (ring-and-order p q
|
---|
164 | &aux
|
---|
165 | (ring (ro-ring ring-and-order))
|
---|
166 | (order (ro-order ring-and-order)))
|
---|
167 | (declare (type list p q) (ring-and-order ring-and-order))
|
---|
168 | (do (r)
|
---|
169 | ((cond
|
---|
170 | ((endp p)
|
---|
171 | (setf r (revappend r (termlist-uminus ring q)))
|
---|
172 | t)
|
---|
173 | ((endp q)
|
---|
174 | (setf r (revappend r p))
|
---|
175 | t)
|
---|
176 | (t
|
---|
177 | (multiple-value-bind
|
---|
178 | (mgreater mequal)
|
---|
179 | (funcall order (termlist-lm p) (termlist-lm q))
|
---|
180 | (cond
|
---|
181 | (mequal
|
---|
182 | (let ((s (funcall (ring-sub ring) (termlist-lc p) (termlist-lc q))))
|
---|
183 | (unless (funcall (ring-zerop ring) s) ;check for cancellation
|
---|
184 | (setf r (cons (make-term (termlist-lm p) s) r)))
|
---|
185 | (setf p (cdr p) q (cdr q))))
|
---|
186 | (mgreater
|
---|
187 | (setf r (cons (car p) r)
|
---|
188 | p (cdr p)))
|
---|
189 | (t (setf r (cons (make-term (termlist-lm q)
|
---|
190 | (funcall (ring-uminus ring) (termlist-lc q))) r)
|
---|
191 | q (cdr q)))))
|
---|
192 | nil))
|
---|
193 | r)))
|
---|
194 |
|
---|
195 | ;; Multiplication of polynomials
|
---|
196 | ;; Non-destructive version
|
---|
197 | (defun termlist-mul (ring-and-order p q
|
---|
198 | &aux (ring (ro-ring ring-and-order)))
|
---|
199 | (declare (ring-and-order ring-and-order))
|
---|
200 | (cond ((or (endp p) (endp q)) nil) ;p or q is 0 (represented by NIL)
|
---|
201 | ;; If p=p0+p1 and q=q0+q1 then pq=p0q0+p0q1+p1q
|
---|
202 | ((endp (cdr p))
|
---|
203 | (term-times-termlist ring (car p) q))
|
---|
204 | ((endp (cdr q))
|
---|
205 | (termlist-times-term ring p (car q)))
|
---|
206 | (t
|
---|
207 | (let ((head (term-mul-lst ring (termlist-lt p) (termlist-lt q)))
|
---|
208 | (tail (termlist-add ring-and-order
|
---|
209 | (term-times-termlist ring (car p) (cdr q))
|
---|
210 | (termlist-mul ring-and-order (cdr p) q))))
|
---|
211 | (cond ((null head) tail)
|
---|
212 | ((null tail) head)
|
---|
213 | (t (nconc head tail)))))))
|
---|
214 |
|
---|
215 | (defun termlist-unit (ring dim)
|
---|
216 | (declare (fixnum dim) (ring ring))
|
---|
217 | (list (make-term (make-monom :dimension dim) (funcall (ring-unit ring)))))
|
---|
218 |
|
---|
219 |
|
---|
220 | (defun termlist-expt (ring-and-order poly n
|
---|
221 | &aux
|
---|
222 | (ring (ro-ring ring-and-order))
|
---|
223 | (dim (monom-dimension (termlist-lm poly))))
|
---|
224 | (declare (type fixnum n dim) (ring-and-order ring-and-order))
|
---|
225 | (cond
|
---|
226 | ((minusp n) (error "termlist-expt: Negative exponent."))
|
---|
227 | ((endp poly) (if (zerop n) (termlist-unit ring dim) nil))
|
---|
228 | (t
|
---|
229 | (do ((k 1 (ash k 1))
|
---|
230 | (q poly (termlist-mul ring-and-order q q)) ;keep squaring
|
---|
231 | (p (termlist-unit ring dim) (if (not (zerop (logand k n))) (termlist-mul ring-and-order p q) p)))
|
---|
232 | ((> k n) p)
|
---|
233 | (declare (fixnum k))))))
|
---|