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.

source: branches/f4grobner/polynomial.lisp@ 4401

Last change on this file since 4401 was 4396, checked in by Marek Rychlik, 8 years ago

* empty log message *

File size: 23.1 KB
Line 
1;;----------------------------------------------------------------
2;;; -*- Mode: Lisp -*-
3;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
4;;;
5;;; Copyright (C) 1999, 2002, 2009, 2015 Marek Rychlik <rychlik@u.arizona.edu>
6;;;
7;;; This program is free software; you can redistribute it and/or modify
8;;; it under the terms of the GNU General Public License as published by
9;;; the Free Software Foundation; either version 2 of the License, or
10;;; (at your option) any later version.
11;;;
12;;; This program is distributed in the hope that it will be useful,
13;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
14;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15;;; GNU General Public License for more details.
16;;;
17;;; You should have received a copy of the GNU General Public License
18;;; along with this program; if not, write to the Free Software
19;;; Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20;;;
21;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
22
23(defpackage "POLYNOMIAL"
24 (:use :cl :utils :monom :copy :ring)
25 (:export "POLY"
26 "POLY-DIMENSION"
27 "POLY-TERMLIST"
28 "POLY-TERM-ORDER"
29 "POLY-INSERT-TERM"
30 "SCALAR-MULTIPLY-BY"
31 "SCALAR-DIVIDE-BY"
32 "LEADING-TERM"
33 "LEADING-MONOMIAL"
34 "LEADING-COEFFICIENT"
35 "SECOND-LEADING-TERM"
36 "SECOND-LEADING-MONOMIAL"
37 "SECOND-LEADING-COEFFICIENT"
38 "ADD-TO"
39 "ADD"
40 "SUBTRACT-FROM"
41 "SUBTRACT"
42 "CHANGE-TERM-ORDER"
43 "STANDARD-EXTENSION"
44 "STANDARD-EXTENSION-1"
45 "STANDARD-SUM"
46 "SATURATION-EXTENSION"
47 "ALIST->POLY"
48 "->INFIX"
49 "UNIVERSAL-EZGCD"
50 "S-POLYNOMIAL"
51 "POLY-CONTENT"
52 "POLY-PRIMITIVE-PART"
53 "SATURATION-EXTENSION-1"
54 "MAKE-POLY-VARIABLE"
55 "MAKE-POLY-CONSTANT"
56 "MAKE-ZERO-FOR"
57 "MAKE-UNIT-FOR"
58 "UNIVERSAL-EXPT"
59 "UNIVERSAL-EQUALP"
60 "UNIVERSAL-ZEROP"
61 "POLY-LENGTH"
62 "POLY-REVERSE"
63 "POLY-P"
64 "+LIST-MARKER+"
65 "POLY-EVAL"
66 "*COEFFICIENT-CLASS*")
67 (:documentation "Implements polynomials. A polynomial is essentially
68a mapping of monomials of the same degree to coefficients. The
69momomials are ordered according to a monomial order."))
70
71(in-package :polynomial)
72
73(proclaim '(optimize (speed 3) (space 0) (safety 0) (debug 0)))
74
75(defclass poly (ring)
76 ((dimension :initform nil
77 :initarg :dimension
78 :accessor poly-dimension
79 :documentation "Shared dimension of all terms, the number of variables")
80 (termlist :initform nil :initarg :termlist :accessor poly-termlist
81 :documentation "List of terms.")
82 (order :initform #'lex> :initarg :order :accessor poly-term-order
83 :documentation "Monomial/term order."))
84 (:default-initargs :dimension nil :termlist nil :order #'lex>)
85 (:documentation "A polynomial with a list of terms TERMLIST, ordered
86according to term order ORDER, which defaults to LEX>."))
87
88(defmethod print-object ((self poly) stream)
89 (print-unreadable-object (self stream :type t :identity t)
90 (with-accessors ((dimension poly-dimension)
91 (termlist poly-termlist)
92 (order poly-term-order))
93 self
94 (format stream "DIMENSION=~A TERMLIST=~A ORDER=~A"
95 dimension termlist order))))
96
97(defmethod copy-instance :around ((object poly) &rest initargs &key &allow-other-keys)
98 "Returns a deep copy of the polynomial POLY, by copying the TERMLIST and its terms."
99 (declare (ignore object initargs))
100 (let ((copy (call-next-method)))
101 (with-slots (termlist)
102 copy
103 (setf termlist (mapcar #'copy-instance termlist)))
104 copy))
105
106
107(defgeneric change-term-order (self other)
108 (:documentation "Change term order of SELF to the term order of OTHER.")
109 (:method ((self poly) (other poly))
110 (unless (eq (poly-term-order self) (poly-term-order other))
111 (setf (poly-termlist self) (sort (poly-termlist self) (poly-term-order other))
112 (poly-term-order self) (poly-term-order other)))
113 self))
114
115(defgeneric poly-insert-term (self term)
116 (:documentation "Insert a term TERM into SELF before all other
117terms. Order is not enforced.")
118 (:method ((self poly) (term term))
119 (cond ((null (poly-dimension self))
120 (setf (poly-dimension self) (monom-dimension term)))
121 (t (assert (= (poly-dimension self) (monom-dimension term)))))
122 (push term (poly-termlist self))
123 self))
124
125(defgeneric poly-append-term (self term)
126 (:documentation "Append a term TERM to SELF after all other terms. Order is not enforced.")
127 (:method ((self poly) (term term))
128 (cond ((null (poly-dimension self))
129 (setf (poly-dimension self) (monom-dimension term)))
130 (t (assert (= (poly-dimension self) (monom-dimension term)))))
131 (setf (cdr (last (poly-termlist self))) (list term))
132 self))
133
134(defun alist->poly (alist &aux (poly (make-instance 'poly)))
135 "It reads polynomial from an alist formatted as ( ... (exponents . coeff) ...).
136It can be used to enter simple polynomials by hand, e.g the polynomial
137in two variables, X and Y, given in standard notation as:
138
139 3*X^2*Y^3+2*Y+7
140
141can be entered as
142(ALIST->POLY '(((2 3) . 3) ((0 1) . 2) ((0 0) . 7))).
143
144NOTE: The primary use is for low-level debugging of the package."
145 (dolist (x alist poly)
146 (poly-insert-term poly (make-instance 'term :exponents (car x) :coeff (cdr x)))))
147
148(defmethod update-instance-for-different-class :after ((old term) (new poly) &key)
149 "Converts OLD of class TERM to a NEW of class POLY, by making it into a 1-element TERMLIST."
150 (reinitialize-instance new
151 :dimension (monom-dimension old)
152 :termlist (list old)))
153
154(defmethod update-instance-for-different-class :after ((old monom) (new poly) &key)
155 "Converts OLD of class MONOM to a NEW of class POLY, by making it into a 1-element TERMLIST."
156 (reinitialize-instance new
157 :dimension (monom-dimension old)
158 :termlist (list (change-class old 'term))))
159
160(defmethod universal-equalp ((self poly) (other poly))
161 "Implements equality of polynomials."
162 (and (eql (poly-dimension self) (poly-dimension other))
163 (every #'universal-equalp (poly-termlist self) (poly-termlist other))
164 (eq (poly-term-order self) (poly-term-order other))))
165
166(defgeneric leading-term (object)
167 (:method ((self poly))
168 (car (poly-termlist self)))
169 (:documentation "The leading term of a polynomial, or NIL for zero polynomial."))
170
171(defgeneric second-leading-term (object)
172 (:method ((self poly))
173 (cadar (poly-termlist self)))
174 (:documentation "The second leading term of a polynomial, or NIL for a polynomial with at most one term."))
175
176(defgeneric leading-monomial (object)
177 (:method ((self poly))
178 (change-class (copy-instance (leading-term self)) 'monom))
179 (:documentation "The leading monomial of a polynomial, or NIL for zero polynomial."))
180
181(defgeneric second-leading-monomial (object)
182 (:method ((self poly))
183 (change-class (copy-instance (second-leading-term self)) 'monom))
184 (:documentation "The leading monomial of a polynomial, or NIL for zero polynomial."))
185
186(defgeneric leading-coefficient (object)
187 (:method ((self poly))
188 (term-coeff (leading-term self)))
189 (:documentation "The leading coefficient of a polynomial. It signals error for a zero polynomial."))
190
191(defgeneric second-leading-coefficient (object)
192 (:method ((self poly))
193 (term-coeff (second-leading-term self)))
194 (:documentation "The second leading coefficient of a polynomial. It
195 signals error for a polynomial with at most one term."))
196
197(defmethod universal-zerop ((self poly))
198 "Return T iff SELF is a zero polynomial."
199 (null (poly-termlist self)))
200
201(defgeneric poly-length (self)
202 (:documentation "Return the number of terms.")
203 (:method ((self poly))
204 (length (poly-termlist self))))
205
206(defgeneric scalar-multiply-by (self other)
207 (:documentation "Multiply vector SELF by a scalar OTHER.")
208 (:method ((self poly) other)
209 (mapc #'(lambda (term) (setf (term-coeff term) (multiply-by (term-coeff term) other)))
210 (poly-termlist self))
211 self))
212
213(defgeneric scalar-divide-by (self other)
214 (:documentation "Divide vector SELF by a scalar OTHER.")
215 (:method ((self poly) other)
216 (mapc #'(lambda (term) (setf (term-coeff term) (divide-by (term-coeff term) other)))
217 (poly-termlist self))
218 self))
219
220(defmethod unary-inverse :before ((self poly))
221 "Checks invertibility of a polynomial SELF. To be invertable, the
222polynomial must be an invertible, constant polynomial."
223 (with-slots (termlist)
224 self
225 (assert (and (= (length termlist) 1) (zerop (total-degree (car termlist))))
226 nil
227 "To be invertible, the polynomial must have 1 term of total degree 0.")))
228
229(defmethod unary-inverse ((self poly))
230 "Returns the unary inverse of a polynomial SELF."
231 (with-slots (termlist)
232 self
233 (setf (car termlist) (unary-inverse (car termlist)))
234 self))
235
236(defmethod multiply-by ((self poly) (other monom))
237 "Multiply a polynomial SELF by OTHER."
238 (mapc #'(lambda (term) (multiply-by term other))
239 (poly-termlist self))
240 self)
241
242(defmethod multiply-by ((self poly) (other term))
243 "Multiply a polynomial SELF by OTHER."
244 (mapc #'(lambda (term) (multiply-by term other))
245 (poly-termlist self))
246 self)
247
248(defmacro fast-add/subtract (p q order-fn add/subtract-fn uminus-fn)
249 "Return an expression which will efficiently adds/subtracts two
250polynomials, P and Q. The addition/subtraction of coefficients is
251performed by calling ADD/SUBTRACT-FN. If UMINUS-FN is supplied, it is
252used to negate the coefficients of Q which do not have a corresponding
253coefficient in P. The code implements an efficient algorithm to add
254two polynomials represented as sorted lists of terms. The code
255destroys both arguments, reusing the terms to build the result."
256 `(macrolet ((lc (x) `(term-coeff (car ,x))))
257 (do ((p ,p)
258 (q ,q)
259 r)
260 ((or (endp p) (endp q))
261 ;; NOTE: R contains the result in reverse order. Can it
262 ;; be more efficient to produce the terms in correct order?
263 (unless (endp q)
264 ;; Upon subtraction, we must change the sign of
265 ;; all coefficients in q
266 ,@(when uminus-fn
267 `((mapc #'(lambda (x) (setf x (funcall ,uminus-fn x))) q)))
268 (setf r (nreconc r q)))
269 (unless (endp p)
270 (setf r (nreconc r p)))
271 r)
272 (multiple-value-bind
273 (greater-p equal-p)
274 (funcall ,order-fn (car p) (car q))
275 (cond
276 (greater-p
277 (rotatef (cdr p) r p)
278 )
279 (equal-p
280 (let ((s (funcall ,add/subtract-fn (lc p) (lc q))))
281 (cond
282 ((universal-zerop s)
283 (setf p (cdr p))
284 )
285 (t
286 (setf (lc p) s)
287 (rotatef (cdr p) r p))))
288 (setf q (cdr q))
289 )
290 (t
291 ;;Negate the term of Q if UMINUS provided, signallig
292 ;;that we are doing subtraction
293 ,(when uminus-fn
294 `(setf (lc q) (funcall ,uminus-fn (lc q))))
295 (rotatef (cdr q) r q))))
296 ;;(format t "P:~A~%" p)
297 ;;(format t "Q:~A~%" q)
298 ;;(format t "R:~A~%" r)
299 )))
300
301(defun fast-add (p q order-fn add-fn)
302 (macrolet ((lc (x) `(term-coeff (car ,x))))
303 (do (r)
304 ((or (endp p) (endp q))
305 ;; NOTE: R contains the result in reverse order. Can it
306 ;; be more efficient to produce the terms in correct order?
307 (unless (endp q)
308 (setf r (nreconc r q)))
309 (unless (endp p)
310 (setf r (nreconc r p)))
311 r)
312 (multiple-value-bind
313 (greater-p equal-p)
314 (funcall order-fn (car p) (car q))
315 (cond
316 (greater-p
317 (rotatef (cdr p) r p)
318 )
319 (equal-p
320 (let ((s (funcall add-fn (lc p) (lc q))))
321 (cond
322 ((universal-zerop s)
323 (setf p (cdr p))
324 )
325 (t
326 (setf (lc p) s)
327 (rotatef (cdr p) r p))))
328 (setf q (cdr q))
329 )
330 (t
331 (rotatef (cdr q) r q)))))))
332
333#|
334;; NOTE: The stuff below works, but may not be worth the trouble.
335
336(defmacro def-add/subtract-method (add/subtract-method-name
337 uminus-method-name
338 &optional
339 (doc-string nil doc-string-supplied-p))
340 "This macro avoids code duplication for two similar operations: ADD-TO and SUBTRACT-FROM."
341 `(defmethod ,add/subtract-method-name ((self poly) (other poly))
342 ,@(when doc-string-supplied-p `(,doc-string))
343 ;; Ensure orders are compatible
344 (change-term-order other self)
345 (setf (poly-termlist self) (fast-add/subtract
346 (poly-termlist self) (poly-termlist other)
347 (poly-term-order self)
348 #',add/subtract-method-name
349 ,(when uminus-method-name `(function ,uminus-method-name))))
350 self))
351
352(eval-when (:load-toplevel :execute)
353
354 (def-add/subtract-method add-to nil
355 "Adds to polynomial SELF another polynomial OTHER.
356This operation destructively modifies both polynomials.
357The result is stored in SELF. This implementation does
358no consing, entirely reusing the sells of SELF and OTHER.")
359
360 (def-add/subtract-method subtract-from unary-minus
361 "Subtracts from polynomial SELF another polynomial OTHER.
362This operation destructively modifies both polynomials.
363The result is stored in SELF. This implementation does
364no consing, entirely reusing the sells of SELF and OTHER.")
365 )
366
367|#
368
369(defmethod unary-minus ((self poly))
370 "Destructively modifies the coefficients of the polynomial SELF,
371by changing their sign."
372 (mapc #'unary-minus (poly-termlist self))
373 self)
374
375(defun add-termlists (p q order-fn)
376 "Destructively adds two termlists P and Q ordered according to ORDER-FN."
377 (fast-add p q order-fn #'add-to))
378
379(defun subtract-termlists (p q order-fn)
380 "Destructively subtracts two termlists P and Q ordered according to ORDER-FN."
381 (setf q (mapc #'unary-minus q))
382 (add-termlists p q order-fn))
383
384(defmethod add-to ((self poly) (other poly) &aux (other-copy (copy-instance other)))
385 "Adds to polynomial SELF another polynomial OTHER.
386This operation destructively modifies both polynomials.
387The result is stored in SELF. This implementation does
388no consing, entirely reusing the sells of SELF and OTHER."
389 (change-term-order other-copy self)
390 (setf (poly-termlist self) (add-termlists
391 (poly-termlist self) (poly-termlist other-copy)
392 (poly-term-order self)))
393 self)
394
395
396(defmethod subtract-from ((self poly) (other poly) &aux (other-copy (copy-instance other)))
397 "Subtracts from polynomial SELF another polynomial OTHER.
398This operation destructively modifies both polynomials.
399The result is stored in SELF. This implementation does
400no consing, entirely reusing the sells of SELF and OTHER."
401 (change-term-order other-copy self)
402 (setf (poly-termlist self) (subtract-termlists
403 (poly-termlist self) (poly-termlist other-copy)
404 (poly-term-order self)))
405 self)
406
407
408(defmethod add-to ((self poly) (other term) &aux (other-copy (copy-instance other)))
409 "Adds to a polynomial SELF a term OTHER. The term OTHER is not
410modified."
411 (add-to self (change-class other-copy 'poly)))
412
413(defmethod subtract-from ((self poly) (other term) &aux (other-copy (copy-instance other)))
414 "Subtracts from a polynomial SELF a term OTHER. The term OTHER is not
415modified."
416 (subtract-from self (change-class other-copy 'poly)))
417
418
419(defmacro multiply-term-by-termlist-dropping-zeros (term termlist
420 &optional (reverse-arg-order-P nil))
421 "Multiplies term TERM by a list of term, TERMLIST.
422Takes into accound divisors of zero in the ring, by
423deleting zero terms. Optionally, if REVERSE-ARG-ORDER-P
424is T, change the order of arguments; this may be important
425if we extend the package to non-commutative rings."
426 `(mapcan #'(lambda (other-term)
427 (let ((prod (multiply
428 ,@(cond
429 (reverse-arg-order-p
430 `(other-term ,term))
431 (t
432 `(,term other-term))))))
433 (cond
434 ((universal-zerop prod) nil)
435 (t (list prod)))))
436 ,termlist))
437
438(defun multiply-termlists (p q order-fn)
439 "A version of polynomial multiplication, operating
440directly on termlists."
441 (cond
442 ((or (endp p) (endp q))
443 ;;p or q is 0 (represented by NIL)
444 nil)
445 ;; If p= p0+p1 and q=q0+q1 then p*q=p0*q0+p0*q1+p1*q
446 ((endp (cdr p))
447 (multiply-term-by-termlist-dropping-zeros (car p) q))
448 ((endp (cdr q))
449 (multiply-term-by-termlist-dropping-zeros (car q) p t))
450 (t
451 (cons (multiply (car p) (car q))
452 (add-termlists
453 (multiply-term-by-termlist-dropping-zeros (car p) (cdr q))
454 (multiply-termlists (cdr p) q order-fn)
455 order-fn)))))
456
457(defmethod multiply-by ((self poly) (other poly) &aux (other-copy (copy-instance other)))
458 (change-term-order other-copy self)
459 (setf (poly-termlist self) (multiply-termlists (poly-termlist self)
460 (poly-termlist other-copy)
461 (poly-term-order self)))
462 self)
463
464(defmethod left-tensor-product-by ((self poly) (other monom))
465 (setf (poly-termlist self)
466 (mapcan #'(lambda (term)
467 (let ((prod (left-tensor-product-by term other)))
468 (cond
469 ((universal-zerop prod) nil)
470 (t (list prod)))))
471 (poly-termlist self)))
472 (incf (poly-dimension self) (monom-dimension other))
473 self)
474
475(defmethod right-tensor-product-by ((self poly) (other monom))
476 (setf (poly-termlist self)
477 (mapcan #'(lambda (term)
478 (let ((prod (right-tensor-product-by term other)))
479 (cond
480 ((universal-zerop prod) nil)
481 (t (list prod)))))
482 (poly-termlist self)))
483 (incf (poly-dimension self) (monom-dimension other))
484 self)
485
486
487(defun standard-extension (plist &aux (k (length plist)) (i 0))
488 "Calculate [U1*P1,U2*P2,...,UK*PK], where PLIST=[P1,P2,...,PK]
489is a list of polynomials. Destructively modifies PLIST elements."
490 (mapc #'(lambda (poly)
491 (left-tensor-product-by
492 poly
493 (prog1
494 (make-monom-variable k i)
495 (incf i))))
496 plist))
497
498(defun standard-extension-1 (plist
499 &aux
500 (plist (standard-extension plist))
501 (nvars (poly-dimension (car plist))))
502 "Calculate [U1*P1-1,U2*P2-1,...,UK*PK-1], where PLIST=[P1,P2,...,PK].
503Firstly, new K variables U1, U2, ..., UK, are inserted into each
504polynomial. Subsequently, P1, P2, ..., PK are destructively modified
505tantamount to replacing PI with UI*PI-1. It assumes that all
506polynomials have the same dimension, and only the first polynomial
507is examined to determine this dimension."
508 ;; Implementation note: we use STANDARD-EXTENSION and then subtract
509 ;; 1 from each polynomial; since UI*PI has no constant term,
510 ;; we just need to append the constant term at the end
511 ;; of each termlist.
512 (flet ((subtract-1 (p)
513 (poly-append-term p (make-instance 'term :dimension nvars :coeff -1))))
514 (setf plist (mapc #'subtract-1 plist)))
515 plist)
516
517
518(defun standard-sum (plist
519 &aux
520 (plist (standard-extension plist))
521 (nvars (poly-dimension (car plist))))
522 "Calculate the polynomial U1*P1+U2*P2+...+UK*PK-1, where PLIST=[P1,P2,...,PK].
523Firstly, new K variables, U1, U2, ..., UK, are inserted into each
524polynomial. Subsequently, P1, P2, ..., PK are destructively modified
525tantamount to replacing PI with UI*PI, and the resulting polynomials
526are added. Finally, 1 is subtracted. It should be noted that the term
527order is not modified, which is equivalent to using a lexicographic
528order on the first K variables."
529 (flet ((subtract-1 (p)
530 (poly-append-term p (make-instance 'term :dimension nvars :coeff -1))))
531 (subtract-1
532 (make-instance
533 'poly
534 :termlist (apply #'nconc (mapcar #'poly-termlist plist))))))
535
536(defgeneric s-polynomial (object1 object2)
537 (:documentation "Yields the S-polynomial of OBJECT1 and OBJECT2.")
538 (:method ((f poly) (g poly))
539 (let* ((lcm (universal-lcm (leading-monomial f) (leading-monomial g)))
540 (mf (divide lcm (leading-monomial f)))
541 (mg (divide lcm (leading-monomial g))))
542 (multiple-value-bind (c cf cg)
543 (universal-ezgcd (leading-coefficient f) (leading-coefficient g))
544 (declare (ignore c))
545 (subtract
546 (multiply f (change-class mf 'term :coeff cg))
547 (multiply g (change-class mg 'term :coeff cf)))))))
548
549(defgeneric poly-content (object)
550 (:documentation "Greatest common divisor of the coefficients of the polynomial object OBJECT.")
551 (:method ((self poly))
552 (reduce #'universal-gcd
553 (mapcar #'term-coeff (rest (poly-termlist self)))
554 :initial-value (leading-coefficient self))))
555
556(defun poly-primitive-part (self)
557 "Divide polynomial SELF by gcd of its
558coefficients. Return the resulting polynomial."
559 (scalar-divide-by self (poly-content self)))
560
561(defun poly-insert-variables (self k)
562 (left-tensor-product-by self (make-instance 'monom :dimension k)))
563
564(defun saturation-extension (f plist &aux (k (length plist)))
565 "Calculate [F', U1*P1-1,U2*P2-1,...,UK*PK-1], where
566PLIST=[P1,P2,...,PK] and F' is F with variables U1,U2,...,UK inserted
567as first K variables. It destructively modifies F and PLIST."
568 (nconc (mapc #'(lambda (x) (poly-insert-variables x k)) f)
569 (standard-extension-1 plist)))
570
571(defun polysaturation-extension (f plist &aux (k (length plist)))
572 "Calculate [F', U1*P1+U2*P2+...+UK*PK-1], where PLIST=[P1,P2,...,PK]
573and F' is F with variables U1,U2,...,UK inserted as first K
574variables. It destructively modifies F and PLIST."
575 (nconc (mapc #'(lambda (x) (poly-insert-variables x k)) f)
576 (list (standard-sum plist))))
577
578(defun saturation-extension-1 (f p)
579 "Given family of polynomials F and a polynomial P, calculate [F',
580U*P-1], where F' is F with variable inserted as the first variable. It
581destructively modifies F and P."
582 (polysaturation-extension f (list p)))
583
584(defmethod multiply-by ((self poly) (other ring))
585 (scalar-multiply-by self other))
586
587(defun make-poly-variable (nvars pos &optional (power 1))
588 (change-class (make-monom-variable nvars pos power) 'poly))
589
590(defun make-poly-constant (nvars coeff)
591 (change-class (make-term-constant nvars coeff) 'poly))
592
593(defgeneric universal-expt (x y)
594 (:documentation "Raises X to power Y.")
595 (:method ((x number) (y integer)) (expt x y))
596 (:method ((x t) (y integer))
597 (declare (type fixnum y))
598 (cond
599 ((minusp y) (error "universal-expt: Negative exponent."))
600 ((universal-zerop x) (if (zerop y) 1))
601 (t
602 (do ((k 1 (ash k 1))
603 (q x (multiply q q)) ;keep squaring
604 (p (make-unit-for x) (if (not (zerop (logand k y))) (multiply p q) p)))
605 ((> k y) p)
606 (declare (fixnum k)))))))
607
608(defgeneric poly-p (object)
609 (:documentation "Checks if an object is a polynomial.")
610 (:method ((self poly)) t)
611 (:method ((self t)) nil))
612
613(defmethod ->sexp :before ((self poly) &optional vars)
614 "Ensures that the number of variables in VARS maches the polynomial dimension of the
615polynomial SELF."
616 (with-slots (dimension)
617 self
618 (assert (= (length vars) dimension)
619 nil
620 "Number of variables ~S does not match the dimension ~S"
621 vars dimension)))
622
623(defmethod ->sexp ((self poly) &optional vars)
624 "Converts a polynomial SELF to a sexp."
625 (let ((m (mapcar #'(lambda (trm) (->sexp trm vars))
626 (poly-termlist self))))
627 (cond ((endp m) 0)
628 ((endp (cdr m)) (car m))
629 (t (cons '+ m)))))
630
631(defconstant +list-marker+ :[
632 "A sexp with this head is considered a list of polynomials.")
633
634(defmethod ->sexp ((self cons) &optional vars)
635 (assert (eql (car self) +list-marker+))
636 (cons +list-marker+ (mapcar #'(lambda (p) (->sexp p vars)) (cdr self))))
637
638(defmethod make-zero-for ((self poly))
639 (make-instance 'poly :dimension (poly-dimension self)))
640
641(defmethod make-unit-for ((self poly))
642 (make-poly-constant (poly-dimension self) 1))
643
644(defgeneric poly-reverse (self)
645 (:documentation "Reverse the order of terms in a polynomial SELF.")
646 (:method ((self poly))
647 (with-slots (termlist)
648 self
649 (setf termlist (nreverse termlist)))
650 self))
651
652
653
Note: See TracBrowser for help on using the repository browser.