[1201] | 1 | ;;; -*- Mode: Lisp -*-
|
---|
[77] | 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 |
|
---|
[431] | 22 | (defpackage "POLYNOMIAL"
|
---|
[2462] | 23 | (:use :cl :ring :monom :order :term #| :infix |# )
|
---|
[2522] | 24 | (:export "POLY")
|
---|
| 25 | (:documentation "Implements polynomials"))
|
---|
[143] | 26 |
|
---|
[431] | 27 | (in-package :polynomial)
|
---|
| 28 |
|
---|
[1927] | 29 | (proclaim '(optimize (speed 3) (space 0) (safety 0) (debug 0)))
|
---|
[52] | 30 |
|
---|
[2442] | 31 | #|
|
---|
[52] | 32 | ;;
|
---|
| 33 | ;; BOA constructor, by default constructs zero polynomial
|
---|
| 34 | (:constructor make-poly-from-termlist (termlist &optional (sugar (termlist-sugar termlist))))
|
---|
| 35 | (:constructor make-poly-zero (&aux (termlist nil) (sugar -1)))
|
---|
| 36 | ;; Constructor of polynomials representing a variable
|
---|
[1657] | 37 | (:constructor make-poly-variable (ring nvars pos &optional (power 1)
|
---|
[53] | 38 | &aux
|
---|
| 39 | (termlist (list
|
---|
| 40 | (make-term-variable ring nvars pos power)))
|
---|
| 41 | (sugar power)))
|
---|
| 42 | (:constructor poly-unit (ring dimension
|
---|
| 43 | &aux
|
---|
| 44 | (termlist (termlist-unit ring dimension))
|
---|
| 45 | (sugar 0))))
|
---|
[52] | 46 |
|
---|
[2442] | 47 | |#
|
---|
| 48 |
|
---|
| 49 | (defclass poly ()
|
---|
[2470] | 50 | ((termlist :initarg :termlist :accessor poly-termlist))
|
---|
[2442] | 51 | (:default-initargs :termlist nil))
|
---|
| 52 |
|
---|
[2471] | 53 | (defmethod print-object ((self poly) stream)
|
---|
| 54 | (format stream "#<POLY TERMLIST=~A >" (poly-termlist self)))
|
---|
[2469] | 55 |
|
---|
[2513] | 56 | (defmethod insert-item ((self poly) (item term))
|
---|
| 57 | (push item (poly-termlist self))
|
---|
[2514] | 58 | self)
|
---|
[2464] | 59 |
|
---|
[2513] | 60 | (defmethod append-item ((self poly) (item term))
|
---|
| 61 | (setf (cdr (last (poly-termlist self))) (list item))
|
---|
| 62 | self)
|
---|
[2466] | 63 |
|
---|
[52] | 64 | ;; Leading term
|
---|
[2442] | 65 | (defgeneric leading-term (object)
|
---|
| 66 | (:method ((self poly))
|
---|
[2525] | 67 | (car (poly-termlist self)))
|
---|
| 68 | (:documentation "The leading term of a polynomial, or NIL for zero polynomial."))
|
---|
[52] | 69 |
|
---|
| 70 | ;; Second term
|
---|
[2442] | 71 | (defgeneric second-leading-term (object)
|
---|
| 72 | (:method ((self poly))
|
---|
[2525] | 73 | (cadar (poly-termlist self)))
|
---|
| 74 | (:documentation "The second leading term of a polynomial, or NIL for a polynomial with at most one term."))
|
---|
[52] | 75 |
|
---|
| 76 | ;; Leading coefficient
|
---|
[2442] | 77 | (defgeneric leading-coefficient (object)
|
---|
| 78 | (:method ((self poly))
|
---|
[2526] | 79 | (r-coeff (leading-term self)))
|
---|
[2527] | 80 | (:documentation "The leading coefficient of a polynomial. It signals
|
---|
| 81 | error for a zero polynomial.")
|
---|
[52] | 82 |
|
---|
| 83 | ;; Second coefficient
|
---|
[2442] | 84 | (defgeneric second-leading-coefficient (object)
|
---|
| 85 | (:method ((self poly))
|
---|
[2526] | 86 | (r-coeff (second-leading-term self)))
|
---|
[2527] | 87 | (:documentation "The second leading coefficient of a polynomial. It
|
---|
| 88 | signals error for a polynomial with at most one term."))
|
---|
[52] | 89 |
|
---|
| 90 | ;; Testing for a zero polynomial
|
---|
[2445] | 91 | (defmethod r-zerop ((self poly))
|
---|
| 92 | (null (poly-termlist self)))
|
---|
[52] | 93 |
|
---|
| 94 | ;; The number of terms
|
---|
[2445] | 95 | (defmethod r-length ((self poly))
|
---|
| 96 | (length (poly-termlist self)))
|
---|
[52] | 97 |
|
---|
[2483] | 98 | (defmethod multiply-by ((self poly) (other monom))
|
---|
[2501] | 99 | (mapc #'(lambda (term) (multiply-by term other))
|
---|
| 100 | (poly-termlist self))
|
---|
[2483] | 101 | self)
|
---|
[2469] | 102 |
|
---|
[2501] | 103 | (defmethod multiply-by ((self poly) (other scalar))
|
---|
[2502] | 104 | (mapc #'(lambda (term) (multiply-by term other))
|
---|
[2501] | 105 | (poly-termlist self))
|
---|
[2487] | 106 | self)
|
---|
| 107 |
|
---|
[2530] | 108 | (defmethod add-to ((self poly) (other poly))
|
---|
| 109 | (macrolet ((lt (termlist) `(car ,termlist))
|
---|
| 110 | (lc (termlist) `(term-coeff (lt ,termlist))))
|
---|
| 111 | (with-slots ((p termlist) order)
|
---|
[2528] | 112 | self
|
---|
[2531] | 113 | (with-slots ((q termlist))
|
---|
[2528] | 114 | other
|
---|
| 115 | (do (r)
|
---|
| 116 | ((cond
|
---|
| 117 | ((endp p)
|
---|
| 118 | (setf r (revappend r q)) t)
|
---|
| 119 | ((endp q)
|
---|
| 120 | (setf r (revappend r p)) t)
|
---|
| 121 | (t
|
---|
| 122 | (multiple-value-bind
|
---|
| 123 | (lm-greater lm-equal)
|
---|
[2530] | 124 | (funcall order (car p) (car q))
|
---|
[2528] | 125 | (cond
|
---|
| 126 | (lm-equal
|
---|
[2530] | 127 | (let ((s (r+ (lc p) (lc q))))
|
---|
[2531] | 128 | (unless (r-zerop
|
---|
[2528] | 129 | (lm-greater
|
---|
| 130 | (setf r (cons (car p) r)
|
---|
| 131 | p (cdr p)))
|
---|
| 132 | (t (setf r (cons (car q) r)
|
---|
| 133 | q (cdr q)))))
|
---|
| 134 | nil))
|
---|
[2531] | 135 | r)))))))))
|
---|
[2528] | 136 | self)
|
---|
[2487] | 137 |
|
---|
[2500] | 138 | (defmethod subtract-from ((self poly) (other poly)))
|
---|
[53] | 139 |
|
---|
[2500] | 140 | (defmethod unary-uminus ((self poly)))
|
---|
[52] | 141 |
|
---|
[2486] | 142 | #|
|
---|
| 143 |
|
---|
[52] | 144 | (defun poly-standard-extension (plist &aux (k (length plist)))
|
---|
| 145 | "Calculate [U1*P1,U2*P2,...,UK*PK], where PLIST=[P1,P2,...,PK]."
|
---|
| 146 | (declare (list plist) (fixnum k))
|
---|
| 147 | (labels ((incf-power (g i)
|
---|
| 148 | (dolist (x (poly-termlist g))
|
---|
| 149 | (incf (monom-elt (term-monom x) i)))
|
---|
| 150 | (incf (poly-sugar g))))
|
---|
| 151 | (setf plist (poly-list-add-variables plist k))
|
---|
| 152 | (dotimes (i k plist)
|
---|
| 153 | (incf-power (nth i plist) i))))
|
---|
| 154 |
|
---|
[1473] | 155 | (defun saturation-extension (ring f plist
|
---|
| 156 | &aux
|
---|
| 157 | (k (length plist))
|
---|
[1474] | 158 | (d (monom-dimension (poly-lm (car plist))))
|
---|
| 159 | f-x plist-x)
|
---|
[52] | 160 | "Calculate [F, U1*P1-1,U2*P2-1,...,UK*PK-1], where PLIST=[P1,P2,...,PK]."
|
---|
[1907] | 161 | (declare (type ring ring))
|
---|
[1474] | 162 | (setf f-x (poly-list-add-variables f k)
|
---|
| 163 | plist-x (mapcar #'(lambda (x)
|
---|
[1843] | 164 | (setf (poly-termlist x)
|
---|
| 165 | (nconc (poly-termlist x)
|
---|
| 166 | (list (make-term :monom (make-monom :dimension d)
|
---|
[1844] | 167 | :coeff (funcall (ring-uminus ring)
|
---|
| 168 | (funcall (ring-unit ring)))))))
|
---|
[1474] | 169 | x)
|
---|
| 170 | (poly-standard-extension plist)))
|
---|
| 171 | (append f-x plist-x))
|
---|
[52] | 172 |
|
---|
| 173 |
|
---|
[1475] | 174 | (defun polysaturation-extension (ring f plist
|
---|
| 175 | &aux
|
---|
| 176 | (k (length plist))
|
---|
[1476] | 177 | (d (+ k (monom-dimension (poly-lm (car plist)))))
|
---|
[1494] | 178 | ;; Add k variables to f
|
---|
[1493] | 179 | (f (poly-list-add-variables f k))
|
---|
[1495] | 180 | ;; Set PLIST to [U1*P1,U2*P2,...,UK*PK]
|
---|
[1493] | 181 | (plist (apply #'poly-append (poly-standard-extension plist))))
|
---|
[1497] | 182 | "Calculate [F, U1*P1+U2*P2+...+UK*PK-1], where PLIST=[P1,P2,...,PK]. It destructively modifies F."
|
---|
[1493] | 183 | ;; Add -1 as the last term
|
---|
[1908] | 184 | (declare (type ring ring))
|
---|
[1493] | 185 | (setf (cdr (last (poly-termlist plist)))
|
---|
[1845] | 186 | (list (make-term :monom (make-monom :dimension d)
|
---|
| 187 | :coeff (funcall (ring-uminus ring) (funcall (ring-unit ring))))))
|
---|
[1493] | 188 | (append f (list plist)))
|
---|
[52] | 189 |
|
---|
[1477] | 190 | (defun saturation-extension-1 (ring f p)
|
---|
[1497] | 191 | "Calculate [F, U*P-1]. It destructively modifies F."
|
---|
[1908] | 192 | (declare (type ring ring))
|
---|
[1477] | 193 | (polysaturation-extension ring f (list p)))
|
---|
[53] | 194 |
|
---|
| 195 | ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
---|
| 196 | ;;
|
---|
| 197 | ;; Evaluation of polynomial (prefix) expressions
|
---|
| 198 | ;;
|
---|
| 199 | ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
|
---|
| 200 |
|
---|
| 201 | (defun coerce-coeff (ring expr vars)
|
---|
| 202 | "Coerce an element of the coefficient ring to a constant polynomial."
|
---|
| 203 | ;; Modular arithmetic handler by rat
|
---|
[1908] | 204 | (declare (type ring ring))
|
---|
[1846] | 205 | (make-poly-from-termlist (list (make-term :monom (make-monom :dimension (length vars))
|
---|
| 206 | :coeff (funcall (ring-parse ring) expr)))
|
---|
[53] | 207 | 0))
|
---|
| 208 |
|
---|
[1046] | 209 | (defun poly-eval (expr vars
|
---|
| 210 | &optional
|
---|
[1668] | 211 | (ring +ring-of-integers+)
|
---|
[1048] | 212 | (order #'lex>)
|
---|
[1170] | 213 | (list-marker :[)
|
---|
[1047] | 214 | &aux
|
---|
| 215 | (ring-and-order (make-ring-and-order :ring ring :order order)))
|
---|
[1168] | 216 | "Evaluate Lisp form EXPR to a polynomial or a list of polynomials in
|
---|
[1208] | 217 | variables VARS. Return the resulting polynomial or list of
|
---|
| 218 | polynomials. Standard arithmetical operators in form EXPR are
|
---|
| 219 | replaced with their analogues in the ring of polynomials, and the
|
---|
| 220 | resulting expression is evaluated, resulting in a polynomial or a list
|
---|
[1209] | 221 | of polynomials in internal form. A similar operation in another computer
|
---|
| 222 | algebra system could be called 'expand' or so."
|
---|
[1909] | 223 | (declare (type ring ring))
|
---|
[1050] | 224 | (labels ((p-eval (arg) (poly-eval arg vars ring order))
|
---|
[1140] | 225 | (p-eval-scalar (arg) (poly-eval-scalar arg))
|
---|
[53] | 226 | (p-eval-list (args) (mapcar #'p-eval args))
|
---|
[989] | 227 | (p-add (x y) (poly-add ring-and-order x y)))
|
---|
[53] | 228 | (cond
|
---|
[1128] | 229 | ((null expr) (error "Empty expression"))
|
---|
[53] | 230 | ((eql expr 0) (make-poly-zero))
|
---|
| 231 | ((member expr vars :test #'equalp)
|
---|
| 232 | (let ((pos (position expr vars :test #'equalp)))
|
---|
[1657] | 233 | (make-poly-variable ring (length vars) pos)))
|
---|
[53] | 234 | ((atom expr)
|
---|
| 235 | (coerce-coeff ring expr vars))
|
---|
| 236 | ((eq (car expr) list-marker)
|
---|
| 237 | (cons list-marker (p-eval-list (cdr expr))))
|
---|
| 238 | (t
|
---|
| 239 | (case (car expr)
|
---|
| 240 | (+ (reduce #'p-add (p-eval-list (cdr expr))))
|
---|
| 241 | (- (case (length expr)
|
---|
| 242 | (1 (make-poly-zero))
|
---|
| 243 | (2 (poly-uminus ring (p-eval (cadr expr))))
|
---|
[989] | 244 | (3 (poly-sub ring-and-order (p-eval (cadr expr)) (p-eval (caddr expr))))
|
---|
| 245 | (otherwise (poly-sub ring-and-order (p-eval (cadr expr))
|
---|
[53] | 246 | (reduce #'p-add (p-eval-list (cddr expr)))))))
|
---|
| 247 | (*
|
---|
| 248 | (if (endp (cddr expr)) ;unary
|
---|
| 249 | (p-eval (cdr expr))
|
---|
[989] | 250 | (reduce #'(lambda (p q) (poly-mul ring-and-order p q)) (p-eval-list (cdr expr)))))
|
---|
[1106] | 251 | (/
|
---|
| 252 | ;; A polynomial can be divided by a scalar
|
---|
[1115] | 253 | (cond
|
---|
| 254 | ((endp (cddr expr))
|
---|
[1117] | 255 | ;; A special case (/ ?), the inverse
|
---|
[1119] | 256 | (coerce-coeff ring (apply (ring-div ring) (cdr expr)) vars))
|
---|
[1128] | 257 | (t
|
---|
[1115] | 258 | (let ((num (p-eval (cadr expr)))
|
---|
[1142] | 259 | (denom-inverse (apply (ring-div ring)
|
---|
| 260 | (cons (funcall (ring-unit ring))
|
---|
| 261 | (mapcar #'p-eval-scalar (cddr expr))))))
|
---|
[1118] | 262 | (scalar-times-poly ring denom-inverse num)))))
|
---|
[53] | 263 | (expt
|
---|
| 264 | (cond
|
---|
| 265 | ((member (cadr expr) vars :test #'equalp)
|
---|
| 266 | ;;Special handling of (expt var pow)
|
---|
| 267 | (let ((pos (position (cadr expr) vars :test #'equalp)))
|
---|
[1657] | 268 | (make-poly-variable ring (length vars) pos (caddr expr))))
|
---|
[53] | 269 | ((not (and (integerp (caddr expr)) (plusp (caddr expr))))
|
---|
| 270 | ;; Negative power means division in coefficient ring
|
---|
| 271 | ;; Non-integer power means non-polynomial coefficient
|
---|
| 272 | (coerce-coeff ring expr vars))
|
---|
[989] | 273 | (t (poly-expt ring-and-order (p-eval (cadr expr)) (caddr expr)))))
|
---|
[53] | 274 | (otherwise
|
---|
| 275 | (coerce-coeff ring expr vars)))))))
|
---|
| 276 |
|
---|
[1133] | 277 | (defun poly-eval-scalar (expr
|
---|
| 278 | &optional
|
---|
[1668] | 279 | (ring +ring-of-integers+)
|
---|
[1133] | 280 | &aux
|
---|
| 281 | (order #'lex>))
|
---|
| 282 | "Evaluate a scalar expression EXPR in ring RING."
|
---|
[1910] | 283 | (declare (type ring ring))
|
---|
[1133] | 284 | (poly-lc (poly-eval expr nil ring order)))
|
---|
| 285 |
|
---|
[1189] | 286 | (defun spoly (ring-and-order f g
|
---|
| 287 | &aux
|
---|
| 288 | (ring (ro-ring ring-and-order)))
|
---|
[55] | 289 | "It yields the S-polynomial of polynomials F and G."
|
---|
[1911] | 290 | (declare (type ring-and-order ring-and-order) (type poly f g))
|
---|
[55] | 291 | (let* ((lcm (monom-lcm (poly-lm f) (poly-lm g)))
|
---|
| 292 | (mf (monom-div lcm (poly-lm f)))
|
---|
| 293 | (mg (monom-div lcm (poly-lm g))))
|
---|
| 294 | (declare (type monom mf mg))
|
---|
| 295 | (multiple-value-bind (c cf cg)
|
---|
| 296 | (funcall (ring-ezgcd ring) (poly-lc f) (poly-lc g))
|
---|
| 297 | (declare (ignore c))
|
---|
| 298 | (poly-sub
|
---|
[1189] | 299 | ring-and-order
|
---|
[55] | 300 | (scalar-times-poly ring cg (monom-times-poly mf f))
|
---|
| 301 | (scalar-times-poly ring cf (monom-times-poly mg g))))))
|
---|
[53] | 302 |
|
---|
| 303 |
|
---|
[55] | 304 | (defun poly-primitive-part (ring p)
|
---|
| 305 | "Divide polynomial P with integer coefficients by gcd of its
|
---|
| 306 | coefficients and return the result."
|
---|
[1912] | 307 | (declare (type ring ring) (type poly p))
|
---|
[55] | 308 | (if (poly-zerop p)
|
---|
| 309 | (values p 1)
|
---|
| 310 | (let ((c (poly-content ring p)))
|
---|
[1203] | 311 | (values (make-poly-from-termlist
|
---|
| 312 | (mapcar
|
---|
| 313 | #'(lambda (x)
|
---|
[1847] | 314 | (make-term :monom (term-monom x)
|
---|
| 315 | :coeff (funcall (ring-div ring) (term-coeff x) c)))
|
---|
[1203] | 316 | (poly-termlist p))
|
---|
| 317 | (poly-sugar p))
|
---|
| 318 | c))))
|
---|
[55] | 319 |
|
---|
| 320 | (defun poly-content (ring p)
|
---|
| 321 | "Greatest common divisor of the coefficients of the polynomial P. Use the RING structure
|
---|
| 322 | to compute the greatest common divisor."
|
---|
[1913] | 323 | (declare (type ring ring) (type poly p))
|
---|
[55] | 324 | (reduce (ring-gcd ring) (mapcar #'term-coeff (rest (poly-termlist p))) :initial-value (poly-lc p)))
|
---|
[1066] | 325 |
|
---|
[1091] | 326 | (defun read-infix-form (&key (stream t))
|
---|
[1066] | 327 | "Parser of infix expressions with integer/rational coefficients
|
---|
| 328 | The parser will recognize two kinds of polynomial expressions:
|
---|
| 329 |
|
---|
| 330 | - polynomials in fully expanded forms with coefficients
|
---|
| 331 | written in front of symbolic expressions; constants can be optionally
|
---|
| 332 | enclosed in (); for example, the infix form
|
---|
| 333 | X^2-Y^2+(-4/3)*U^2*W^3-5
|
---|
| 334 | parses to
|
---|
| 335 | (+ (- (EXPT X 2) (EXPT Y 2)) (* (- (/ 4 3)) (EXPT U 2) (EXPT W 3)) (- 5))
|
---|
| 336 |
|
---|
| 337 | - lists of polynomials; for example
|
---|
| 338 | [X-Y, X^2+3*Z]
|
---|
| 339 | parses to
|
---|
| 340 | (:[ (- X Y) (+ (EXPT X 2) (* 3 Z)))
|
---|
| 341 | where the first symbol [ marks a list of polynomials.
|
---|
| 342 |
|
---|
| 343 | -other infix expressions, for example
|
---|
| 344 | [(X-Y)*(X+Y)/Z,(X+1)^2]
|
---|
| 345 | parses to:
|
---|
| 346 | (:[ (/ (* (- X Y) (+ X Y)) Z) (EXPT (+ X 1) 2))
|
---|
| 347 | Currently this function is implemented using M. Kantrowitz's INFIX package."
|
---|
| 348 | (read-from-string
|
---|
| 349 | (concatenate 'string
|
---|
| 350 | "#I("
|
---|
| 351 | (with-output-to-string (s)
|
---|
| 352 | (loop
|
---|
| 353 | (multiple-value-bind (line eof)
|
---|
| 354 | (read-line stream t)
|
---|
| 355 | (format s "~A" line)
|
---|
| 356 | (when eof (return)))))
|
---|
| 357 | ")")))
|
---|
| 358 |
|
---|
[1145] | 359 | (defun read-poly (vars &key
|
---|
| 360 | (stream t)
|
---|
[1668] | 361 | (ring +ring-of-integers+)
|
---|
[1145] | 362 | (order #'lex>))
|
---|
[1067] | 363 | "Reads an expression in prefix form from a stream STREAM.
|
---|
[1144] | 364 | The expression read from the strem should represent a polynomial or a
|
---|
| 365 | list of polynomials in variables VARS, over the ring RING. The
|
---|
| 366 | polynomial or list of polynomials is returned, with terms in each
|
---|
| 367 | polynomial ordered according to monomial order ORDER."
|
---|
[1146] | 368 | (poly-eval (read-infix-form :stream stream) vars ring order))
|
---|
[1092] | 369 |
|
---|
[1146] | 370 | (defun string->poly (str vars
|
---|
[1164] | 371 | &optional
|
---|
[1668] | 372 | (ring +ring-of-integers+)
|
---|
[1146] | 373 | (order #'lex>))
|
---|
| 374 | "Converts a string STR to a polynomial in variables VARS."
|
---|
[1097] | 375 | (with-input-from-string (s str)
|
---|
[1165] | 376 | (read-poly vars :stream s :ring ring :order order)))
|
---|
[1095] | 377 |
|
---|
[1143] | 378 | (defun poly->alist (p)
|
---|
| 379 | "Convert a polynomial P to an association list. Thus, the format of the
|
---|
| 380 | returned value is ((MONOM[0] . COEFF[0]) (MONOM[1] . COEFF[1]) ...), where
|
---|
| 381 | MONOM[I] is a list of exponents in the monomial and COEFF[I] is the
|
---|
| 382 | corresponding coefficient in the ring."
|
---|
[1171] | 383 | (cond
|
---|
| 384 | ((poly-p p)
|
---|
| 385 | (mapcar #'term->cons (poly-termlist p)))
|
---|
| 386 | ((and (consp p) (eq (car p) :[))
|
---|
[1172] | 387 | (cons :[ (mapcar #'poly->alist (cdr p))))))
|
---|
[1143] | 388 |
|
---|
[1164] | 389 | (defun string->alist (str vars
|
---|
| 390 | &optional
|
---|
[1668] | 391 | (ring +ring-of-integers+)
|
---|
[1164] | 392 | (order #'lex>))
|
---|
[1143] | 393 | "Convert a string STR representing a polynomial or polynomial list to
|
---|
[1158] | 394 | an association list (... (MONOM . COEFF) ...)."
|
---|
[1166] | 395 | (poly->alist (string->poly str vars ring order)))
|
---|
[1440] | 396 |
|
---|
| 397 | (defun poly-equal-no-sugar-p (p q)
|
---|
| 398 | "Compare polynomials for equality, ignoring sugar."
|
---|
[1914] | 399 | (declare (type poly p q))
|
---|
[1440] | 400 | (equalp (poly-termlist p) (poly-termlist q)))
|
---|
[1559] | 401 |
|
---|
| 402 | (defun poly-set-equal-no-sugar-p (p q)
|
---|
| 403 | "Compare polynomial sets P and Q for equality, ignoring sugar."
|
---|
| 404 | (null (set-exclusive-or p q :test #'poly-equal-no-sugar-p )))
|
---|
[1560] | 405 |
|
---|
| 406 | (defun poly-list-equal-no-sugar-p (p q)
|
---|
| 407 | "Compare polynomial lists P and Q for equality, ignoring sugar."
|
---|
| 408 | (every #'poly-equal-no-sugar-p p q))
|
---|
[2456] | 409 | |#
|
---|