diff options
| author | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
|---|---|---|
| committer | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
| commit | ab8cc85adde879fb963c94d15675783f2cf4b183 (patch) | |
| tree | c202482327f474583b750b2c45dedfc4e4312b1d /src/algebra/polycat.spad.pamphlet | |
| download | open-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz | |
Initial population.
Diffstat (limited to 'src/algebra/polycat.spad.pamphlet')
| -rw-r--r-- | src/algebra/polycat.spad.pamphlet | 4785 |
1 files changed, 4785 insertions, 0 deletions
diff --git a/src/algebra/polycat.spad.pamphlet b/src/algebra/polycat.spad.pamphlet new file mode 100644 index 00000000..01cbbccc --- /dev/null +++ b/src/algebra/polycat.spad.pamphlet @@ -0,0 +1,4785 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra polycat.spad} +\author{Manuel Bronstein} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{category AMR AbelianMonoidRing} +<<category AMR AbelianMonoidRing>>= +)abbrev category AMR AbelianMonoidRing +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ Abelian monoid ring elements (not necessarily of finite support) +++ of this ring are of the form formal SUM (r_i * e_i) +++ where the r_i are coefficents and the e_i, elements of the +++ ordered abelian monoid, are thought of as exponents or monomials. +++ The monomials commute with each other, and with +++ the coefficients (which themselves may or may not be commutative). +++ See \spadtype{FiniteAbelianMonoidRing} for the case of finite support +++ a useful common model for polynomials and power series. +++ Conceptually at least, only the non-zero terms are ever operated on. + +AbelianMonoidRing(R:Ring, E:OrderedAbelianMonoid): Category == + Join(Ring,BiModule(R,R)) with + leadingCoefficient: % -> R + ++ leadingCoefficient(p) returns the coefficient highest degree term of p. + leadingMonomial: % -> % + ++ leadingMonomial(p) returns the monomial of p with the highest degree. + degree: % -> E + ++ degree(p) returns the maximum of the exponents of the terms of p. + map: (R -> R, %) -> % + ++ map(fn,u) maps function fn onto the coefficients + ++ of the non-zero monomials of u. + monomial?: % -> Boolean + ++ monomial?(p) tests if p is a single monomial. + monomial: (R,E) -> % + ++ monomial(r,e) makes a term from a coefficient r and an exponent e. + reductum: % -> % + ++ reductum(u) returns u minus its leading monomial + ++ returns zero if handed the zero element. + coefficient: (%,E) -> R + ++ coefficient(p,e) extracts the coefficient of the monomial with + ++ exponent e from polynomial p, or returns zero if exponent is not present. + if R has Field then "/": (%,R) -> % + ++ p/c divides p by the coefficient c. + if R has CommutativeRing then + CommutativeRing + Algebra R + if R has CharacteristicZero then CharacteristicZero + if R has CharacteristicNonZero then CharacteristicNonZero + if R has IntegralDomain then IntegralDomain + if R has Algebra Fraction Integer then Algebra Fraction Integer + add + monomial? x == zero? reductum x + + map(fn:R -> R, x: %) == + -- this default definition assumes that reductum is cheap + zero? x => 0 + r:=fn leadingCoefficient x + zero? r => map(fn,reductum x) + monomial(r, degree x) + map(fn,reductum x) + + if R has Algebra Fraction Integer then + q:Fraction(Integer) * p:% == map(q * #1, p) + +@ +\section{category FAMR FiniteAbelianMonoidRing} +<<category FAMR FiniteAbelianMonoidRing>>= +)abbrev category FAMR FiniteAbelianMonoidRing +++ Author: +++ Date Created: +++ Date Last Updated: 14.08.2000 Exported pomopo! and binomThmExpt [MMM] +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: This category is +++ similar to AbelianMonoidRing, except that the sum is assumed to be finite. +++ It is a useful model for polynomials, +++ but is somewhat more general. + +FiniteAbelianMonoidRing(R:Ring, E:OrderedAbelianMonoid): Category == + Join(AbelianMonoidRing(R,E),FullyRetractableTo R) with + ground?: % -> Boolean + ++ ground?(p) tests if polynomial p is a member of the coefficient ring. + -- can't be defined earlier, since a power series + -- might not know if there were other terms or not + ground: % -> R + ++ ground(p) retracts polynomial p to the coefficient ring. + coefficients: % -> List R + ++ coefficients(p) gives the list of non-zero coefficients of polynomial p. + numberOfMonomials: % -> NonNegativeInteger + ++ numberOfMonomials(p) gives the number of non-zero monomials in polynomial p. + minimumDegree: % -> E + ++ minimumDegree(p) gives the least exponent of a non-zero term of polynomial p. + ++ Error: if applied to 0. + mapExponents: (E -> E, %) -> % + ++ mapExponents(fn,u) maps function fn onto the exponents + ++ of the non-zero monomials of polynomial u. + pomopo!: (%,R,E,%) -> % + ++ \spad{pomopo!(p1,r,e,p2)} returns \spad{p1 + monomial(e,r) * p2} + ++ and may use \spad{p1} as workspace. The constaant \spad{r} is + ++ assumed to be nonzero. + if R has CommutativeRing then + binomThmExpt: (%,%,NonNegativeInteger) -> % + ++ \spad{binomThmExpt(p,q,n)} returns \spad{(x+y)^n} + ++ by means of the binomial theorem trick. + if R has IntegralDomain then + "exquo": (%,R) -> Union(%,"failed") + ++ exquo(p,r) returns the exact quotient of polynomial p by r, or "failed" + ++ if none exists. + if R has GcdDomain then + content: % -> R + ++ content(p) gives the gcd of the coefficients of polynomial p. + primitivePart: % -> % + ++ primitivePart(p) returns the unit normalized form of polynomial p + ++ divided by the content of p. + add + pomopo!(p1,r,e,p2) == p1 + r * mapExponents(#1+e,p2) + + if R has CommutativeRing then + binomThmExpt(x,y,nn) == + nn = 0 => 1$% + ans,xn,yn: % + bincoef: Integer + powl: List(%):= [x] + for i in 2..nn repeat powl:=[x * powl.first, :powl] + yn:=y; ans:=powl.first; i:=1; bincoef:=nn + for xn in powl.rest repeat + ans:= bincoef * xn * yn + ans + bincoef:= (nn-i) * bincoef quo (i+1); i:= i+1 + -- last I and BINCOEF unused + yn:= y * yn + ans + yn + ground? x == + retractIfCan(x)@Union(R,"failed") case "failed" => false + true + ground x == retract(x)@R + mapExponents (fn:E -> E, x: %) == + -- this default definition assumes that reductum is cheap + zero? x => 0 + monomial(leadingCoefficient x,fn degree x)+mapExponents(fn,reductum x) + coefficients x == + zero? x => empty() + concat(leadingCoefficient x, coefficients reductum x) + + if R has Field then + x/r == map(#1/r,x) + if R has IntegralDomain then + x exquo r == + -- probably not a very good definition in most special cases + zero? x => 0 + ans:% :=0 + t:=leadingCoefficient x exquo r + while not (t case "failed") and not zero? x repeat + ans:=ans+monomial(t::R,degree x) + x:=reductum x + if not zero? x then t:=leadingCoefficient x exquo r + t case "failed" => "failed" + ans + if R has GcdDomain then + content x == -- this assumes reductum is cheap + zero? x => 0 + r:=leadingCoefficient x + x:=reductum x +-- while not zero? x and not one? r repeat + while not zero? x and not (r = 1) repeat + r:=gcd(r,leadingCoefficient x) + x:=reductum x + r + primitivePart x == + zero? x => x + c := content x + unitCanonical((x exquo c)::%) + +@ +\section{category POLYCAT PolynomialCategory} +<<category POLYCAT PolynomialCategory>>= +)abbrev category POLYCAT PolynomialCategory +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: Ring, monomial, coefficient, differentiate, eval +++ Related Constructors: Polynomial, DistributedMultivariatePolynomial +++ Also See: UnivariatePolynomialCategory +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The category for general multi-variate polynomials over a ring +++ R, in variables from VarSet, with exponents from the +++ \spadtype{OrderedAbelianMonoidSup}. + +PolynomialCategory(R:Ring, E:OrderedAbelianMonoidSup, VarSet:OrderedSet): + Category == + Join(PartialDifferentialRing VarSet, FiniteAbelianMonoidRing(R, E), + Evalable %, InnerEvalable(VarSet, R), + InnerEvalable(VarSet, %), RetractableTo VarSet, + FullyLinearlyExplicitRingOver R) with + -- operations + degree : (%,VarSet) -> NonNegativeInteger + ++ degree(p,v) gives the degree of polynomial p with respect to the variable v. + degree : (%,List(VarSet)) -> List(NonNegativeInteger) + ++ degree(p,lv) gives the list of degrees of polynomial p + ++ with respect to each of the variables in the list lv. + coefficient: (%,VarSet,NonNegativeInteger) -> % + ++ coefficient(p,v,n) views the polynomial p as a univariate + ++ polynomial in v and returns the coefficient of the \spad{v**n} term. + coefficient: (%,List VarSet,List NonNegativeInteger) -> % + ++ coefficient(p, lv, ln) views the polynomial p as a polynomial + ++ in the variables of lv and returns the coefficient of the term + ++ \spad{lv**ln}, i.e. \spad{prod(lv_i ** ln_i)}. + monomials: % -> List % + ++ monomials(p) returns the list of non-zero monomials of polynomial p, i.e. + ++ \spad{monomials(sum(a_(i) X^(i))) = [a_(1) X^(1),...,a_(n) X^(n)]}. + univariate : (%,VarSet) -> SparseUnivariatePolynomial(%) + ++ univariate(p,v) converts the multivariate polynomial p + ++ into a univariate polynomial in v, whose coefficients are still + ++ multivariate polynomials (in all the other variables). + univariate : % -> SparseUnivariatePolynomial(R) + ++ univariate(p) converts the multivariate polynomial p, + ++ which should actually involve only one variable, + ++ into a univariate polynomial + ++ in that variable, whose coefficients are in the ground ring. + ++ Error: if polynomial is genuinely multivariate + mainVariable : % -> Union(VarSet,"failed") + ++ mainVariable(p) returns the biggest variable which actually + ++ occurs in the polynomial p, or "failed" if no variables are + ++ present. + ++ fails precisely if polynomial satisfies ground? + minimumDegree : (%,VarSet) -> NonNegativeInteger + ++ minimumDegree(p,v) gives the minimum degree of polynomial p + ++ with respect to v, i.e. viewed a univariate polynomial in v + minimumDegree : (%,List(VarSet)) -> List(NonNegativeInteger) + ++ minimumDegree(p, lv) gives the list of minimum degrees of the + ++ polynomial p with respect to each of the variables in the list lv + monicDivide : (%,%,VarSet) -> Record(quotient:%,remainder:%) + ++ monicDivide(a,b,v) divides the polynomial a by the polynomial b, + ++ with each viewed as a univariate polynomial in v returning + ++ both the quotient and remainder. + ++ Error: if b is not monic with respect to v. + monomial : (%,VarSet,NonNegativeInteger) -> % + ++ monomial(a,x,n) creates the monomial \spad{a*x**n} where \spad{a} is + ++ a polynomial, x is a variable and n is a nonnegative integer. + monomial : (%,List VarSet,List NonNegativeInteger) -> % + ++ monomial(a,[v1..vn],[e1..en]) returns \spad{a*prod(vi**ei)}. + multivariate : (SparseUnivariatePolynomial(R),VarSet) -> % + ++ multivariate(sup,v) converts an anonymous univariable + ++ polynomial sup to a polynomial in the variable v. + multivariate : (SparseUnivariatePolynomial(%),VarSet) -> % + ++ multivariate(sup,v) converts an anonymous univariable + ++ polynomial sup to a polynomial in the variable v. + isPlus: % -> Union(List %, "failed") + ++ isPlus(p) returns \spad{[m1,...,mn]} if polynomial \spad{p = m1 + ... + mn} and + ++ \spad{n >= 2} and each mi is a nonzero monomial. + isTimes: % -> Union(List %, "failed") + ++ isTimes(p) returns \spad{[a1,...,an]} if polynomial \spad{p = a1 ... an} + ++ and \spad{n >= 2}, and, for each i, ai is either a nontrivial constant in R or else of the + ++ form \spad{x**e}, where \spad{e > 0} is an integer and x in a member of VarSet. + isExpt: % -> Union(Record(var:VarSet, exponent:NonNegativeInteger),_ + "failed") + ++ isExpt(p) returns \spad{[x, n]} if polynomial p has the form \spad{x**n} and \spad{n > 0}. + totalDegree : % -> NonNegativeInteger + ++ totalDegree(p) returns the largest sum over all monomials + ++ of all exponents of a monomial. + totalDegree : (%,List VarSet) -> NonNegativeInteger + ++ totalDegree(p, lv) returns the maximum sum (over all monomials of polynomial p) + ++ of the variables in the list lv. + variables : % -> List(VarSet) + ++ variables(p) returns the list of those variables actually + ++ appearing in the polynomial p. + primitiveMonomials: % -> List % + ++ primitiveMonomials(p) gives the list of monomials of the + ++ polynomial p with their coefficients removed. + ++ Note: \spad{primitiveMonomials(sum(a_(i) X^(i))) = [X^(1),...,X^(n)]}. + if R has OrderedSet then OrderedSet + -- OrderedRing view removed to allow EXPR to define abs + --if R has OrderedRing then OrderedRing + if (R has ConvertibleTo InputForm) and + (VarSet has ConvertibleTo InputForm) then + ConvertibleTo InputForm + if (R has ConvertibleTo Pattern Integer) and + (VarSet has ConvertibleTo Pattern Integer) then + ConvertibleTo Pattern Integer + if (R has ConvertibleTo Pattern Float) and + (VarSet has ConvertibleTo Pattern Float) then + ConvertibleTo Pattern Float + if (R has PatternMatchable Integer) and + (VarSet has PatternMatchable Integer) then + PatternMatchable Integer + if (R has PatternMatchable Float) and + (VarSet has PatternMatchable Float) then + PatternMatchable Float + if R has CommutativeRing then + resultant : (%,%,VarSet) -> % + ++ resultant(p,q,v) returns the resultant of the polynomials + ++ p and q with respect to the variable v. + discriminant : (%,VarSet) -> % + ++ discriminant(p,v) returns the disriminant of the polynomial p + ++ with respect to the variable v. + if R has GcdDomain then + GcdDomain + content: (%,VarSet) -> % + ++ content(p,v) is the gcd of the coefficients of the polynomial p + ++ when p is viewed as a univariate polynomial with respect to the + ++ variable v. + ++ Thus, for polynomial 7*x**2*y + 14*x*y**2, the gcd of the + ++ coefficients with respect to x is 7*y. + primitivePart: % -> % + ++ primitivePart(p) returns the unitCanonical associate of the + ++ polynomial p with its content divided out. + primitivePart: (%,VarSet) -> % + ++ primitivePart(p,v) returns the unitCanonical associate of the + ++ polynomial p with its content with respect to the variable v + ++ divided out. + squareFree: % -> Factored % + ++ squareFree(p) returns the square free factorization of the + ++ polynomial p. + squareFreePart: % -> % + ++ squareFreePart(p) returns product of all the irreducible factors + ++ of polynomial p each taken with multiplicity one. + + -- assertions + if R has canonicalUnitNormal then canonicalUnitNormal + ++ we can choose a unique representative for each + ++ associate class. + ++ This normalization is chosen to be normalization of + ++ leading coefficient (by default). + if R has PolynomialFactorizationExplicit then + PolynomialFactorizationExplicit + add + p:% + v:VarSet + ln:List NonNegativeInteger + lv:List VarSet + n:NonNegativeInteger + pp,qq:SparseUnivariatePolynomial % + eval(p:%, l:List Equation %) == + empty? l => p + for e in l repeat + retractIfCan(lhs e)@Union(VarSet,"failed") case "failed" => + error "cannot find a variable to evaluate" + lvar:=[retract(lhs e)@VarSet for e in l] + eval(p, lvar,[rhs e for e in l]$List(%)) + monomials p == +-- zero? p => empty() +-- concat(leadingMonomial p, monomials reductum p) +-- replaced by sequential version for efficiency, by WMSIT, 7/30/90 + ml:= empty$List(%) + while p ^= 0 repeat + ml:=concat(leadingMonomial p, ml) + p:= reductum p + reverse ml + isPlus p == + empty? rest(l := monomials p) => "failed" + l + isTimes p == + empty?(lv := variables p) or not monomial? p => "failed" + l := [monomial(1, v, degree(p, v)) for v in lv] +-- one?(r := leadingCoefficient p) => + ((r := leadingCoefficient p) = 1) => + empty? rest lv => "failed" + l + concat(r::%, l) + isExpt p == + (u := mainVariable p) case "failed" => "failed" + p = monomial(1, u::VarSet, d := degree(p, u::VarSet)) => + [u::VarSet, d] + "failed" + coefficient(p,v,n) == coefficient(univariate(p,v),n) + coefficient(p,lv,ln) == + empty? lv => + empty? ln => p + error "mismatched lists in coefficient" + empty? ln => error "mismatched lists in coefficient" + coefficient(coefficient(univariate(p,first lv),first ln), + rest lv,rest ln) + monomial(p,lv,ln) == + empty? lv => + empty? ln => p + error "mismatched lists in monomial" + empty? ln => error "mismatched lists in monomial" + monomial(monomial(p,first lv, first ln),rest lv, rest ln) + retract(p:%):VarSet == + q := mainVariable(p)::VarSet + q::% = p => q + error "Polynomial is not a single variable" + retractIfCan(p:%):Union(VarSet, "failed") == + ((q := mainVariable p) case VarSet) and (q::VarSet::% = p) => q + "failed" + mkPrim(p:%):% == monomial(1,degree p) + primitiveMonomials p == [mkPrim q for q in monomials p] + totalDegree p == + ground? p => 0 + u := univariate(p, mainVariable(p)::VarSet) + d: NonNegativeInteger := 0 + while u ^= 0 repeat + d := max(d, degree u + totalDegree leadingCoefficient u) + u := reductum u + d + totalDegree(p,lv) == + ground? p => 0 + u := univariate(p, v:=(mainVariable(p)::VarSet)) + d: NonNegativeInteger := 0 + w: NonNegativeInteger := 0 + if member?(v, lv) then w:=1 + while u ^= 0 repeat + d := max(d, w*(degree u) + totalDegree(leadingCoefficient u,lv)) + u := reductum u + d + + if R has CommutativeRing then + resultant(p1,p2,mvar) == + resultant(univariate(p1,mvar),univariate(p2,mvar)) + discriminant(p,var) == + discriminant(univariate(p,var)) + + if R has IntegralDomain then + allMonoms(l:List %):List(%) == + removeDuplicates_! concat [primitiveMonomials p for p in l] + P2R(p:%, b:List E, n:NonNegativeInteger):Vector(R) == + w := new(n, 0)$Vector(R) + for i in minIndex w .. maxIndex w for bj in b repeat + qsetelt_!(w, i, coefficient(p, bj)) + w + eq2R(l:List %, b:List E):Matrix(R) == + matrix [[coefficient(p, bj) for p in l] for bj in b] + reducedSystem(m:Matrix %):Matrix(R) == + l := listOfLists m + b := removeDuplicates_! + concat [allMonoms r for r in l]$List(List(%)) + d := [degree bj for bj in b] + mm := eq2R(first l, d) + l := rest l + while not empty? l repeat + mm := vertConcat(mm, eq2R(first l, d)) + l := rest l + mm + reducedSystem(m:Matrix %, v:Vector %): + Record(mat:Matrix R, vec:Vector R) == + l := listOfLists m + r := entries v + b : List % := removeDuplicates_! concat(allMonoms r, + concat [allMonoms s for s in l]$List(List(%))) + d := [degree bj for bj in b] + n := #d + mm := eq2R(first l, d) + w := P2R(first r, d, n) + l := rest l + r := rest r + while not empty? l repeat + mm := vertConcat(mm, eq2R(first l, d)) + w := concat(w, P2R(first r, d, n)) + l := rest l + r := rest r + [mm, w] + + if R has PolynomialFactorizationExplicit then + -- we might be in trouble if its actually only + -- a univariate polynomial category - have to remember to + -- over-ride these in UnivariatePolynomialCategory + PFBR ==>PolynomialFactorizationByRecursion(R,E,VarSet,%) + gcdPolynomial(pp,qq) == + gcdPolynomial(pp,qq)$GeneralPolynomialGcdPackage(E,VarSet,R,%) + solveLinearPolynomialEquation(lpp,pp) == + solveLinearPolynomialEquationByRecursion(lpp,pp)$PFBR + factorPolynomial(pp) == + factorByRecursion(pp)$PFBR + factorSquareFreePolynomial(pp) == + factorSquareFreeByRecursion(pp)$PFBR + factor p == + v:Union(VarSet,"failed"):=mainVariable p + v case "failed" => + ansR:=factor leadingCoefficient p + makeFR(unit(ansR)::%, + [[w.flg,w.fctr::%,w.xpnt] for w in factorList ansR]) + up:SparseUnivariatePolynomial %:=univariate(p,v) + ansSUP:=factorByRecursion(up)$PFBR + makeFR(multivariate(unit(ansSUP),v), + [[ww.flg,multivariate(ww.fctr,v),ww.xpnt] + for ww in factorList ansSUP]) + if R has CharacteristicNonZero then + mat: Matrix % + conditionP mat == + ll:=listOfLists transpose mat -- hence each list corresponds to a + -- column, i.e. to one variable + llR:List List R := [ empty() for z in first ll] + monslist:List List % := empty() + ch:=characteristic()$% + for l in ll repeat + mons:= "setUnion"/[primitiveMonomials u for u in l] + redmons:List % :=[] + for m in mons repeat + vars:=variables m + degs:=degree(m,vars) + deg1:List NonNegativeInteger + deg1:=[ ((nd:=d:Integer exquo ch:Integer) + case "failed" => return "failed" ; + nd::Integer::NonNegativeInteger) + for d in degs ] + redmons:=[monomial(1,vars,deg1),:redmons] + llR:=[[ground coefficient(u,vars,degs),:v] for u in l for v in llR] + monslist:=[redmons,:monslist] + ans:=conditionP transpose matrix llR + ans case "failed" => "failed" + i:NonNegativeInteger:=0 + [ +/[m*(ans.(i:=i+1))::% for m in mons ] + for mons in monslist] + + if R has CharacteristicNonZero then + charthRootlv: (%,List VarSet,NonNegativeInteger) -> Union(%,"failed") + charthRoot p == + vars:= variables p + empty? vars => + ans := charthRoot ground p + ans case "failed" => "failed" + ans::R::% + ch:=characteristic()$% + charthRootlv(p,vars,ch) + charthRootlv(p,vars,ch) == + empty? vars => + ans := charthRoot ground p + ans case "failed" => "failed" + ans::R::% + v:=first vars + vars:=rest vars + d:=degree(p,v) + ans:% := 0 + while (d>0) repeat + (dd:=(d::Integer exquo ch::Integer)) case "failed" => + return "failed" + cp:=coefficient(p,v,d) + p:=p-monomial(cp,v,d) + ansx:=charthRootlv(cp,vars,ch) + ansx case "failed" => return "failed" + d:=degree(p,v) + ans:=ans+monomial(ansx,v,dd::Integer::NonNegativeInteger) + ansx:=charthRootlv(p,vars,ch) + ansx case "failed" => return "failed" + return ans+ansx + + monicDivide(p1,p2,mvar) == + result:=monicDivide(univariate(p1,mvar),univariate(p2,mvar)) + [multivariate(result.quotient,mvar), + multivariate(result.remainder,mvar)] + + + if R has GcdDomain then + if R has EuclideanDomain and R has CharacteristicZero then + squareFree p == squareFree(p)$MultivariateSquareFree(E,VarSet,R,%) + else + squareFree p == squareFree(p)$PolynomialSquareFree(VarSet,E,R,%) + squareFreePart p == + unit(s := squareFree p) * */[f.factor for f in factors s] + content(p,v) == content univariate(p,v) + primitivePart p == + unitNormal((p exquo content p) ::%).canonical + primitivePart(p,v) == + unitNormal((p exquo content(p,v)) ::%).canonical + if R has OrderedSet then + p:% < q:% == + (dp:= degree p) < (dq := degree q) => (leadingCoefficient q) > 0 + dq < dp => (leadingCoefficient p) < 0 + leadingCoefficient(p - q) < 0 + if (R has PatternMatchable Integer) and + (VarSet has PatternMatchable Integer) then + patternMatch(p:%, pat:Pattern Integer, + l:PatternMatchResult(Integer, %)) == + patternMatch(p, pat, + l)$PatternMatchPolynomialCategory(Integer,E,VarSet,R,%) + if (R has PatternMatchable Float) and + (VarSet has PatternMatchable Float) then + patternMatch(p:%, pat:Pattern Float, + l:PatternMatchResult(Float, %)) == + patternMatch(p, pat, + l)$PatternMatchPolynomialCategory(Float,E,VarSet,R,%) + + if (R has ConvertibleTo Pattern Integer) and + (VarSet has ConvertibleTo Pattern Integer) then + convert(x:%):Pattern(Integer) == + map(convert, convert, + x)$PolynomialCategoryLifting(E,VarSet,R,%,Pattern Integer) + if (R has ConvertibleTo Pattern Float) and + (VarSet has ConvertibleTo Pattern Float) then + convert(x:%):Pattern(Float) == + map(convert, convert, + x)$PolynomialCategoryLifting(E, VarSet, R, %, Pattern Float) + if (R has ConvertibleTo InputForm) and + (VarSet has ConvertibleTo InputForm) then + convert(p:%):InputForm == + map(convert, convert, + p)$PolynomialCategoryLifting(E,VarSet,R,%,InputForm) + +@ +\section{POLYCAT.lsp BOOTSTRAP} +{\bf POLYCAT} depends on itself. We need to break this cycle to build +the algebra. So we keep a cached copy of the translated {\bf POLYCAT} +category which we can write into the {\bf MID} directory. We compile +the lisp code and copy the {\bf POLYCAT.o} file to the {\bf OUT} directory. +This is eventually forcibly replaced by a recompiled version. + +Note that this code is not included in the generated catdef.spad file. + +<<POLYCAT.lsp BOOTSTRAP>>= + +(|/VERSIONCHECK| 2) + +(SETQ |PolynomialCategory;CAT| (QUOTE NIL)) + +(SETQ |PolynomialCategory;AL| (QUOTE NIL)) + +(DEFUN |PolynomialCategory| (|&REST| #1=#:G101841 |&AUX| #2=#:G101839) + (DSETQ #2# #1#) + (LET (#3=#:G101840) + (COND + ((SETQ #3# (|assoc| (|devaluateList| #2#) |PolynomialCategory;AL|)) + (CDR #3#)) + (T + (SETQ |PolynomialCategory;AL| + (|cons5| + (CONS + (|devaluateList| #2#) + (SETQ #3# (APPLY (FUNCTION |PolynomialCategory;|) #2#))) + |PolynomialCategory;AL|)) + #3#)))) + +(DEFUN |PolynomialCategory;| (|t#1| |t#2| |t#3|) + (PROG (#1=#:G101838) + (RETURN + (PROG1 + (LETT #1# + (|sublisV| + (PAIR + (QUOTE (|t#1| |t#2| |t#3|)) + (LIST + (|devaluate| |t#1|) + (|devaluate| |t#2|) + (|devaluate| |t#3|))) + (COND + (|PolynomialCategory;CAT|) + ((QUOTE T) + (LETT |PolynomialCategory;CAT| + (|Join| + (|PartialDifferentialRing| (QUOTE |t#3|)) + (|FiniteAbelianMonoidRing| (QUOTE |t#1|) (QUOTE |t#2|)) + (|Evalable| (QUOTE |$|)) + (|InnerEvalable| (QUOTE |t#3|) (QUOTE |t#1|)) + (|InnerEvalable| (QUOTE |t#3|) (QUOTE |$|)) + (|RetractableTo| (QUOTE |t#3|)) + (|FullyLinearlyExplicitRingOver| (QUOTE |t#1|)) + (|mkCategory| + (QUOTE |domain|) + (QUOTE ( + ((|degree| ((|NonNegativeInteger|) |$| |t#3|)) T) + ((|degree| + ((|List| (|NonNegativeInteger|)) + |$| + (|List| |t#3|))) T) + ((|coefficient| + (|$| |$| |t#3| (|NonNegativeInteger|))) T) + ((|coefficient| + (|$| + |$| + (|List| |t#3|) + (|List| (|NonNegativeInteger|)))) T) + ((|monomials| ((|List| |$|) |$|)) T) + ((|univariate| + ((|SparseUnivariatePolynomial| |$|) |$| |t#3|)) T) + ((|univariate| + ((|SparseUnivariatePolynomial| |t#1|) |$|)) T) + ((|mainVariable| ((|Union| |t#3| "failed") |$|)) T) + ((|minimumDegree| + ((|NonNegativeInteger|) |$| |t#3|)) T) + ((|minimumDegree| + ((|List| (|NonNegativeInteger|)) + |$| + (|List| |t#3|))) T) + ((|monicDivide| + ((|Record| + (|:| |quotient| |$|) + (|:| |remainder| |$|)) + |$| + |$| + |t#3|)) T) + ((|monomial| (|$| |$| |t#3| (|NonNegativeInteger|))) T) + ((|monomial| + (|$| + |$| + (|List| |t#3|) + (|List| (|NonNegativeInteger|)))) T) + ((|multivariate| + (|$| (|SparseUnivariatePolynomial| |t#1|) |t#3|)) T) + ((|multivariate| + (|$| (|SparseUnivariatePolynomial| |$|) |t#3|)) T) + ((|isPlus| ((|Union| (|List| |$|) "failed") |$|)) T) + ((|isTimes| ((|Union| (|List| |$|) "failed") |$|)) T) + ((|isExpt| + ((|Union| + (|Record| + (|:| |var| |t#3|) + (|:| |exponent| (|NonNegativeInteger|))) + "failed") + |$|)) T) + ((|totalDegree| ((|NonNegativeInteger|) |$|)) T) + ((|totalDegree| + ((|NonNegativeInteger|) |$| (|List| |t#3|))) T) + ((|variables| ((|List| |t#3|) |$|)) T) + ((|primitiveMonomials| ((|List| |$|) |$|)) T) + ((|resultant| (|$| |$| |$| |t#3|)) + (|has| |t#1| (|CommutativeRing|))) + ((|discriminant| (|$| |$| |t#3|)) + (|has| |t#1| (|CommutativeRing|))) + ((|content| (|$| |$| |t#3|)) + (|has| |t#1| (|GcdDomain|))) + ((|primitivePart| (|$| |$|)) + (|has| |t#1| (|GcdDomain|))) + ((|primitivePart| (|$| |$| |t#3|)) + (|has| |t#1| (|GcdDomain|))) + ((|squareFree| ((|Factored| |$|) |$|)) + (|has| |t#1| (|GcdDomain|))) + ((|squareFreePart| (|$| |$|)) ( + |has| |t#1| (|GcdDomain|))))) + (QUOTE ( + ((|OrderedSet|) (|has| |t#1| (|OrderedSet|))) + ((|ConvertibleTo| (|InputForm|)) + (AND + (|has| |t#3| (|ConvertibleTo| (|InputForm|))) + (|has| |t#1| (|ConvertibleTo| (|InputForm|))))) + ((|ConvertibleTo| (|Pattern| (|Integer|))) + (AND + (|has| |t#3| + (|ConvertibleTo| (|Pattern| (|Integer|)))) + (|has| |t#1| + (|ConvertibleTo| (|Pattern| (|Integer|)))))) + ((|ConvertibleTo| (|Pattern| (|Float|))) + (AND + (|has| |t#3| + (|ConvertibleTo| (|Pattern| (|Float|)))) + (|has| |t#1| + (|ConvertibleTo| (|Pattern| (|Float|)))))) + ((|PatternMatchable| (|Integer|)) + (AND + (|has| |t#3| (|PatternMatchable| (|Integer|))) + (|has| |t#1| (|PatternMatchable| (|Integer|))))) + ((|PatternMatchable| (|Float|)) + (AND + (|has| |t#3| (|PatternMatchable| (|Float|))) + (|has| |t#1| (|PatternMatchable| (|Float|))))) + ((|GcdDomain|) (|has| |t#1| (|GcdDomain|))) + (|canonicalUnitNormal| + (|has| |t#1| (ATTRIBUTE |canonicalUnitNormal|))) + ((|PolynomialFactorizationExplicit|) + (|has| |t#1| (|PolynomialFactorizationExplicit|))))) + (QUOTE ( + (|Factored| |$|) + (|List| |$|) + (|List| |t#3|) + (|NonNegativeInteger|) + (|SparseUnivariatePolynomial| |$|) + (|SparseUnivariatePolynomial| |t#1|) + (|List| (|NonNegativeInteger|)))) + NIL)) + . #2=(|PolynomialCategory|))))) + . #2#) + (SETELT #1# 0 + (LIST + (QUOTE |PolynomialCategory|) + (|devaluate| |t#1|) + (|devaluate| |t#2|) + (|devaluate| |t#3|))))))) + +@ +\section{POLYCAT-.lsp BOOTSTRAP} +{\bf POLYCAT-} depends on {\bf POLYCAT}. We need to break this cycle to build +the algebra. So we keep a cached copy of the translated {\bf POLYCAT-} +category which we can write into the {\bf MID} directory. We compile +the lisp code and copy the {\bf POLYCAT-.o} file to the {\bf OUT} directory. +This is eventually forcibly replaced by a recompiled version. + +Note that this code is not included in the generated catdef.spad file. + +<<POLYCAT-.lsp BOOTSTRAP>>= + +(|/VERSIONCHECK| 2) + +(DEFUN |POLYCAT-;eval;SLS;1| (|p| |l| |$|) + (PROG (#1=#:G101870 #2=#:G101860 #3=#:G101868 #4=#:G101869 + |lvar| #5=#:G101866 |e| #6=#:G101867) + (RETURN + (SEQ + (COND + ((NULL |l|) |p|) + ((QUOTE T) + (SEQ + (SEQ + (EXIT + (SEQ + (LETT |e| NIL |POLYCAT-;eval;SLS;1|) + (LETT #1# |l| |POLYCAT-;eval;SLS;1|) + G190 + (COND + ((OR + (ATOM #1#) + (PROGN (LETT |e| (CAR #1#) |POLYCAT-;eval;SLS;1|) NIL)) + (GO G191))) + (SEQ + (EXIT + (COND + ((QEQCAR + (SPADCALL + (SPADCALL |e| (QREFELT |$| 11)) + (QREFELT |$| 13)) + 1) + (PROGN + (LETT #2# + (|error| "cannot find a variable to evaluate") + |POLYCAT-;eval;SLS;1|) + (GO #2#)))))) + (LETT #1# (CDR #1#) |POLYCAT-;eval;SLS;1|) + (GO G190) + G191 + (EXIT NIL))) + #2# + (EXIT #2#)) + (LETT |lvar| + (PROGN + (LETT #3# NIL |POLYCAT-;eval;SLS;1|) + (SEQ + (LETT |e| NIL |POLYCAT-;eval;SLS;1|) + (LETT #4# |l| |POLYCAT-;eval;SLS;1|) + G190 + (COND + ((OR + (ATOM #4#) + (PROGN + (LETT |e| (CAR #4#) |POLYCAT-;eval;SLS;1|) NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #3# + (CONS + (SPADCALL + (SPADCALL |e| (QREFELT |$| 11)) + (QREFELT |$| 14)) + #3#) + |POLYCAT-;eval;SLS;1|))) + (LETT #4# (CDR #4#) |POLYCAT-;eval;SLS;1|) + (GO G190) + G191 + (EXIT (NREVERSE0 #3#)))) + |POLYCAT-;eval;SLS;1|) + (EXIT + (SPADCALL + |p| + |lvar| + (PROGN + (LETT #5# NIL |POLYCAT-;eval;SLS;1|) + (SEQ + (LETT |e| NIL |POLYCAT-;eval;SLS;1|) + (LETT #6# |l| |POLYCAT-;eval;SLS;1|) + G190 + (COND + ((OR + (ATOM #6#) + (PROGN + (LETT |e| (CAR #6#) |POLYCAT-;eval;SLS;1|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #5# + (CONS (SPADCALL |e| (QREFELT |$| 15)) #5#) + |POLYCAT-;eval;SLS;1|))) + (LETT #6# (CDR #6#) |POLYCAT-;eval;SLS;1|) + (GO G190) + G191 + (EXIT (NREVERSE0 #5#)))) + (QREFELT |$| 18)))))))))) + +(DEFUN |POLYCAT-;monomials;SL;2| (|p| |$|) + (PROG (|ml|) + (RETURN + (SEQ + (LETT |ml| NIL |POLYCAT-;monomials;SL;2|) + (SEQ G190 + (COND + ((NULL + (COND + ((SPADCALL |p| (|spadConstant| |$| 21) (QREFELT |$| 24)) + (QUOTE NIL)) + ((QUOTE T) (QUOTE T)))) + (GO G191))) + (SEQ + (LETT |ml| + (CONS (SPADCALL |p| (QREFELT |$| 25)) |ml|) + |POLYCAT-;monomials;SL;2|) + (EXIT + (LETT |p| + (SPADCALL |p| (QREFELT |$| 26)) + |POLYCAT-;monomials;SL;2|))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (EXIT (REVERSE |ml|)))))) + +(DEFUN |POLYCAT-;isPlus;SU;3| (|p| |$|) + (PROG (|l|) + (RETURN + (COND + ((NULL + (CDR + (LETT |l| + (SPADCALL |p| (QREFELT |$| 28)) + |POLYCAT-;isPlus;SU;3|))) + (CONS 1 "failed")) + ((QUOTE T) (CONS 0 |l|)))))) + +(DEFUN |POLYCAT-;isTimes;SU;4| (|p| |$|) + (PROG (|lv| #1=#:G101892 |v| #2=#:G101893 |l| |r|) + (RETURN + (SEQ + (COND + ((OR + (NULL + (LETT |lv| + (SPADCALL |p| (QREFELT |$| 31)) + |POLYCAT-;isTimes;SU;4|)) + (NULL (SPADCALL |p| (QREFELT |$| 32)))) + (CONS 1 "failed")) + ((QUOTE T) + (SEQ + (LETT |l| + (PROGN + (LETT #1# NIL |POLYCAT-;isTimes;SU;4|) + (SEQ + (LETT |v| NIL |POLYCAT-;isTimes;SU;4|) + (LETT #2# |lv| |POLYCAT-;isTimes;SU;4|) + G190 + (COND + ((OR + (ATOM #2#) + (PROGN + (LETT |v| (CAR #2#) |POLYCAT-;isTimes;SU;4|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #1# + (CONS + (SPADCALL + (|spadConstant| |$| 33) + |v| + (SPADCALL |p| |v| (QREFELT |$| 36)) + (QREFELT |$| 37)) + #1#) + |POLYCAT-;isTimes;SU;4|))) + (LETT #2# (CDR #2#) |POLYCAT-;isTimes;SU;4|) + (GO G190) + G191 + (EXIT (NREVERSE0 #1#)))) + |POLYCAT-;isTimes;SU;4|) + (EXIT + (COND + ((SPADCALL + (LETT |r| + (SPADCALL |p| (QREFELT |$| 38)) + |POLYCAT-;isTimes;SU;4|) + (QREFELT |$| 39)) + (COND + ((NULL (CDR |lv|)) (CONS 1 "failed")) + ((QUOTE T) (CONS 0 |l|)))) + ((QUOTE T) + (CONS 0 + (CONS (SPADCALL |r| (QREFELT |$| 40)) |l|)))))))))))) + +(DEFUN |POLYCAT-;isExpt;SU;5| (|p| |$|) + (PROG (|u| |d|) + (RETURN + (SEQ + (LETT |u| (SPADCALL |p| (QREFELT |$| 42)) |POLYCAT-;isExpt;SU;5|) + (EXIT + (COND + ((OR + (QEQCAR |u| 1) + (NULL + (SPADCALL |p| + (SPADCALL + (|spadConstant| |$| 33) + (QCDR |u|) + (LETT |d| + (SPADCALL |p| (QCDR |u|) (QREFELT |$| 36)) + |POLYCAT-;isExpt;SU;5|) + (QREFELT |$| 37)) + (QREFELT |$| 24)))) + (CONS 1 "failed")) + ((QUOTE T) (CONS 0 (CONS (QCDR |u|) |d|))))))))) + +(DEFUN |POLYCAT-;coefficient;SVarSetNniS;6| (|p| |v| |n| |$|) + (SPADCALL (SPADCALL |p| |v| (QREFELT |$| 47)) |n| (QREFELT |$| 49))) + +(DEFUN |POLYCAT-;coefficient;SLLS;7| (|p| |lv| |ln| |$|) + (COND + ((NULL |lv|) + (COND + ((NULL |ln|) |p|) + ((QUOTE T) (|error| "mismatched lists in coefficient")))) + ((NULL |ln|) + (|error| "mismatched lists in coefficient")) + ((QUOTE T) + (SPADCALL + (SPADCALL + (SPADCALL |p| (|SPADfirst| |lv|) (QREFELT |$| 47)) + (|SPADfirst| |ln|) + (QREFELT |$| 49)) + (CDR |lv|) + (CDR |ln|) + (QREFELT |$| 52))))) + +(DEFUN |POLYCAT-;monomial;SLLS;8| (|p| |lv| |ln| |$|) + (COND + ((NULL |lv|) + (COND + ((NULL |ln|) |p|) + ((QUOTE T) (|error| "mismatched lists in monomial")))) + ((NULL |ln|) + (|error| "mismatched lists in monomial")) + ((QUOTE T) + (SPADCALL + (SPADCALL |p| (|SPADfirst| |lv|) (|SPADfirst| |ln|) (QREFELT |$| 37)) + (CDR |lv|) + (CDR |ln|) + (QREFELT |$| 54))))) + +(DEFUN |POLYCAT-;retract;SVarSet;9| (|p| |$|) + (PROG (#1=#:G101918 |q|) + (RETURN + (SEQ + (LETT |q| + (PROG2 + (LETT #1# + (SPADCALL |p| (QREFELT |$| 42)) + |POLYCAT-;retract;SVarSet;9|) + (QCDR #1#) + (|check-union| (QEQCAR #1# 0) (QREFELT |$| 9) #1#)) + |POLYCAT-;retract;SVarSet;9|) + (EXIT + (COND + ((SPADCALL + (SPADCALL |q| (QREFELT |$| 56)) + |p| + (QREFELT |$| 24)) + |q|) + ((QUOTE T) + (|error| "Polynomial is not a single variable")))))))) + +(DEFUN |POLYCAT-;retractIfCan;SU;10| (|p| |$|) + (PROG (|q| #1=#:G101926) + (RETURN + (SEQ + (EXIT + (SEQ + (SEQ + (LETT |q| + (SPADCALL |p| (QREFELT |$| 42)) + |POLYCAT-;retractIfCan;SU;10|) + (EXIT + (COND + ((QEQCAR |q| 0) + (COND + ((SPADCALL + (SPADCALL (QCDR |q|) (QREFELT |$| 56)) + |p| + (QREFELT |$| 24)) + (PROGN + (LETT #1# |q| |POLYCAT-;retractIfCan;SU;10|) + (GO #1#)))))))) + (EXIT (CONS 1 "failed")))) + #1# + (EXIT #1#))))) + +(DEFUN |POLYCAT-;mkPrim| (|p| |$|) + (SPADCALL + (|spadConstant| |$| 34) + (SPADCALL |p| (QREFELT |$| 59)) + (QREFELT |$| 60))) + +(DEFUN |POLYCAT-;primitiveMonomials;SL;12| (|p| |$|) + (PROG (#1=#:G101931 |q| #2=#:G101932) + (RETURN + (SEQ + (PROGN + (LETT #1# NIL |POLYCAT-;primitiveMonomials;SL;12|) + (SEQ + (LETT |q| NIL |POLYCAT-;primitiveMonomials;SL;12|) + (LETT #2# + (SPADCALL |p| (QREFELT |$| 28)) + |POLYCAT-;primitiveMonomials;SL;12|) + G190 + (COND + ((OR + (ATOM #2#) + (PROGN + (LETT |q| (CAR #2#) |POLYCAT-;primitiveMonomials;SL;12|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #1# + (CONS + (|POLYCAT-;mkPrim| |q| |$|) + #1#) + |POLYCAT-;primitiveMonomials;SL;12|))) + (LETT #2# (CDR #2#) |POLYCAT-;primitiveMonomials;SL;12|) + (GO G190) + G191 + (EXIT (NREVERSE0 #1#)))))))) + +(DEFUN |POLYCAT-;totalDegree;SNni;13| (|p| |$|) + (PROG (#1=#:G101934 |d| |u|) + (RETURN + (SEQ + (COND + ((SPADCALL |p| (QREFELT |$| 62)) 0) + ((QUOTE T) + (SEQ + (LETT |u| + (SPADCALL |p| + (PROG2 + (LETT #1# + (SPADCALL |p| (QREFELT |$| 42)) + |POLYCAT-;totalDegree;SNni;13|) + (QCDR #1#) + (|check-union| (QEQCAR #1# 0) (QREFELT |$| 9) #1#)) + (QREFELT |$| 47)) + |POLYCAT-;totalDegree;SNni;13|) + (LETT |d| 0 |POLYCAT-;totalDegree;SNni;13|) + (SEQ G190 + (COND + ((NULL + (COND + ((SPADCALL |u| (|spadConstant| |$| 63) (QREFELT |$| 64)) + (QUOTE NIL)) + ((QUOTE T) (QUOTE T)))) (GO G191))) + (SEQ + (LETT |d| + (MAX |d| + (|+| + (SPADCALL |u| (QREFELT |$| 65)) + (SPADCALL + (SPADCALL |u| (QREFELT |$| 66)) + (QREFELT |$| 67)))) + |POLYCAT-;totalDegree;SNni;13|) + (EXIT + (LETT |u| + (SPADCALL |u| (QREFELT |$| 68)) + |POLYCAT-;totalDegree;SNni;13|))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (EXIT |d|)))))))) + +(DEFUN |POLYCAT-;totalDegree;SLNni;14| (|p| |lv| |$|) + (PROG (#1=#:G101942 |v| |w| |d| |u|) + (RETURN + (SEQ + (COND + ((SPADCALL |p| (QREFELT |$| 62)) 0) + ((QUOTE T) + (SEQ + (LETT |u| + (SPADCALL |p| + (LETT |v| + (PROG2 + (LETT #1# + (SPADCALL |p| (QREFELT |$| 42)) + |POLYCAT-;totalDegree;SLNni;14|) + (QCDR #1#) + (|check-union| (QEQCAR #1# 0) (QREFELT |$| 9) #1#)) + |POLYCAT-;totalDegree;SLNni;14|) + (QREFELT |$| 47)) + |POLYCAT-;totalDegree;SLNni;14|) + (LETT |d| 0 |POLYCAT-;totalDegree;SLNni;14|) + (LETT |w| 0 |POLYCAT-;totalDegree;SLNni;14|) + (COND + ((SPADCALL |v| |lv| (QREFELT |$| 70)) + (LETT |w| 1 |POLYCAT-;totalDegree;SLNni;14|))) + (SEQ G190 + (COND + ((NULL + (COND + ((SPADCALL |u| (|spadConstant| |$| 63) (QREFELT |$| 64)) + (QUOTE NIL)) + ((QUOTE T) (QUOTE T)))) + (GO G191))) + (SEQ + (LETT |d| + (MAX |d| + (|+| + (|*| |w| (SPADCALL |u| (QREFELT |$| 65))) + (SPADCALL + (SPADCALL |u| (QREFELT |$| 66)) + |lv| + (QREFELT |$| 71)))) + |POLYCAT-;totalDegree;SLNni;14|) + (EXIT + (LETT |u| + (SPADCALL |u| (QREFELT |$| 68)) + |POLYCAT-;totalDegree;SLNni;14|))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (EXIT |d|)))))))) + +(DEFUN |POLYCAT-;resultant;2SVarSetS;15| (|p1| |p2| |mvar| |$|) + (SPADCALL + (SPADCALL |p1| |mvar| (QREFELT |$| 47)) + (SPADCALL |p2| |mvar| (QREFELT |$| 47)) + (QREFELT |$| 73))) + +(DEFUN |POLYCAT-;discriminant;SVarSetS;16| (|p| |var| |$|) + (SPADCALL (SPADCALL |p| |var| (QREFELT |$| 47)) (QREFELT |$| 75))) + +(DEFUN |POLYCAT-;allMonoms| (|l| |$|) + (PROG (#1=#:G101954 |p| #2=#:G101955) + (RETURN + (SEQ + (SPADCALL + (SPADCALL + (PROGN + (LETT #1# NIL |POLYCAT-;allMonoms|) + (SEQ + (LETT |p| NIL |POLYCAT-;allMonoms|) + (LETT #2# |l| |POLYCAT-;allMonoms|) + G190 + (COND + ((OR + (ATOM #2#) + (PROGN (LETT |p| (CAR #2#) |POLYCAT-;allMonoms|) NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #1# + (CONS (SPADCALL |p| (QREFELT |$| 77)) #1#) + |POLYCAT-;allMonoms|))) + (LETT #2# (CDR #2#) |POLYCAT-;allMonoms|) + (GO G190) + G191 + (EXIT (NREVERSE0 #1#)))) + (QREFELT |$| 79)) + (QREFELT |$| 80)))))) + +(DEFUN |POLYCAT-;P2R| (|p| |b| |n| |$|) + (PROG (|w| |bj| #1=#:G101960 |i| #2=#:G101959) + (RETURN + (SEQ + (LETT |w| + (SPADCALL |n| (|spadConstant| |$| 22) (QREFELT |$| 82)) + |POLYCAT-;P2R|) + (SEQ + (LETT |bj| NIL |POLYCAT-;P2R|) + (LETT #1# |b| |POLYCAT-;P2R|) + (LETT |i| (SPADCALL |w| (QREFELT |$| 84)) |POLYCAT-;P2R|) + (LETT #2# (QVSIZE |w|) |POLYCAT-;P2R|) + G190 + (COND + ((OR + (|>| |i| #2#) + (ATOM #1#) + (PROGN (LETT |bj| (CAR #1#) |POLYCAT-;P2R|) NIL)) + (GO G191))) + (SEQ + (EXIT + (SPADCALL |w| |i| + (SPADCALL |p| |bj| (QREFELT |$| 85)) + (QREFELT |$| 86)))) + (LETT |i| + (PROG1 + (|+| |i| 1) + (LETT #1# (CDR #1#) |POLYCAT-;P2R|)) + |POLYCAT-;P2R|) + (GO G190) + G191 + (EXIT NIL)) + (EXIT |w|))))) + +(DEFUN |POLYCAT-;eq2R| (|l| |b| |$|) + (PROG (#1=#:G101964 |bj| #2=#:G101965 #3=#:G101966 |p| #4=#:G101967) + (RETURN + (SEQ + (SPADCALL + (PROGN + (LETT #1# NIL |POLYCAT-;eq2R|) + (SEQ + (LETT |bj| NIL |POLYCAT-;eq2R|) + (LETT #2# |b| |POLYCAT-;eq2R|) + G190 + (COND + ((OR + (ATOM #2#) + (PROGN (LETT |bj| (CAR #2#) |POLYCAT-;eq2R|) NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #1# + (CONS + (PROGN + (LETT #3# NIL |POLYCAT-;eq2R|) + (SEQ + (LETT |p| NIL |POLYCAT-;eq2R|) + (LETT #4# |l| |POLYCAT-;eq2R|) + G190 + (COND + ((OR + (ATOM #4#) + (PROGN + (LETT |p| (CAR #4#) |POLYCAT-;eq2R|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #3# + (CONS (SPADCALL |p| |bj| (QREFELT |$| 85)) #3#) + |POLYCAT-;eq2R|))) + (LETT #4# (CDR #4#) |POLYCAT-;eq2R|) + (GO G190) + G191 + (EXIT (NREVERSE0 #3#)))) + #1#) + |POLYCAT-;eq2R|))) + (LETT #2# (CDR #2#) |POLYCAT-;eq2R|) + (GO G190) + G191 + (EXIT (NREVERSE0 #1#)))) + (QREFELT |$| 89)))))) + +(DEFUN |POLYCAT-;reducedSystem;MM;20| (|m| |$|) + (PROG (#1=#:G101979 |r| #2=#:G101980 |b| #3=#:G101977 + |bj| #4=#:G101978 |d| |mm| |l|) + (RETURN + (SEQ + (LETT |l| + (SPADCALL |m| (QREFELT |$| 92)) + |POLYCAT-;reducedSystem;MM;20|) + (LETT |b| + (SPADCALL + (SPADCALL + (PROGN + (LETT #1# NIL |POLYCAT-;reducedSystem;MM;20|) + (SEQ + (LETT |r| NIL |POLYCAT-;reducedSystem;MM;20|) + (LETT #2# |l| |POLYCAT-;reducedSystem;MM;20|) + G190 + (COND + ((OR + (ATOM #2#) + (PROGN + (LETT |r| (CAR #2#) |POLYCAT-;reducedSystem;MM;20|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #1# + (CONS (|POLYCAT-;allMonoms| |r| |$|) #1#) + |POLYCAT-;reducedSystem;MM;20|))) + (LETT #2# (CDR #2#) |POLYCAT-;reducedSystem;MM;20|) + (GO G190) + G191 + (EXIT (NREVERSE0 #1#)))) + (QREFELT |$| 79)) + (QREFELT |$| 80)) + |POLYCAT-;reducedSystem;MM;20|) + (LETT |d| + (PROGN + (LETT #3# NIL |POLYCAT-;reducedSystem;MM;20|) + (SEQ + (LETT |bj| NIL |POLYCAT-;reducedSystem;MM;20|) + (LETT #4# |b| |POLYCAT-;reducedSystem;MM;20|) + G190 + (COND + ((OR + (ATOM #4#) + (PROGN + (LETT |bj| (CAR #4#) |POLYCAT-;reducedSystem;MM;20|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #3# + (CONS (SPADCALL |bj| (QREFELT |$| 59)) #3#) + |POLYCAT-;reducedSystem;MM;20|))) + (LETT #4# (CDR #4#) |POLYCAT-;reducedSystem;MM;20|) + (GO G190) + G191 + (EXIT (NREVERSE0 #3#)))) + |POLYCAT-;reducedSystem;MM;20|) + (LETT |mm| + (|POLYCAT-;eq2R| (|SPADfirst| |l|) |d| |$|) + |POLYCAT-;reducedSystem;MM;20|) + (LETT |l| (CDR |l|) |POLYCAT-;reducedSystem;MM;20|) + (SEQ G190 + (COND + ((NULL (COND ((NULL |l|) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) + (GO G191))) + (SEQ + (LETT |mm| + (SPADCALL |mm| + (|POLYCAT-;eq2R| (|SPADfirst| |l|) |d| |$|) (QREFELT |$| 93)) + |POLYCAT-;reducedSystem;MM;20|) + (EXIT (LETT |l| (CDR |l|) |POLYCAT-;reducedSystem;MM;20|))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (EXIT |mm|))))) + +(DEFUN |POLYCAT-;reducedSystem;MVR;21| (|m| |v| |$|) + (PROG (#1=#:G101994 |s| #2=#:G101995 |b| #3=#:G101992 |bj| #4=#:G101993 + |d| |n| |mm| |w| |l| |r|) + (RETURN + (SEQ + (LETT |l| (SPADCALL |m| (QREFELT |$| 92)) |POLYCAT-;reducedSystem;MVR;21|) + (LETT |r| (SPADCALL |v| (QREFELT |$| 97)) |POLYCAT-;reducedSystem;MVR;21|) + (LETT |b| + (SPADCALL + (SPADCALL + (|POLYCAT-;allMonoms| |r| |$|) + (SPADCALL + (PROGN + (LETT #1# NIL |POLYCAT-;reducedSystem;MVR;21|) + (SEQ + (LETT |s| NIL |POLYCAT-;reducedSystem;MVR;21|) + (LETT #2# |l| |POLYCAT-;reducedSystem;MVR;21|) + G190 + (COND + ((OR + (ATOM #2#) + (PROGN + (LETT |s| (CAR #2#) |POLYCAT-;reducedSystem;MVR;21|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #1# + (CONS (|POLYCAT-;allMonoms| |s| |$|) #1#) + |POLYCAT-;reducedSystem;MVR;21|))) + (LETT #2# (CDR #2#) |POLYCAT-;reducedSystem;MVR;21|) + (GO G190) + G191 + (EXIT (NREVERSE0 #1#)))) + (QREFELT |$| 79)) + (QREFELT |$| 98)) + (QREFELT |$| 80)) + |POLYCAT-;reducedSystem;MVR;21|) + (LETT |d| + (PROGN + (LETT #3# NIL |POLYCAT-;reducedSystem;MVR;21|) + (SEQ + (LETT |bj| NIL |POLYCAT-;reducedSystem;MVR;21|) + (LETT #4# |b| |POLYCAT-;reducedSystem;MVR;21|) + G190 + (COND + ((OR + (ATOM #4#) + (PROGN + (LETT |bj| (CAR #4#) |POLYCAT-;reducedSystem;MVR;21|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #3# + (CONS (SPADCALL |bj| (QREFELT |$| 59)) #3#) + |POLYCAT-;reducedSystem;MVR;21|))) + (LETT #4# (CDR #4#) |POLYCAT-;reducedSystem;MVR;21|) + (GO G190) + G191 + (EXIT (NREVERSE0 #3#)))) + |POLYCAT-;reducedSystem;MVR;21|) + (LETT |n| (LENGTH |d|) |POLYCAT-;reducedSystem;MVR;21|) + (LETT |mm| + (|POLYCAT-;eq2R| (|SPADfirst| |l|) |d| |$|) + |POLYCAT-;reducedSystem;MVR;21|) + (LETT |w| + (|POLYCAT-;P2R| (|SPADfirst| |r|) |d| |n| |$|) + |POLYCAT-;reducedSystem;MVR;21|) + (LETT |l| (CDR |l|) |POLYCAT-;reducedSystem;MVR;21|) + (LETT |r| (CDR |r|) |POLYCAT-;reducedSystem;MVR;21|) + (SEQ G190 + (COND + ((NULL (COND ((NULL |l|) (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) + (GO G191))) + (SEQ + (LETT |mm| + (SPADCALL |mm| + (|POLYCAT-;eq2R| (|SPADfirst| |l|) |d| |$|) + (QREFELT |$| 93)) + |POLYCAT-;reducedSystem;MVR;21|) + (LETT |w| + (SPADCALL |w| + (|POLYCAT-;P2R| (|SPADfirst| |r|) |d| |n| |$|) + (QREFELT |$| 99)) + |POLYCAT-;reducedSystem;MVR;21|) + (LETT |l| (CDR |l|) |POLYCAT-;reducedSystem;MVR;21|) + (EXIT (LETT |r| (CDR |r|) |POLYCAT-;reducedSystem;MVR;21|))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (EXIT (CONS |mm| |w|)))))) + +(DEFUN |POLYCAT-;gcdPolynomial;3Sup;22| (|pp| |qq| |$|) + (SPADCALL |pp| |qq| (QREFELT |$| 104))) + +(DEFUN |POLYCAT-;solveLinearPolynomialEquation;LSupU;23| (|lpp| |pp| |$|) + (SPADCALL |lpp| |pp| (QREFELT |$| 109))) + +(DEFUN |POLYCAT-;factorPolynomial;SupF;24| (|pp| |$|) + (SPADCALL |pp| (QREFELT |$| 114))) + +(DEFUN |POLYCAT-;factorSquareFreePolynomial;SupF;25| (|pp| |$|) + (SPADCALL |pp| (QREFELT |$| 117))) + +(DEFUN |POLYCAT-;factor;SF;26| (|p| |$|) + (PROG (|v| |ansR| #1=#:G102039 |w| #2=#:G102040 |up| |ansSUP| + #3=#:G102037 |ww| #4=#:G102038) + (RETURN + (SEQ + (LETT |v| (SPADCALL |p| (QREFELT |$| 42)) |POLYCAT-;factor;SF;26|) + (EXIT + (COND + ((QEQCAR |v| 1) + (SEQ + (LETT |ansR| + (SPADCALL (SPADCALL |p| (QREFELT |$| 38)) (QREFELT |$| 120)) + |POLYCAT-;factor;SF;26|) + (EXIT + (SPADCALL + (SPADCALL + (SPADCALL |ansR| (QREFELT |$| 122)) + (QREFELT |$| 40)) + (PROGN + (LETT #1# NIL |POLYCAT-;factor;SF;26|) + (SEQ + (LETT |w| NIL |POLYCAT-;factor;SF;26|) + (LETT #2# + (SPADCALL |ansR| (QREFELT |$| 126)) + |POLYCAT-;factor;SF;26|) + G190 + (COND + ((OR + (ATOM #2#) + (PROGN + (LETT |w| (CAR #2#) |POLYCAT-;factor;SF;26|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #1# + (CONS + (VECTOR + (QVELT |w| 0) + (SPADCALL (QVELT |w| 1) (QREFELT |$| 40)) + (QVELT |w| 2)) + #1#) + |POLYCAT-;factor;SF;26|))) + (LETT #2# (CDR #2#) |POLYCAT-;factor;SF;26|) + (GO G190) + G191 + (EXIT (NREVERSE0 #1#)))) + (QREFELT |$| 130))))) + ((QUOTE T) + (SEQ + (LETT |up| + (SPADCALL |p| (QCDR |v|) (QREFELT |$| 47)) + |POLYCAT-;factor;SF;26|) + (LETT |ansSUP| + (SPADCALL |up| (QREFELT |$| 114)) + |POLYCAT-;factor;SF;26|) + (EXIT + (SPADCALL + (SPADCALL + (SPADCALL |ansSUP| (QREFELT |$| 131)) + (QCDR |v|) + (QREFELT |$| 132)) + (PROGN + (LETT #3# NIL |POLYCAT-;factor;SF;26|) + (SEQ + (LETT |ww| NIL |POLYCAT-;factor;SF;26|) + (LETT #4# + (SPADCALL |ansSUP| (QREFELT |$| 135)) + |POLYCAT-;factor;SF;26|) + G190 + (COND + ((OR + (ATOM #4#) + (PROGN + (LETT |ww| (CAR #4#) |POLYCAT-;factor;SF;26|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #3# + (CONS + (VECTOR + (QVELT |ww| 0) + (SPADCALL + (QVELT |ww| 1) + (QCDR |v|) + (QREFELT |$| 132)) + (QVELT |ww| 2)) + #3#) + |POLYCAT-;factor;SF;26|))) + (LETT #4# (CDR #4#) |POLYCAT-;factor;SF;26|) + (GO G190) + G191 + (EXIT (NREVERSE0 #3#)))) + (QREFELT |$| 130))))))))))) + +(DEFUN |POLYCAT-;conditionP;MU;27| (|mat| |$|) + (PROG (|ll| #1=#:G102087 |z| #2=#:G102088 |ch| |l| #3=#:G102079 + #4=#:G102086 #5=#:G102047 #6=#:G102045 #7=#:G102046 #8=#:G102080 + |vars| |degs| #9=#:G102084 |d| #10=#:G102085 |nd| #11=#:G102074 + #12=#:G102054 |deg1| |redmons| #13=#:G102081 |v| #14=#:G102083 |u| + #15=#:G102082 |llR| |monslist| |ans| #16=#:G102075 #17=#:G102076 + |mons| #18=#:G102077 |m| #19=#:G102078 |i| #20=#:G102070 + #21=#:G102068 #22=#:G102069) + (RETURN + (SEQ + (EXIT + (SEQ + (LETT |ll| + (SPADCALL (SPADCALL |mat| (QREFELT |$| 137)) (QREFELT |$| 92)) + |POLYCAT-;conditionP;MU;27|) + (LETT |llR| + (PROGN (LETT #1# NIL |POLYCAT-;conditionP;MU;27|) + (SEQ + (LETT |z| NIL |POLYCAT-;conditionP;MU;27|) + (LETT #2# (|SPADfirst| |ll|) |POLYCAT-;conditionP;MU;27|) + G190 + (COND + ((OR + (ATOM #2#) + (PROGN + (LETT |z| (CAR #2#) |POLYCAT-;conditionP;MU;27|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #1# (CONS NIL #1#) |POLYCAT-;conditionP;MU;27|))) + (LETT #2# (CDR #2#) |POLYCAT-;conditionP;MU;27|) + (GO G190) + G191 + (EXIT (NREVERSE0 #1#)))) + |POLYCAT-;conditionP;MU;27|) + (LETT |monslist| NIL |POLYCAT-;conditionP;MU;27|) + (LETT |ch| + (SPADCALL (QREFELT |$| 138)) + |POLYCAT-;conditionP;MU;27|) + (SEQ + (LETT |l| NIL |POLYCAT-;conditionP;MU;27|) + (LETT #3# |ll| |POLYCAT-;conditionP;MU;27|) + G190 + (COND + ((OR + (ATOM #3#) + (PROGN + (LETT |l| (CAR #3#) |POLYCAT-;conditionP;MU;27|) + NIL)) + (GO G191))) + (SEQ + (LETT |mons| + (PROGN + (LETT #7# NIL |POLYCAT-;conditionP;MU;27|) + (SEQ + (LETT |u| NIL |POLYCAT-;conditionP;MU;27|) + (LETT #4# |l| |POLYCAT-;conditionP;MU;27|) + G190 + (COND + ((OR + (ATOM #4#) + (PROGN + (LETT |u| (CAR #4#) |POLYCAT-;conditionP;MU;27|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (PROGN + (LETT #5# + (SPADCALL |u| (QREFELT |$| 77)) + |POLYCAT-;conditionP;MU;27|) + (COND + (#7# + (LETT #6# + (SPADCALL #6# #5# (QREFELT |$| 139)) + |POLYCAT-;conditionP;MU;27|)) + ((QUOTE T) + (PROGN + (LETT #6# #5# |POLYCAT-;conditionP;MU;27|) + (LETT #7# + (QUOTE T) + |POLYCAT-;conditionP;MU;27|))))))) + (LETT #4# (CDR #4#) |POLYCAT-;conditionP;MU;27|) + (GO G190) + G191 + (EXIT NIL)) + (COND + (#7# #6#) + ((QUOTE T) (|IdentityError| (QUOTE |setUnion|))))) + |POLYCAT-;conditionP;MU;27|) + (LETT |redmons| NIL |POLYCAT-;conditionP;MU;27|) + (SEQ + (LETT |m| NIL |POLYCAT-;conditionP;MU;27|) + (LETT #8# |mons| |POLYCAT-;conditionP;MU;27|) + G190 + (COND + ((OR + (ATOM #8#) + (PROGN + (LETT |m| (CAR #8#) |POLYCAT-;conditionP;MU;27|) + NIL)) + (GO G191))) + (SEQ + (LETT |vars| + (SPADCALL |m| (QREFELT |$| 31)) + |POLYCAT-;conditionP;MU;27|) + (LETT |degs| + (SPADCALL |m| |vars| (QREFELT |$| 140)) + |POLYCAT-;conditionP;MU;27|) + (LETT |deg1| + (PROGN + (LETT #9# NIL |POLYCAT-;conditionP;MU;27|) + (SEQ + (LETT |d| NIL |POLYCAT-;conditionP;MU;27|) + (LETT #10# |degs| |POLYCAT-;conditionP;MU;27|) + G190 + (COND + ((OR + (ATOM #10#) + (PROGN + (LETT |d| + (CAR #10#) + |POLYCAT-;conditionP;MU;27|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #9# + (CONS + (SEQ + (LETT |nd| + (SPADCALL |d| |ch| (QREFELT |$| 142)) + |POLYCAT-;conditionP;MU;27|) + (EXIT + (COND + ((QEQCAR |nd| 1) + (PROGN + (LETT #11# + (CONS 1 "failed") + |POLYCAT-;conditionP;MU;27|) + (GO #11#))) + ((QUOTE T) + (PROG1 + (LETT #12# + (QCDR |nd|) + |POLYCAT-;conditionP;MU;27|) + (|check-subtype| + (|>=| #12# 0) + (QUOTE (|NonNegativeInteger|)) + #12#)))))) + #9#) + |POLYCAT-;conditionP;MU;27|))) + (LETT #10# (CDR #10#) |POLYCAT-;conditionP;MU;27|) + (GO G190) + G191 + (EXIT (NREVERSE0 #9#)))) + |POLYCAT-;conditionP;MU;27|) + (LETT |redmons| + (CONS + (SPADCALL + (|spadConstant| |$| 33) + |vars| + |deg1| + (QREFELT |$| 54)) + |redmons|) + |POLYCAT-;conditionP;MU;27|) + (EXIT + (LETT |llR| + (PROGN + (LETT #13# NIL |POLYCAT-;conditionP;MU;27|) + (SEQ + (LETT |v| NIL |POLYCAT-;conditionP;MU;27|) + (LETT #14# |llR| |POLYCAT-;conditionP;MU;27|) + (LETT |u| NIL |POLYCAT-;conditionP;MU;27|) + (LETT #15# |l| |POLYCAT-;conditionP;MU;27|) + G190 + (COND + ((OR + (ATOM #15#) + (PROGN + (LETT |u| + (CAR #15#) + |POLYCAT-;conditionP;MU;27|) + NIL) + (ATOM #14#) + (PROGN + (LETT |v| + (CAR #14#) + |POLYCAT-;conditionP;MU;27|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #13# + (CONS + (CONS + (SPADCALL + (SPADCALL + |u| + |vars| + |degs| + (QREFELT |$| 52)) + (QREFELT |$| 143)) + |v|) + #13#) + |POLYCAT-;conditionP;MU;27|))) + (LETT #15# + (PROG1 + (CDR #15#) + (LETT #14# + (CDR #14#) + |POLYCAT-;conditionP;MU;27|)) + |POLYCAT-;conditionP;MU;27|) + (GO G190) + G191 + (EXIT (NREVERSE0 #13#)))) + |POLYCAT-;conditionP;MU;27|))) + (LETT #8# (CDR #8#) |POLYCAT-;conditionP;MU;27|) + (GO G190) + G191 + (EXIT NIL)) + (EXIT + (LETT |monslist| + (CONS |redmons| |monslist|) + |POLYCAT-;conditionP;MU;27|))) + (LETT #3# (CDR #3#) |POLYCAT-;conditionP;MU;27|) + (GO G190) + G191 + (EXIT NIL)) + (LETT |ans| + (SPADCALL + (SPADCALL + (SPADCALL |llR| (QREFELT |$| 89)) + (QREFELT |$| 144)) + (QREFELT |$| 146)) + |POLYCAT-;conditionP;MU;27|) + (EXIT + (COND + ((QEQCAR |ans| 1) (CONS 1 "failed")) + ((QUOTE T) + (SEQ + (LETT |i| 0 |POLYCAT-;conditionP;MU;27|) + (EXIT + (CONS + 0 + (PRIMVEC2ARR + (PROGN + (LETT #16# + (GETREFV (SIZE |monslist|)) + |POLYCAT-;conditionP;MU;27|) + (SEQ + (LETT #17# 0 |POLYCAT-;conditionP;MU;27|) + (LETT |mons| NIL |POLYCAT-;conditionP;MU;27|) + (LETT #18# + |monslist| + |POLYCAT-;conditionP;MU;27|) + G190 + (COND + ((OR + (ATOM #18#) + (PROGN + (LETT |mons| + (CAR #18#) + |POLYCAT-;conditionP;MU;27|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (SETELT + #16# + #17# + (PROGN + (LETT #22# + NIL + |POLYCAT-;conditionP;MU;27|) + (SEQ + (LETT |m| + NIL + |POLYCAT-;conditionP;MU;27|) + (LETT #19# + |mons| + |POLYCAT-;conditionP;MU;27|) + G190 + (COND + ((OR + (ATOM #19#) + (PROGN + (LETT |m| + (CAR #19#) + |POLYCAT-;conditionP;MU;27|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (PROGN + (LETT #20# + (SPADCALL |m| + (SPADCALL + (SPADCALL + (QCDR |ans|) + (LETT |i| + (|+| |i| 1) + |POLYCAT-;conditionP;MU;27|) + (QREFELT |$| 147)) + (QREFELT |$| 40)) + (QREFELT |$| 148)) + |POLYCAT-;conditionP;MU;27|) + (COND + (#22# + (LETT #21# + (SPADCALL #21# #20# + (QREFELT |$| 149)) + |POLYCAT-;conditionP;MU;27|)) + ((QUOTE T) + (PROGN + (LETT #21# #20# + |POLYCAT-;conditionP;MU;27|) + (LETT #22# (QUOTE T) + |POLYCAT-;conditionP;MU;27|))))))) + (LETT #19# (CDR #19#) + |POLYCAT-;conditionP;MU;27|) + (GO G190) + G191 + (EXIT NIL)) + (COND + (#22# #21#) + ((QUOTE T) + (|spadConstant| |$| 21))))))) + (LETT #18# + (PROG1 + (CDR #18#) + (LETT #17# + (QSADD1 #17#) + |POLYCAT-;conditionP;MU;27|)) + |POLYCAT-;conditionP;MU;27|) + (GO G190) + G191 + (EXIT NIL)) + #16#)))))))))) + #11# + (EXIT #11#))))) + +(DEFUN |POLYCAT-;charthRoot;SU;28| (|p| |$|) + (PROG (|vars| |ans| |ch|) + (RETURN + (SEQ + (LETT |vars| + (SPADCALL |p| (QREFELT |$| 31)) |POLYCAT-;charthRoot;SU;28|) + (EXIT + (COND + ((NULL |vars|) + (SEQ + (LETT |ans| + (SPADCALL + (SPADCALL |p| (QREFELT |$| 143)) + (QREFELT |$| 151)) + |POLYCAT-;charthRoot;SU;28|) + (EXIT + (COND + ((QEQCAR |ans| 1) + (CONS 1 "failed")) + ((QUOTE T) + (CONS 0 (SPADCALL (QCDR |ans|) (QREFELT |$| 40)))))))) + ((QUOTE T) + (SEQ + (LETT |ch| + (SPADCALL (QREFELT |$| 138)) + |POLYCAT-;charthRoot;SU;28|) + (EXIT (|POLYCAT-;charthRootlv| |p| |vars| |ch| |$|)))))))))) + +(DEFUN |POLYCAT-;charthRootlv| (|p| |vars| |ch| |$|) + (PROG (|v| |dd| |cp| |d| #1=#:G102109 |ans| |ansx| #2=#:G102116) + (RETURN + (SEQ + (EXIT + (COND + ((NULL |vars|) + (SEQ + (LETT |ans| + (SPADCALL (SPADCALL |p| (QREFELT |$| 143)) (QREFELT |$| 151)) + |POLYCAT-;charthRootlv|) + (EXIT + (COND + ((QEQCAR |ans| 1) (CONS 1 "failed")) + ((QUOTE T) + (CONS 0 (SPADCALL (QCDR |ans|) (QREFELT |$| 40)))))))) + ((QUOTE T) + (SEQ + (LETT |v| (|SPADfirst| |vars|) |POLYCAT-;charthRootlv|) + (LETT |vars| (CDR |vars|) |POLYCAT-;charthRootlv|) + (LETT |d| + (SPADCALL |p| |v| (QREFELT |$| 36)) + |POLYCAT-;charthRootlv|) + (LETT |ans| (|spadConstant| |$| 21) |POLYCAT-;charthRootlv|) + (SEQ G190 + (COND ((NULL (|<| 0 |d|)) (GO G191))) + (SEQ + (LETT |dd| + (SPADCALL |d| |ch| (QREFELT |$| 142)) + |POLYCAT-;charthRootlv|) + (EXIT + (COND + ((QEQCAR |dd| 1) + (PROGN + (LETT #2# + (CONS 1 "failed") + |POLYCAT-;charthRootlv|) + (GO #2#))) + ((QUOTE T) + (SEQ + (LETT |cp| + (SPADCALL |p| |v| |d| (QREFELT |$| 154)) + |POLYCAT-;charthRootlv|) + (LETT |p| + (SPADCALL |p| + (SPADCALL |cp| |v| |d| (QREFELT |$| 37)) + (QREFELT |$| 155)) + |POLYCAT-;charthRootlv|) + (LETT |ansx| + (|POLYCAT-;charthRootlv| |cp| |vars| |ch| |$|) + |POLYCAT-;charthRootlv|) + (EXIT + (COND + ((QEQCAR |ansx| 1) + (PROGN + (LETT #2# + (CONS 1 "failed") + |POLYCAT-;charthRootlv|) + (GO #2#))) + ((QUOTE T) + (SEQ + (LETT |d| + (SPADCALL |p| |v| (QREFELT |$| 36)) + |POLYCAT-;charthRootlv|) + (EXIT + (LETT |ans| + (SPADCALL |ans| + (SPADCALL + (QCDR |ansx|) + |v| + (PROG1 + (LETT #1# + (QCDR |dd|) + |POLYCAT-;charthRootlv|) + (|check-subtype| + (|>=| #1# 0) + (QUOTE (|NonNegativeInteger|)) + #1#)) + (QREFELT |$| 37)) + (QREFELT |$| 149)) + |POLYCAT-;charthRootlv|))))))))))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (LETT |ansx| + (|POLYCAT-;charthRootlv| |p| |vars| |ch| |$|) + |POLYCAT-;charthRootlv|) + (EXIT + (COND + ((QEQCAR |ansx| 1) + (PROGN + (LETT #2# (CONS 1 "failed") |POLYCAT-;charthRootlv|) + (GO #2#))) + ((QUOTE T) + (PROGN + (LETT #2# + (CONS + 0 + (SPADCALL |ans| (QCDR |ansx|) (QREFELT |$| 149))) + |POLYCAT-;charthRootlv|) + (GO #2#))))))))) + #2# + (EXIT #2#))))) + +(DEFUN |POLYCAT-;monicDivide;2SVarSetR;30| (|p1| |p2| |mvar| |$|) + (PROG (|result|) + (RETURN + (SEQ + (LETT |result| + (SPADCALL + (SPADCALL |p1| |mvar| (QREFELT |$| 47)) + (SPADCALL |p2| |mvar| (QREFELT |$| 47)) + (QREFELT |$| 157)) + |POLYCAT-;monicDivide;2SVarSetR;30|) + (EXIT + (CONS + (SPADCALL (QCAR |result|) |mvar| (QREFELT |$| 132)) + (SPADCALL (QCDR |result|) |mvar| (QREFELT |$| 132)))))))) + +(DEFUN |POLYCAT-;squareFree;SF;31| (|p| |$|) + (SPADCALL |p| (QREFELT |$| 160))) + +(DEFUN |POLYCAT-;squareFree;SF;32| (|p| |$|) + (SPADCALL |p| (QREFELT |$| 163))) + +(DEFUN |POLYCAT-;squareFree;SF;33| (|p| |$|) + (SPADCALL |p| (QREFELT |$| 163))) + +(DEFUN |POLYCAT-;squareFreePart;2S;34| (|p| |$|) + (PROG (|s| |f| #1=#:G102132 #2=#:G102130 #3=#:G102128 #4=#:G102129) + (RETURN + (SEQ + (SPADCALL + (SPADCALL + (LETT |s| + (SPADCALL |p| (QREFELT |$| 164)) + |POLYCAT-;squareFreePart;2S;34|) + (QREFELT |$| 165)) + (PROGN + (LETT #4# NIL |POLYCAT-;squareFreePart;2S;34|) + (SEQ + (LETT |f| NIL |POLYCAT-;squareFreePart;2S;34|) + (LETT #1# + (SPADCALL |s| (QREFELT |$| 168)) + |POLYCAT-;squareFreePart;2S;34|) + G190 + (COND + ((OR + (ATOM #1#) + (PROGN + (LETT |f| (CAR #1#) |POLYCAT-;squareFreePart;2S;34|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (PROGN + (LETT #2# (QCAR |f|) |POLYCAT-;squareFreePart;2S;34|) + (COND + (#4# + (LETT #3# + (SPADCALL #3# #2# (QREFELT |$| 148)) + |POLYCAT-;squareFreePart;2S;34|)) + ((QUOTE T) + (PROGN + (LETT #3# #2# |POLYCAT-;squareFreePart;2S;34|) + (LETT #4# + (QUOTE T) + |POLYCAT-;squareFreePart;2S;34|))))))) + (LETT #1# (CDR #1#) |POLYCAT-;squareFreePart;2S;34|) + (GO G190) + G191 + (EXIT NIL)) + (COND + (#4# #3#) + ((QUOTE T) (|spadConstant| |$| 33)))) + (QREFELT |$| 148)))))) + +(DEFUN |POLYCAT-;content;SVarSetS;35| (|p| |v| |$|) + (SPADCALL (SPADCALL |p| |v| (QREFELT |$| 47)) (QREFELT |$| 170))) + +(DEFUN |POLYCAT-;primitivePart;2S;36| (|p| |$|) + (PROG (#1=#:G102135) + (RETURN + (QVELT + (SPADCALL + (PROG2 + (LETT #1# + (SPADCALL |p| (SPADCALL |p| (QREFELT |$| 172)) (QREFELT |$| 173)) + |POLYCAT-;primitivePart;2S;36|) + (QCDR #1#) + (|check-union| (QEQCAR #1# 0) (QREFELT |$| 6) #1#)) + (QREFELT |$| 175)) + 1)))) + +(DEFUN |POLYCAT-;primitivePart;SVarSetS;37| (|p| |v| |$|) + (PROG (#1=#:G102141) + (RETURN + (QVELT + (SPADCALL + (PROG2 + (LETT #1# + (SPADCALL |p| + (SPADCALL |p| |v| (QREFELT |$| 177)) + (QREFELT |$| 178)) + |POLYCAT-;primitivePart;SVarSetS;37|) + (QCDR #1#) + (|check-union| (QEQCAR #1# 0) (QREFELT |$| 6) #1#)) + (QREFELT |$| 175)) 1)))) + +(DEFUN |POLYCAT-;<;2SB;38| (|p| |q| |$|) + (PROG (|dp| |dq|) + (RETURN + (SEQ + (LETT |dp| (SPADCALL |p| (QREFELT |$| 59)) |POLYCAT-;<;2SB;38|) + (LETT |dq| (SPADCALL |q| (QREFELT |$| 59)) |POLYCAT-;<;2SB;38|) + (EXIT + (COND + ((SPADCALL |dp| |dq| (QREFELT |$| 180)) + (SPADCALL + (|spadConstant| |$| 22) + (SPADCALL |q| (QREFELT |$| 38)) + (QREFELT |$| 181))) + ((SPADCALL |dq| |dp| (QREFELT |$| 180)) + (SPADCALL + (SPADCALL |p| (QREFELT |$| 38)) + (|spadConstant| |$| 22) + (QREFELT |$| 181))) + ((QUOTE T) + (SPADCALL + (SPADCALL + (SPADCALL |p| |q| (QREFELT |$| 155)) + (QREFELT |$| 38)) + (|spadConstant| |$| 22) + (QREFELT |$| 181))))))))) + +(DEFUN |POLYCAT-;patternMatch;SP2Pmr;39| (|p| |pat| |l| |$|) + (SPADCALL |p| |pat| |l| (QREFELT |$| 186))) + +(DEFUN |POLYCAT-;patternMatch;SP2Pmr;40| (|p| |pat| |l| |$|) + (SPADCALL |p| |pat| |l| (QREFELT |$| 192))) + +(DEFUN |POLYCAT-;convert;SP;41| (|x| |$|) + (SPADCALL (ELT |$| 195) (ELT |$| 196) |x| (QREFELT |$| 200))) + +(DEFUN |POLYCAT-;convert;SP;42| (|x| |$|) + (SPADCALL (ELT |$| 202) (ELT |$| 203) |x| (QREFELT |$| 207))) + +(DEFUN |POLYCAT-;convert;SIf;43| (|p| |$|) + (SPADCALL (ELT |$| 210) (ELT |$| 211) |p| (QREFELT |$| 215))) + +(DEFUN |PolynomialCategory&| (|#1| |#2| |#3| |#4|) + (PROG (|DV$1| |DV$2| |DV$3| |DV$4| |dv$| |$| |pv$|) + (RETURN + (PROGN + (LETT |DV$1| (|devaluate| |#1|) . #1=(|PolynomialCategory&|)) + (LETT |DV$2| (|devaluate| |#2|) . #1#) + (LETT |DV$3| (|devaluate| |#3|) . #1#) + (LETT |DV$4| (|devaluate| |#4|) . #1#) + (LETT |dv$| + (LIST + (QUOTE |PolynomialCategory&|) |DV$1| |DV$2| |DV$3| |DV$4|) . #1#) + (LETT |$| (GETREFV 225) . #1#) + (QSETREFV |$| 0 |dv$|) + (QSETREFV |$| 3 + (LETT |pv$| + (|buildPredVector| 0 0 + (LIST + (|HasCategory| |#2| + (QUOTE (|PolynomialFactorizationExplicit|))) + (|HasAttribute| |#2| (QUOTE |canonicalUnitNormal|)) + (|HasCategory| |#2| (QUOTE (|GcdDomain|))) + (|HasCategory| |#2| (QUOTE (|CommutativeRing|))) + (|HasCategory| |#4| (QUOTE (|PatternMatchable| (|Float|)))) + (|HasCategory| |#2| (QUOTE (|PatternMatchable| (|Float|)))) + (|HasCategory| |#4| (QUOTE (|PatternMatchable| (|Integer|)))) + (|HasCategory| |#2| (QUOTE (|PatternMatchable| (|Integer|)))) + (|HasCategory| |#4| + (QUOTE (|ConvertibleTo| (|Pattern| (|Float|))))) + (|HasCategory| |#2| + (QUOTE (|ConvertibleTo| (|Pattern| (|Float|))))) + (|HasCategory| |#4| + (QUOTE (|ConvertibleTo| (|Pattern| (|Integer|))))) + (|HasCategory| |#2| + (QUOTE (|ConvertibleTo| (|Pattern| (|Integer|))))) + (|HasCategory| |#4| (QUOTE (|ConvertibleTo| (|InputForm|)))) + (|HasCategory| |#2| (QUOTE (|ConvertibleTo| (|InputForm|)))) + (|HasCategory| |#2| (QUOTE (|OrderedSet|))))) . #1#)) + (|stuffDomainSlots| |$|) + (QSETREFV |$| 6 |#1|) + (QSETREFV |$| 7 |#2|) + (QSETREFV |$| 8 |#3|) + (QSETREFV |$| 9 |#4|) + (COND + ((|testBitVector| |pv$| 4) + (PROGN + (QSETREFV |$| 74 + (CONS + (|dispatchFunction| |POLYCAT-;resultant;2SVarSetS;15|) + |$|)) + (QSETREFV |$| 76 + (CONS + (|dispatchFunction| |POLYCAT-;discriminant;SVarSetS;16|) + |$|))))) + (COND + ((|HasCategory| |#2| (QUOTE (|IntegralDomain|))) + (PROGN + (QSETREFV |$| 95 + (CONS (|dispatchFunction| |POLYCAT-;reducedSystem;MM;20|) |$|)) + (QSETREFV |$| 102 + (CONS + (|dispatchFunction| |POLYCAT-;reducedSystem;MVR;21|) + |$|))))) + (COND + ((|testBitVector| |pv$| 1) + (PROGN + (QSETREFV |$| 105 + (CONS + (|dispatchFunction| |POLYCAT-;gcdPolynomial;3Sup;22|) + |$|)) + (QSETREFV |$| 112 + (CONS + (|dispatchFunction| + |POLYCAT-;solveLinearPolynomialEquation;LSupU;23|) + |$|)) + (QSETREFV |$| 116 + (CONS + (|dispatchFunction| |POLYCAT-;factorPolynomial;SupF;24|) + |$|)) + (QSETREFV |$| 118 + (CONS + (|dispatchFunction| + |POLYCAT-;factorSquareFreePolynomial;SupF;25|) + |$|)) + (QSETREFV |$| 136 + (CONS + (|dispatchFunction| |POLYCAT-;factor;SF;26|) |$|)) + (COND + ((|HasCategory| |#2| (QUOTE (|CharacteristicNonZero|))) + (PROGN + (QSETREFV |$| 150 + (CONS + (|dispatchFunction| |POLYCAT-;conditionP;MU;27|) + |$|)))))))) + (COND + ((|HasCategory| |#2| (QUOTE (|CharacteristicNonZero|))) + (PROGN + (QSETREFV |$| 152 + (CONS + (|dispatchFunction| |POLYCAT-;charthRoot;SU;28|) + |$|))))) + (COND + ((|testBitVector| |pv$| 3) + (PROGN + (COND + ((|HasCategory| |#2| (QUOTE (|EuclideanDomain|))) + (COND + ((|HasCategory| |#2| (QUOTE (|CharacteristicZero|))) + (QSETREFV |$| 161 + (CONS + (|dispatchFunction| |POLYCAT-;squareFree;SF;31|) + |$|))) + ((QUOTE T) + (QSETREFV |$| 161 + (CONS + (|dispatchFunction| |POLYCAT-;squareFree;SF;32|) + |$|))))) + ((QUOTE T) + (QSETREFV |$| 161 + (CONS + (|dispatchFunction| |POLYCAT-;squareFree;SF;33|) |$|)))) + (QSETREFV |$| 169 + (CONS + (|dispatchFunction| |POLYCAT-;squareFreePart;2S;34|) |$|)) + (QSETREFV |$| 171 + (CONS (|dispatchFunction| |POLYCAT-;content;SVarSetS;35|) |$|)) + (QSETREFV |$| 176 + (CONS (|dispatchFunction| |POLYCAT-;primitivePart;2S;36|) |$|)) + (QSETREFV |$| 179 + (CONS + (|dispatchFunction| |POLYCAT-;primitivePart;SVarSetS;37|) |$|))))) + (COND + ((|testBitVector| |pv$| 15) + (PROGN + (QSETREFV |$| 182 + (CONS (|dispatchFunction| |POLYCAT-;<;2SB;38|) |$|)) + (COND + ((|testBitVector| |pv$| 8) + (COND + ((|testBitVector| |pv$| 7) + (QSETREFV |$| 188 + (CONS + (|dispatchFunction| + |POLYCAT-;patternMatch;SP2Pmr;39|) + |$|)))))) + (COND + ((|testBitVector| |pv$| 6) + (COND + ((|testBitVector| |pv$| 5) + (QSETREFV |$| 194 + (CONS + (|dispatchFunction| + |POLYCAT-;patternMatch;SP2Pmr;40|) + |$|))))))))) + (COND + ((|testBitVector| |pv$| 12) + (COND + ((|testBitVector| |pv$| 11) + (QSETREFV |$| 201 + (CONS (|dispatchFunction| |POLYCAT-;convert;SP;41|) |$|)))))) + (COND + ((|testBitVector| |pv$| 10) + (COND + ((|testBitVector| |pv$| 9) + (QSETREFV |$| 208 + (CONS (|dispatchFunction| |POLYCAT-;convert;SP;42|) |$|)))))) + (COND + ((|testBitVector| |pv$| 14) + (COND + ((|testBitVector| |pv$| 13) + (QSETREFV |$| 216 + (CONS + (|dispatchFunction| |POLYCAT-;convert;SIf;43|) + |$|)))))) + |$|)))) + +(MAKEPROP + (QUOTE |PolynomialCategory&|) + (QUOTE |infovec|) + (LIST + (QUOTE + #(NIL NIL NIL NIL NIL NIL + (|local| |#1|) + (|local| |#2|) + (|local| |#3|) + (|local| |#4|) + (|Equation| 6) + (0 . |lhs|) + (|Union| 9 (QUOTE "failed")) + (5 . |retractIfCan|) + (10 . |retract|) + (15 . |rhs|) + (|List| 9) + (|List| |$|) + (20 . |eval|) + (|List| 220) + |POLYCAT-;eval;SLS;1| + (27 . |Zero|) + (31 . |Zero|) + (|Boolean|) + (35 . |=|) + (41 . |leadingMonomial|) + (46 . |reductum|) + |POLYCAT-;monomials;SL;2| + (51 . |monomials|) + (|Union| 17 (QUOTE "failed")) + |POLYCAT-;isPlus;SU;3| + (56 . |variables|) + (61 . |monomial?|) + (66 . |One|) + (70 . |One|) + (|NonNegativeInteger|) + (74 . |degree|) + (80 . |monomial|) + (87 . |leadingCoefficient|) + (92 . |one?|) + (97 . |coerce|) + |POLYCAT-;isTimes;SU;4| + (102 . |mainVariable|) + (|Record| (|:| |var| 9) (|:| |exponent| 35)) + (|Union| 43 (QUOTE "failed")) + |POLYCAT-;isExpt;SU;5| + (|SparseUnivariatePolynomial| |$|) + (107 . |univariate|) + (|SparseUnivariatePolynomial| 6) + (113 . |coefficient|) + |POLYCAT-;coefficient;SVarSetNniS;6| + (|List| 35) + (119 . |coefficient|) + |POLYCAT-;coefficient;SLLS;7| + (126 . |monomial|) + |POLYCAT-;monomial;SLLS;8| + (133 . |coerce|) + |POLYCAT-;retract;SVarSet;9| + |POLYCAT-;retractIfCan;SU;10| + (138 . |degree|) + (143 . |monomial|) + |POLYCAT-;primitiveMonomials;SL;12| + (149 . |ground?|) + (154 . |Zero|) + (158 . |=|) + (164 . |degree|) + (169 . |leadingCoefficient|) + (174 . |totalDegree|) + (179 . |reductum|) + |POLYCAT-;totalDegree;SNni;13| + (184 . |member?|) + (190 . |totalDegree|) + |POLYCAT-;totalDegree;SLNni;14| + (196 . |resultant|) + (202 . |resultant|) + (209 . |discriminant|) + (214 . |discriminant|) + (220 . |primitiveMonomials|) + (|List| 6) + (225 . |concat|) + (230 . |removeDuplicates!|) + (|Vector| 7) + (235 . |new|) + (|Integer|) + (241 . |minIndex|) + (246 . |coefficient|) + (252 . |qsetelt!|) + (|List| 219) + (|Matrix| 7) + (259 . |matrix|) + (|List| 78) + (|Matrix| 6) + (264 . |listOfLists|) + (269 . |vertConcat|) + (|Matrix| |$|) + (275 . |reducedSystem|) + (|Vector| 6) + (280 . |entries|) + (285 . |concat|) + (291 . |concat|) + (|Record| (|:| |mat| 88) (|:| |vec| 81)) + (|Vector| |$|) + (297 . |reducedSystem|) + (|GeneralPolynomialGcdPackage| 8 9 7 6) + (303 . |gcdPolynomial|) + (309 . |gcdPolynomial|) + (|Union| 107 (QUOTE "failed")) + (|List| 48) + (|PolynomialFactorizationByRecursion| 7 8 9 6) + (315 . |solveLinearPolynomialEquationByRecursion|) + (|Union| 111 (QUOTE "failed")) + (|List| 46) + (321 . |solveLinearPolynomialEquation|) + (|Factored| 48) + (327 . |factorByRecursion|) + (|Factored| 46) + (332 . |factorPolynomial|) + (337 . |factorSquareFreeByRecursion|) + (342 . |factorSquareFreePolynomial|) + (|Factored| |$|) + (347 . |factor|) + (|Factored| 7) + (352 . |unit|) + (|Union| (QUOTE "nil") (QUOTE "sqfr") (QUOTE "irred") (QUOTE "prime")) + (|Record| (|:| |flg| 123) (|:| |fctr| 7) (|:| |xpnt| 83)) + (|List| 124) + (357 . |factorList|) + (|Record| (|:| |flg| 123) (|:| |fctr| 6) (|:| |xpnt| 83)) + (|List| 127) + (|Factored| 6) + (362 . |makeFR|) + (368 . |unit|) + (373 . |multivariate|) + (|Record| (|:| |flg| 123) (|:| |fctr| 48) (|:| |xpnt| 83)) + (|List| 133) + (379 . |factorList|) + (384 . |factor|) + (389 . |transpose|) + (394 . |characteristic|) + (398 . |setUnion|) + (404 . |degree|) + (|Union| |$| (QUOTE "failed")) + (410 . |exquo|) + (416 . |ground|) + (421 . |transpose|) + (|Union| 101 (QUOTE "failed")) + (426 . |conditionP|) + (431 . |elt|) + (437 . |*|) + (443 . |+|) + (449 . |conditionP|) + (454 . |charthRoot|) + (459 . |charthRoot|) + (464 . |Zero|) + (468 . |coefficient|) + (475 . |-|) + (|Record| (|:| |quotient| |$|) (|:| |remainder| |$|)) + (481 . |monicDivide|) + |POLYCAT-;monicDivide;2SVarSetR;30| + (|MultivariateSquareFree| 8 9 7 6) + (487 . |squareFree|) + (492 . |squareFree|) + (|PolynomialSquareFree| 9 8 7 6) + (497 . |squareFree|) + (502 . |squareFree|) + (507 . |unit|) + (|Record| (|:| |factor| 6) (|:| |exponent| 83)) + (|List| 166) + (512 . |factors|) + (517 . |squareFreePart|) + (522 . |content|) + (527 . |content|) + (533 . |content|) + (538 . |exquo|) + (|Record| (|:| |unit| |$|) (|:| |canonical| |$|) (|:| |associate| |$|)) + (544 . |unitNormal|) + (549 . |primitivePart|) + (554 . |content|) + (560 . |exquo|) + (566 . |primitivePart|) + (572 . |<|) + (578 . |<|) + (584 . |<|) + (|PatternMatchResult| 83 6) + (|Pattern| 83) + (|PatternMatchPolynomialCategory| 83 8 9 7 6) + (590 . |patternMatch|) + (|PatternMatchResult| 83 |$|) + (597 . |patternMatch|) + (|PatternMatchResult| (|Float|) 6) + (|Pattern| (|Float|)) + (|PatternMatchPolynomialCategory| (|Float|) 8 9 7 6) + (604 . |patternMatch|) + (|PatternMatchResult| (|Float|) |$|) + (611 . |patternMatch|) + (618 . |convert|) + (623 . |convert|) + (|Mapping| 184 9) + (|Mapping| 184 7) + (|PolynomialCategoryLifting| 8 9 7 6 184) + (628 . |map|) + (635 . |convert|) + (640 . |convert|) + (645 . |convert|) + (|Mapping| 190 9) + (|Mapping| 190 7) + (|PolynomialCategoryLifting| 8 9 7 6 190) + (650 . |map|) + (657 . |convert|) + (|InputForm|) + (662 . |convert|) + (667 . |convert|) + (|Mapping| 209 9) + (|Mapping| 209 7) + (|PolynomialCategoryLifting| 8 9 7 6 209) + (672 . |map|) + (679 . |convert|) + (|Record| (|:| |mat| 218) (|:| |vec| (|Vector| 83))) + (|Matrix| 83) + (|List| 7) + (|Equation| |$|) + (|Union| 83 (QUOTE "failed")) + (|Union| 223 (QUOTE "failed")) + (|Fraction| 83) + (|Union| 7 (QUOTE "failed")))) + (QUOTE + #(|totalDegree| 684 |squareFreePart| 695 |squareFree| 700 + |solveLinearPolynomialEquation| 705 |retractIfCan| 711 |retract| 716 + |resultant| 721 |reducedSystem| 728 |primitivePart| 739 + |primitiveMonomials| 750 |patternMatch| 755 |monomials| 769 + |monomial| 774 |monicDivide| 781 |isTimes| 788 |isPlus| 793 + |isExpt| 798 |gcdPolynomial| 803 |factorSquareFreePolynomial| 809 + |factorPolynomial| 814 |factor| 819 |eval| 824 |discriminant| 830 + |convert| 836 |content| 851 |conditionP| 857 |coefficient| 862 + |charthRoot| 876 |<| 881)) + (QUOTE NIL) + (CONS + (|makeByteWordVec2| 1 (QUOTE NIL)) + (CONS + (QUOTE #()) + (CONS + (QUOTE #()) + (|makeByteWordVec2| 216 + (QUOTE + (1 10 6 0 11 1 6 12 0 13 1 6 9 0 14 1 10 6 0 15 3 6 0 0 16 + 17 18 0 6 0 21 0 7 0 22 2 6 23 0 0 24 1 6 0 0 25 1 6 0 0 + 26 1 6 17 0 28 1 6 16 0 31 1 6 23 0 32 0 6 0 33 0 7 0 34 2 + 6 35 0 9 36 3 6 0 0 9 35 37 1 6 7 0 38 1 7 23 0 39 1 6 0 7 + 40 1 6 12 0 42 2 6 46 0 9 47 2 48 6 0 35 49 3 6 0 0 16 51 + 52 3 6 0 0 16 51 54 1 6 0 9 56 1 6 8 0 59 2 6 0 7 8 60 1 6 + 23 0 62 0 48 0 63 2 48 23 0 0 64 1 48 35 0 65 1 48 6 0 66 + 1 6 35 0 67 1 48 0 0 68 2 16 23 9 0 70 2 6 35 0 16 71 2 48 + 6 0 0 73 3 0 0 0 0 9 74 1 48 6 0 75 2 0 0 0 9 76 1 6 17 0 + 77 1 78 0 17 79 1 78 0 0 80 2 81 0 35 7 82 1 81 83 0 84 2 + 6 7 0 8 85 3 81 7 0 83 7 86 1 88 0 87 89 1 91 90 0 92 2 88 + 0 0 0 93 1 0 88 94 95 1 96 78 0 97 2 78 0 0 0 98 2 81 0 0 + 0 99 2 0 100 94 101 102 2 103 48 48 48 104 2 0 46 46 46 + 105 2 108 106 107 48 109 2 0 110 111 46 112 1 108 113 48 + 114 1 0 115 46 116 1 108 113 48 117 1 0 115 46 118 1 7 119 + 0 120 1 121 7 0 122 1 121 125 0 126 2 129 0 6 128 130 1 113 + 48 0 131 2 6 0 46 9 132 1 113 134 0 135 1 0 119 0 136 1 91 + 0 0 137 0 6 35 138 2 78 0 0 0 139 2 6 51 0 16 140 2 83 141 + 0 0 142 1 6 7 0 143 1 88 0 0 144 1 7 145 94 146 2 81 7 0 + 83 147 2 6 0 0 0 148 2 6 0 0 0 149 1 0 145 94 150 1 7 141 + 0 151 1 0 141 0 152 0 8 0 153 3 6 0 0 9 35 154 2 6 0 0 0 + 155 2 48 156 0 0 157 1 159 129 6 160 1 0 119 0 161 1 162 + 129 6 163 1 6 119 0 164 1 129 6 0 165 1 129 167 0 168 1 0 + 0 0 169 1 48 6 0 170 2 0 0 0 9 171 1 6 7 0 172 2 6 141 0 7 + 173 1 6 174 0 175 1 0 0 0 176 2 6 0 0 9 177 2 6 141 0 0 + 178 2 0 0 0 9 179 2 8 23 0 0 180 2 7 23 0 0 181 2 0 23 0 0 + 182 3 185 183 6 184 183 186 3 0 187 0 184 187 188 3 191 189 + 6 190 189 192 3 0 193 0 190 193 194 1 9 184 0 195 1 7 184 + 0 196 3 199 184 197 198 6 200 1 0 184 0 201 1 9 190 0 202 + 1 7 190 0 203 3 206 190 204 205 6 207 1 0 190 0 208 1 9 + 209 0 210 1 7 209 0 211 3 214 209 212 213 6 215 1 0 209 0 + 216 2 0 35 0 16 72 1 0 35 0 69 1 0 0 0 169 1 0 119 0 161 2 + 0 110 111 46 112 1 0 12 0 58 1 0 9 0 57 3 0 0 0 0 9 74 1 0 + 88 94 95 2 0 100 94 101 102 2 0 0 0 9 179 1 0 0 0 176 1 0 + 17 0 61 3 0 187 0 184 187 188 3 0 193 0 190 193 194 1 0 17 + 0 27 3 0 0 0 16 51 55 3 0 156 0 0 9 158 1 0 29 0 41 1 0 29 + 0 30 1 0 44 0 45 2 0 46 46 46 105 1 0 115 46 118 1 0 115 + 46 116 1 0 119 0 136 2 0 0 0 19 20 2 0 0 0 9 76 1 0 209 0 + 216 1 0 184 0 201 1 0 190 0 208 2 0 0 0 9 171 1 0 145 94 + 150 3 0 0 0 16 51 53 3 0 0 0 9 35 50 1 0 141 0 152 2 0 + 23 0 0 182)))))) + (QUOTE |lookupComplete|))) + +@ +\section{package POLYLIFT PolynomialCategoryLifting} +<<package POLYLIFT PolynomialCategoryLifting>>= +)abbrev package POLYLIFT PolynomialCategoryLifting +++ Author: Manuel Bronstein +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ This package provides a very general map function, which +++ given a set S and polynomials over R with maps from the +++ variables into S and the coefficients into S, maps polynomials +++ into S. S is assumed to support \spad{+}, \spad{*} and \spad{**}. + +PolynomialCategoryLifting(E,Vars,R,P,S): Exports == Implementation where + E : OrderedAbelianMonoidSup + Vars: OrderedSet + R : Ring + P : PolynomialCategory(R, E, Vars) + S : SetCategory with + "+" : (%, %) -> % + "*" : (%, %) -> % + "**": (%, NonNegativeInteger) -> % + + Exports ==> with + map: (Vars -> S, R -> S, P) -> S + ++ map(varmap, coefmap, p) takes a + ++ varmap, a mapping from the variables of polynomial p into S, + ++ coefmap, a mapping from coefficients of p into S, and p, and + ++ produces a member of S using the corresponding arithmetic. + ++ in S + + Implementation ==> add + map(fv, fc, p) == + (x1 := mainVariable p) case "failed" => fc leadingCoefficient p + up := univariate(p, x1::Vars) + t := fv(x1::Vars) + ans:= fc 0 + while not ground? up repeat + ans := ans + map(fv,fc, leadingCoefficient up) * t ** (degree up) + up := reductum up + ans + map(fv, fc, leadingCoefficient up) + +@ +\section{category UPOLYC UnivariatePolynomialCategory} +<<category UPOLYC UnivariatePolynomialCategory>>= +)abbrev category UPOLYC UnivariatePolynomialCategory +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: Ring, monomial, coefficient, reductum, differentiate, +++ elt, map, resultant, discriminant +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ The category of univariate polynomials over a ring R. +++ No particular model is assumed - implementations can be either +++ sparse or dense. + +UnivariatePolynomialCategory(R:Ring): Category == + Join(PolynomialCategory(R, NonNegativeInteger, SingletonAsOrderedSet), + Eltable(R, R), Eltable(%, %), DifferentialRing, + DifferentialExtension R) with + vectorise : (%,NonNegativeInteger) -> Vector R + ++ vectorise(p, n) returns \spad{[a0,...,a(n-1)]} where + ++ \spad{p = a0 + a1*x + ... + a(n-1)*x**(n-1)} + higher order terms. + ++ The degree of polynomial p can be different from \spad{n-1}. + makeSUP: % -> SparseUnivariatePolynomial R + ++ makeSUP(p) converts the polynomial p to be of type + ++ SparseUnivariatePolynomial over the same coefficients. + unmakeSUP: SparseUnivariatePolynomial R -> % + ++ unmakeSUP(sup) converts sup of type \spadtype{SparseUnivariatePolynomial(R)} + ++ to be a member of the given type. + ++ Note: converse of makeSUP. + multiplyExponents: (%,NonNegativeInteger) -> % + ++ multiplyExponents(p,n) returns a new polynomial resulting from + ++ multiplying all exponents of the polynomial p by the non negative + ++ integer n. + divideExponents: (%,NonNegativeInteger) -> Union(%,"failed") + ++ divideExponents(p,n) returns a new polynomial resulting from + ++ dividing all exponents of the polynomial p by the non negative + ++ integer n, or "failed" if some exponent is not exactly divisible + ++ by n. + monicDivide: (%,%) -> Record(quotient:%,remainder:%) + ++ monicDivide(p,q) divide the polynomial p by the monic polynomial q, + ++ returning the pair \spad{[quotient, remainder]}. + ++ Error: if q isn't monic. +-- These three are for Karatsuba + karatsubaDivide: (%,NonNegativeInteger) -> Record(quotient:%,remainder:%) + ++ \spad{karatsubaDivide(p,n)} returns the same as \spad{monicDivide(p,monomial(1,n))} + shiftRight: (%,NonNegativeInteger) -> % + ++ \spad{shiftRight(p,n)} returns \spad{monicDivide(p,monomial(1,n)).quotient} + shiftLeft: (%,NonNegativeInteger) -> % + ++ \spad{shiftLeft(p,n)} returns \spad{p * monomial(1,n)} + pseudoRemainder: (%,%) -> % + ++ pseudoRemainder(p,q) = r, for polynomials p and q, returns the remainder when + ++ \spad{p' := p*lc(q)**(deg p - deg q + 1)} + ++ is pseudo right-divided by q, i.e. \spad{p' = s q + r}. + differentiate: (%, R -> R, %) -> % + ++ differentiate(p, d, x') extends the R-derivation d to an + ++ extension D in \spad{R[x]} where Dx is given by x', and returns \spad{Dp}. + if R has StepThrough then StepThrough + if R has CommutativeRing then + discriminant: % -> R + ++ discriminant(p) returns the discriminant of the polynomial p. + resultant: (%,%) -> R + ++ resultant(p,q) returns the resultant of the polynomials p and q. + if R has IntegralDomain then + Eltable(Fraction %, Fraction %) + elt : (Fraction %, Fraction %) -> Fraction % + ++ elt(a,b) evaluates the fraction of univariate polynomials \spad{a} + ++ with the distinguished variable replaced by b. + order: (%, %) -> NonNegativeInteger + ++ order(p, q) returns the largest n such that \spad{q**n} divides polynomial p + ++ i.e. the order of \spad{p(x)} at \spad{q(x)=0}. + subResultantGcd: (%,%) -> % + ++ subResultantGcd(p,q) computes the gcd of the polynomials p and q + ++ using the SubResultant GCD algorithm. + composite: (%, %) -> Union(%, "failed") + ++ composite(p, q) returns h if \spad{p = h(q)}, and "failed" no such h exists. + composite: (Fraction %, %) -> Union(Fraction %, "failed") + ++ composite(f, q) returns h if f = h(q), and "failed" is no such h exists. + pseudoQuotient: (%,%) -> % + ++ pseudoQuotient(p,q) returns r, the quotient when + ++ \spad{p' := p*lc(q)**(deg p - deg q + 1)} + ++ is pseudo right-divided by q, i.e. \spad{p' = s q + r}. + pseudoDivide: (%, %) -> Record(coef:R, quotient: %, remainder:%) + ++ pseudoDivide(p,q) returns \spad{[c, q, r]}, when + ++ \spad{p' := p*lc(q)**(deg p - deg q + 1) = c * p} + ++ is pseudo right-divided by q, i.e. \spad{p' = s q + r}. + if R has GcdDomain then + separate: (%, %) -> Record(primePart:%, commonPart: %) + ++ separate(p, q) returns \spad{[a, b]} such that polynomial \spad{p = a b} and + ++ \spad{a} is relatively prime to q. + if R has Field then + EuclideanDomain + additiveValuation + ++ euclideanSize(a*b) = euclideanSize(a) + euclideanSize(b) + elt : (Fraction %, R) -> R + ++ elt(a,r) evaluates the fraction of univariate polynomials \spad{a} + ++ with the distinguished variable replaced by the constant r. + if R has Algebra Fraction Integer then + integrate: % -> % + ++ integrate(p) integrates the univariate polynomial p with respect + ++ to its distinguished variable. + add + pp,qq: SparseUnivariatePolynomial % + variables(p) == + zero? p or zero?(degree p) => [] + [create()] + degree(p:%,v:SingletonAsOrderedSet) == degree p + totalDegree(p:%,lv:List SingletonAsOrderedSet) == + empty? lv => 0 + totalDegree p + degree(p:%,lv:List SingletonAsOrderedSet) == + empty? lv => [] + [degree p] + eval(p:%,lv: List SingletonAsOrderedSet,lq: List %):% == + empty? lv => p + not empty? rest lv => error "can only eval a univariate polynomial once" + eval(p,first lv,first lq)$% + eval(p:%,v:SingletonAsOrderedSet,q:%):% == p(q) + eval(p:%,lv: List SingletonAsOrderedSet,lr: List R):% == + empty? lv => p + not empty? rest lv => error "can only eval a univariate polynomial once" + eval(p,first lv,first lr)$% + eval(p:%,v:SingletonAsOrderedSet,r:R):% == p(r)::% + eval(p:%,le:List Equation %):% == + empty? le => p + not empty? rest le => error "can only eval a univariate polynomial once" + mainVariable(lhs first le) case "failed" => p + p(rhs first le) + mainVariable(p:%) == + zero? degree p => "failed" + create()$SingletonAsOrderedSet + minimumDegree(p:%,v:SingletonAsOrderedSet) == minimumDegree p + minimumDegree(p:%,lv:List SingletonAsOrderedSet) == + empty? lv => [] + [minimumDegree p] + monomial(p:%,v:SingletonAsOrderedSet,n:NonNegativeInteger) == + mapExponents(#1+n,p) + coerce(v:SingletonAsOrderedSet):% == monomial(1,1) + makeSUP p == + zero? p => 0 + monomial(leadingCoefficient p,degree p) + makeSUP reductum p + unmakeSUP sp == + zero? sp => 0 + monomial(leadingCoefficient sp,degree sp) + unmakeSUP reductum sp + karatsubaDivide(p:%,n:NonNegativeInteger) == monicDivide(p,monomial(1,n)) + shiftRight(p:%,n:NonNegativeInteger) == monicDivide(p,monomial(1,n)).quotient + shiftLeft(p:%,n:NonNegativeInteger) == p * monomial(1,n) + if R has PolynomialFactorizationExplicit then + PFBRU ==>PolynomialFactorizationByRecursionUnivariate(R,%) + pp,qq:SparseUnivariatePolynomial % + lpp:List SparseUnivariatePolynomial % + SupR ==> SparseUnivariatePolynomial R + sp:SupR + + solveLinearPolynomialEquation(lpp,pp) == + solveLinearPolynomialEquationByRecursion(lpp,pp)$PFBRU + factorPolynomial(pp) == + factorByRecursion(pp)$PFBRU + factorSquareFreePolynomial(pp) == + factorSquareFreeByRecursion(pp)$PFBRU + import FactoredFunctions2(SupR,S) + factor p == + zero? degree p => + ansR:=factor leadingCoefficient p + makeFR(unit(ansR)::%, + [[w.flg,w.fctr::%,w.xpnt] for w in factorList ansR]) + map(unmakeSUP,factorPolynomial(makeSUP p)$R) + + vectorise(p, n) == + m := minIndex(v := new(n, 0)$Vector(R)) + for i in minIndex v .. maxIndex v repeat + qsetelt_!(v, i, coefficient(p, (i - m)::NonNegativeInteger)) + v + retract(p:%):R == + zero? p => 0 + zero? degree p => leadingCoefficient p + error "Polynomial is not of degree 0" + retractIfCan(p:%):Union(R, "failed") == + zero? p => 0 + zero? degree p => leadingCoefficient p + "failed" + + if R has StepThrough then + init() == init()$R::% + nextItemInner: % -> Union(%,"failed") + nextItemInner(n) == + zero? n => nextItem(0$R)::R::% -- assumed not to fail + zero? degree n => + nn:=nextItem leadingCoefficient n + nn case "failed" => "failed" + nn::R::% + n1:=reductum n + n2:=nextItemInner n1 -- try stepping the reductum + n2 case % => monomial(leadingCoefficient n,degree n) + n2 + 1+degree n1 < degree n => -- there was a hole between lt n and n1 + monomial(leadingCoefficient n,degree n)+ + monomial(nextItem(init()$R)::R,1+degree n1) + n3:=nextItem leadingCoefficient n + n3 case "failed" => "failed" + monomial(n3,degree n) + nextItem(n) == + n1:=nextItemInner n + n1 case "failed" => monomial(nextItem(init()$R)::R,1+degree(n)) + n1 + + if R has GcdDomain then + + content(p:%,v:SingletonAsOrderedSet) == content(p)::% + + primeFactor: (%, %) -> % + + primeFactor(p, q) == + (p1 := (p exquo gcd(p, q))::%) = p => p + primeFactor(p1, q) + + separate(p, q) == + a := primeFactor(p, q) + [a, (p exquo a)::%] + + if R has CommutativeRing then + differentiate(x:%, deriv:R -> R, x':%) == + d:% := 0 + while (dg := degree x) > 0 repeat + lc := leadingCoefficient x + d := d + x' * monomial(dg * lc, (dg - 1)::NonNegativeInteger) + + monomial(deriv lc, dg) + x := reductum x + d + deriv(leadingCoefficient x)::% + else + ncdiff: (NonNegativeInteger, %) -> % + -- computes d(x**n) given dx = x', non-commutative case + ncdiff(n, x') == + zero? n => 0 + zero?(n1 := (n - 1)::NonNegativeInteger) => x' + x' * monomial(1, n1) + monomial(1, 1) * ncdiff(n1, x') + + differentiate(x:%, deriv:R -> R, x':%) == + d:% := 0 + while (dg := degree x) > 0 repeat + lc := leadingCoefficient x + d := d + monomial(deriv lc, dg) + lc * ncdiff(dg, x') + x := reductum x + d + deriv(leadingCoefficient x)::% + differentiate(x:%, deriv:R -> R) == differentiate(x, deriv, 1$%)$% + differentiate(x:%) == + d:% := 0 + while (dg := degree x) > 0 repeat + d := d + monomial(dg * leadingCoefficient x, (dg - 1)::NonNegativeInteger) + x := reductum x + d + differentiate(x:%,v:SingletonAsOrderedSet) == differentiate x + if R has IntegralDomain then + elt(g:Fraction %, f:Fraction %) == ((numer g) f) / ((denom g) f) + + pseudoQuotient(p, q) == + (n := degree(p)::Integer - degree q + 1) < 1 => 0 + ((leadingCoefficient(q)**(n::NonNegativeInteger) * p + - pseudoRemainder(p, q)) exquo q)::% + + pseudoDivide(p, q) == + (n := degree(p)::Integer - degree q + 1) < 1 => [1, 0, p] + prem := pseudoRemainder(p, q) + lc := leadingCoefficient(q)**(n::NonNegativeInteger) + [lc,((lc*p - prem) exquo q)::%, prem] + + composite(f:Fraction %, q:%) == + (n := composite(numer f, q)) case "failed" => "failed" + (d := composite(denom f, q)) case "failed" => "failed" + n::% / d::% + + composite(p:%, q:%) == + ground? p => p + cqr := pseudoDivide(p, q) + ground?(cqr.remainder) and + ((v := cqr.remainder exquo cqr.coef) case %) and + ((u := composite(cqr.quotient, q)) case %) and + ((w := (u::%) exquo cqr.coef) case %) => + v::% + monomial(1, 1) * w::% + "failed" + + elt(p:%, f:Fraction %) == + zero? p => 0 + ans:Fraction(%) := (leadingCoefficient p)::%::Fraction(%) + n := degree p + while not zero?(p:=reductum p) repeat + ans := ans * f ** (n - (n := degree p))::NonNegativeInteger + + (leadingCoefficient p)::%::Fraction(%) + zero? n => ans + ans * f ** n + + order(p, q) == + zero? p => error "order: arguments must be nonzero" + degree(q) < 1 => error "order: place must be non-trivial" + ans:NonNegativeInteger := 0 + repeat + (u := p exquo q) case "failed" => return ans + p := u::% + ans := ans + 1 + + if R has GcdDomain then + squareFree(p:%) == + squareFree(p)$UnivariatePolynomialSquareFree(R, %) + + squareFreePart(p:%) == + squareFreePart(p)$UnivariatePolynomialSquareFree(R, %) + + if R has PolynomialFactorizationExplicit then + + gcdPolynomial(pp,qq) == + zero? pp => unitCanonical qq -- subResultantGcd can't handle 0 + zero? qq => unitCanonical pp + unitCanonical(gcd(content (pp),content(qq))* + primitivePart + subResultantGcd(primitivePart pp,primitivePart qq)) + + squareFreePolynomial pp == + squareFree(pp)$UnivariatePolynomialSquareFree(%, + SparseUnivariatePolynomial %) + + if R has Field then + elt(f:Fraction %, r:R) == ((numer f) r) / ((denom f) r) + + euclideanSize x == + zero? x => + error "euclideanSize called on 0 in Univariate Polynomial" + degree x + divide(x,y) == + zero? y => error "division by 0 in Univariate Polynomials" + quot:=0 + lc := inv leadingCoefficient y + while not zero?(x) and (degree x >= degree y) repeat + f:=lc*leadingCoefficient x + n:=(degree x - degree y)::NonNegativeInteger + quot:=quot+monomial(f,n) + x:=x-monomial(f,n)*y + [quot,x] + if R has Algebra Fraction Integer then + integrate p == + ans:% := 0 + while p ^= 0 repeat + l := leadingCoefficient p + d := 1 + degree p + ans := ans + inv(d::Fraction(Integer)) * monomial(l, d) + p := reductum p + ans + +@ +\section{UPOLYC.lsp BOOTSTRAP} +{\bf UPOLYC} depends on itself. We need to break this cycle to build +the algebra. So we keep a cached copy of the translated {\bf UPOLYC} +category which we can write into the {\bf MID} directory. We compile +the lisp code and copy the {\bf UPOLYC.o} file to the {\bf OUT} directory. +This is eventually forcibly replaced by a recompiled version. + +Note that this code is not included in the generated catdef.spad file. + +<<UPOLYC.lsp BOOTSTRAP>>= + +(|/VERSIONCHECK| 2) + +(SETQ |UnivariatePolynomialCategory;CAT| (QUOTE NIL)) + +(SETQ |UnivariatePolynomialCategory;AL| (QUOTE NIL)) + +(DEFUN |UnivariatePolynomialCategory| (#1=#:G103214) + (LET (#2=#:G103215) + (COND + ((SETQ #2# (|assoc| (|devaluate| #1#) |UnivariatePolynomialCategory;AL|)) + (CDR #2#)) + (T + (SETQ |UnivariatePolynomialCategory;AL| + (|cons5| + (CONS + (|devaluate| #1#) + (SETQ #2# (|UnivariatePolynomialCategory;| #1#))) + |UnivariatePolynomialCategory;AL|)) + #2#)))) + +(DEFUN |UnivariatePolynomialCategory;| (|t#1|) + (PROG (#1=#:G103213) + (RETURN + (PROG1 + (LETT #1# + (|sublisV| + (PAIR (QUOTE (|t#1|)) (LIST (|devaluate| |t#1|))) + (|sublisV| + (PAIR + (QUOTE (#2=#:G103211 #3=#:G103212)) + (LIST + (QUOTE (|NonNegativeInteger|)) + (QUOTE (|SingletonAsOrderedSet|)))) + (COND + (|UnivariatePolynomialCategory;CAT|) + ((QUOTE T) + (LETT |UnivariatePolynomialCategory;CAT| + (|Join| + (|PolynomialCategory| + (QUOTE |t#1|) (QUOTE #2#) (QUOTE #3#)) + (|Eltable| (QUOTE |t#1|) (QUOTE |t#1|)) + (|Eltable| (QUOTE |$|) (QUOTE |$|)) + (|DifferentialRing|) + (|DifferentialExtension| (QUOTE |t#1|)) + (|mkCategory| + (QUOTE |domain|) + (QUOTE ( + ((|vectorise| + ((|Vector| |t#1|) |$| (|NonNegativeInteger|))) T) + ((|makeSUP| + ((|SparseUnivariatePolynomial| |t#1|) |$|)) T) + ((|unmakeSUP| + (|$| (|SparseUnivariatePolynomial| |t#1|))) T) + ((|multiplyExponents| + (|$| |$| (|NonNegativeInteger|))) T) + ((|divideExponents| + ((|Union| |$| "failed") + |$| + (|NonNegativeInteger|))) T) + ((|monicDivide| + ((|Record| + (|:| |quotient| |$|) + (|:| |remainder| |$|)) + |$| + |$|)) T) + ((|karatsubaDivide| + ((|Record| + (|:| |quotient| |$|) + (|:| |remainder| |$|)) + |$| + (|NonNegativeInteger|))) T) + ((|shiftRight| (|$| |$| (|NonNegativeInteger|))) T) + ((|shiftLeft| (|$| |$| (|NonNegativeInteger|))) T) + ((|pseudoRemainder| (|$| |$| |$|)) T) + ((|differentiate| + (|$| |$| (|Mapping| |t#1| |t#1|) |$|)) T) + ((|discriminant| (|t#1| |$|)) + (|has| |t#1| (|CommutativeRing|))) + ((|resultant| (|t#1| |$| |$|)) + (|has| |t#1| (|CommutativeRing|))) + ((|elt| + ((|Fraction| |$|) + (|Fraction| |$|) + (|Fraction| |$|))) + (|has| |t#1| (|IntegralDomain|))) + ((|order| ((|NonNegativeInteger|) |$| |$|)) + (|has| |t#1| (|IntegralDomain|))) + ((|subResultantGcd| (|$| |$| |$|)) + (|has| |t#1| (|IntegralDomain|))) + ((|composite| ((|Union| |$| "failed") |$| |$|)) + (|has| |t#1| (|IntegralDomain|))) + ((|composite| + ((|Union| (|Fraction| |$|) "failed") + (|Fraction| |$|) + |$|)) + (|has| |t#1| (|IntegralDomain|))) + ((|pseudoQuotient| (|$| |$| |$|)) + (|has| |t#1| (|IntegralDomain|))) + ((|pseudoDivide| + ((|Record| + (|:| |coef| |t#1|) + (|:| |quotient| |$|) + (|:| |remainder| |$|)) + |$| + |$|)) + (|has| |t#1| (|IntegralDomain|))) + ((|separate| + ((|Record| + (|:| |primePart| |$|) + (|:| |commonPart| |$|)) + |$| + |$|)) + (|has| |t#1| (|GcdDomain|))) + ((|elt| (|t#1| (|Fraction| |$|) |t#1|)) + (|has| |t#1| (|Field|))) + ((|integrate| (|$| |$|)) + (|has| |t#1| + (|Algebra| (|Fraction| (|Integer|))))))) + (QUOTE ( + ((|StepThrough|) (|has| |t#1| (|StepThrough|))) + ((|Eltable| + (|Fraction| |$|) + (|Fraction| |$|)) + (|has| |t#1| (|IntegralDomain|))) + ((|EuclideanDomain|) (|has| |t#1| (|Field|))) + (|additiveValuation| (|has| |t#1| (|Field|))))) + (QUOTE ( + (|Fraction| |$|) + (|NonNegativeInteger|) + (|SparseUnivariatePolynomial| |t#1|) + (|Vector| |t#1|))) + NIL)) + . #4=(|UnivariatePolynomialCategory|)))))) + . #4#) + (SETELT #1# 0 + (LIST + (QUOTE |UnivariatePolynomialCategory|) + (|devaluate| |t#1|))))))) + +@ +\section{UPOLYC-.lsp BOOTSTRAP} +{\bf UPOLYC-} depends on {\bf UPOLYC}. We need to break this cycle to build +the algebra. So we keep a cached copy of the translated {\bf UPOLYC-} +category which we can write into the {\bf MID} directory. We compile +the lisp code and copy the {\bf UPOLYC-.o} file to the {\bf OUT} directory. +This is eventually forcibly replaced by a recompiled version. + +Note that this code is not included in the generated catdef.spad file. + +<<UPOLYC-.lsp BOOTSTRAP>>= + +(|/VERSIONCHECK| 2) + +(DEFUN |UPOLYC-;variables;SL;1| (|p| |$|) + (COND + ((OR + (SPADCALL |p| (QREFELT |$| 9)) + (ZEROP (SPADCALL |p| (QREFELT |$| 11)))) + NIL) + ((QUOTE T) (LIST (SPADCALL (QREFELT |$| 13)))))) + +(DEFUN |UPOLYC-;degree;SSaosNni;2| (|p| |v| |$|) + (SPADCALL |p| (QREFELT |$| 11))) + +(DEFUN |UPOLYC-;totalDegree;SLNni;3| (|p| |lv| |$|) + (COND ((NULL |lv|) 0) ((QUOTE T) (SPADCALL |p| (QREFELT |$| 17))))) + +(DEFUN |UPOLYC-;degree;SLL;4| (|p| |lv| |$|) + (COND ((NULL |lv|) NIL) ((QUOTE T) (LIST (SPADCALL |p| (QREFELT |$| 11)))))) + +(DEFUN |UPOLYC-;eval;SLLS;5| (|p| |lv| |lq| |$|) + (COND + ((NULL |lv|) |p|) + ((NULL (NULL (CDR |lv|))) + (|error| "can only eval a univariate polynomial once")) + ((QUOTE T) + (SPADCALL |p| (|SPADfirst| |lv|) (|SPADfirst| |lq|) (QREFELT |$| 21))))) + +(DEFUN |UPOLYC-;eval;SSaos2S;6| (|p| |v| |q| |$|) + (SPADCALL |p| |q| (QREFELT |$| 24))) + +(DEFUN |UPOLYC-;eval;SLLS;7| (|p| |lv| |lr| |$|) + (COND + ((NULL |lv|) |p|) + ((NULL (NULL (CDR |lv|))) + (|error| "can only eval a univariate polynomial once")) + ((QUOTE T) + (SPADCALL |p| (|SPADfirst| |lv|) (|SPADfirst| |lr|) (QREFELT |$| 26))))) + +(DEFUN |UPOLYC-;eval;SSaosRS;8| (|p| |v| |r| |$|) + (SPADCALL (SPADCALL |p| |r| (QREFELT |$| 29)) (QREFELT |$| 30))) + +(DEFUN |UPOLYC-;eval;SLS;9| (|p| |le| |$|) + (COND + ((NULL |le|) |p|) + ((NULL (NULL (CDR |le|))) + (|error| "can only eval a univariate polynomial once")) + ((QUOTE T) + (COND + ((QEQCAR + (SPADCALL + (SPADCALL (|SPADfirst| |le|) (QREFELT |$| 33)) + (QREFELT |$| 35)) + 1) + |p|) + ((QUOTE T) + (SPADCALL |p| + (SPADCALL (|SPADfirst| |le|) (QREFELT |$| 36)) + (QREFELT |$| 24))))))) + +(DEFUN |UPOLYC-;mainVariable;SU;10| (|p| |$|) + (COND + ((ZEROP (SPADCALL |p| (QREFELT |$| 11))) (CONS 1 "failed")) + ((QUOTE T) (CONS 0 (SPADCALL (QREFELT |$| 13)))))) + +(DEFUN |UPOLYC-;minimumDegree;SSaosNni;11| (|p| |v| |$|) + (SPADCALL |p| (QREFELT |$| 40))) + +(DEFUN |UPOLYC-;minimumDegree;SLL;12| (|p| |lv| |$|) + (COND ((NULL |lv|) NIL) ((QUOTE T) (LIST (SPADCALL |p| (QREFELT |$| 40)))))) + +(DEFUN |UPOLYC-;monomial;SSaosNniS;13| (|p| |v| |n| |$|) + (SPADCALL + (CONS (FUNCTION |UPOLYC-;monomial;SSaosNniS;13!0|) (VECTOR |$| |n|)) + |p| + (QREFELT |$| 45))) + +(DEFUN |UPOLYC-;monomial;SSaosNniS;13!0| (|#1| |$$|) + (SPADCALL |#1| (QREFELT |$$| 1) (QREFELT (QREFELT |$$| 0) 43))) + +(DEFUN |UPOLYC-;coerce;SaosS;14| (|v| |$|) + (SPADCALL (|spadConstant| |$| 48) 1 (QREFELT |$| 49))) + +(DEFUN |UPOLYC-;makeSUP;SSup;15| (|p| |$|) + (COND + ((SPADCALL |p| (QREFELT |$| 9)) (|spadConstant| |$| 52)) + ((QUOTE T) + (SPADCALL + (SPADCALL + (SPADCALL |p| (QREFELT |$| 53)) + (SPADCALL |p| (QREFELT |$| 11)) + (QREFELT |$| 54)) + (SPADCALL + (SPADCALL |p| (QREFELT |$| 55)) + (QREFELT |$| 56)) + (QREFELT |$| 57))))) + +(DEFUN |UPOLYC-;unmakeSUP;SupS;16| (|sp| |$|) + (COND + ((SPADCALL |sp| (QREFELT |$| 59)) (|spadConstant| |$| 60)) + ((QUOTE T) + (SPADCALL + (SPADCALL + (SPADCALL |sp| (QREFELT |$| 61)) + (SPADCALL |sp| (QREFELT |$| 62)) + (QREFELT |$| 49)) + (SPADCALL (SPADCALL |sp| (QREFELT |$| 63)) (QREFELT |$| 64)) + (QREFELT |$| 65))))) + +(DEFUN |UPOLYC-;karatsubaDivide;SNniR;17| (|p| |n| |$|) + (SPADCALL |p| + (SPADCALL (|spadConstant| |$| 48) |n| (QREFELT |$| 49)) + (QREFELT |$| 68))) + +(DEFUN |UPOLYC-;shiftRight;SNniS;18| (|p| |n| |$|) + (QCAR + (SPADCALL |p| + (SPADCALL (|spadConstant| |$| 48) |n| (QREFELT |$| 49)) + (QREFELT |$| 68)))) + +(DEFUN |UPOLYC-;shiftLeft;SNniS;19| (|p| |n| |$|) + (SPADCALL |p| + (SPADCALL (|spadConstant| |$| 48) |n| (QREFELT |$| 49)) (QREFELT |$| 71))) + +(DEFUN |UPOLYC-;solveLinearPolynomialEquation;LSupU;20| (|lpp| |pp| |$|) + (SPADCALL |lpp| |pp| (QREFELT |$| 77))) + +(DEFUN |UPOLYC-;factorPolynomial;SupF;21| (|pp| |$|) + (SPADCALL |pp| (QREFELT |$| 83))) + +(DEFUN |UPOLYC-;factorSquareFreePolynomial;SupF;22| (|pp| |$|) + (SPADCALL |pp| (QREFELT |$| 86))) + +(DEFUN |UPOLYC-;factor;SF;23| (|p| |$|) + (PROG (|ansR| #1=#:G103310 |w| #2=#:G103311) + (RETURN + (SEQ + (COND + ((ZEROP (SPADCALL |p| (QREFELT |$| 11))) + (SEQ + (LETT |ansR| + (SPADCALL + (SPADCALL |p| (QREFELT |$| 53)) + (QREFELT |$| 89)) + |UPOLYC-;factor;SF;23|) + (EXIT + (SPADCALL + (SPADCALL + (SPADCALL |ansR| (QREFELT |$| 91)) + (QREFELT |$| 30)) + (PROGN + (LETT #1# NIL |UPOLYC-;factor;SF;23|) + (SEQ + (LETT |w| NIL |UPOLYC-;factor;SF;23|) + (LETT #2# + (SPADCALL |ansR| (QREFELT |$| 95)) + |UPOLYC-;factor;SF;23|) + G190 + (COND + ((OR + (ATOM #2#) + (PROGN + (LETT |w| (CAR #2#) |UPOLYC-;factor;SF;23|) + NIL)) + (GO G191))) + (SEQ + (EXIT + (LETT #1# + (CONS + (VECTOR + (QVELT |w| 0) + (SPADCALL (QVELT |w| 1) (QREFELT |$| 30)) + (QVELT |w| 2)) + #1#) + |UPOLYC-;factor;SF;23|))) + (LETT #2# (CDR #2#) |UPOLYC-;factor;SF;23|) + (GO G190) + G191 + (EXIT (NREVERSE0 #1#)))) + (QREFELT |$| 99))))) + ((QUOTE T) + (SPADCALL + (ELT |$| 64) + (SPADCALL (SPADCALL |p| (QREFELT |$| 56)) (QREFELT |$| 100)) + (QREFELT |$| 104)))))))) + +(DEFUN |UPOLYC-;vectorise;SNniV;24| (|p| |n| |$|) + (PROG (|v| |m| |i| #1=#:G103316 #2=#:G103312) + (RETURN + (SEQ + (LETT |m| + (SPADCALL + (LETT |v| + (SPADCALL |n| (|spadConstant| |$| 106) (QREFELT |$| 108)) + |UPOLYC-;vectorise;SNniV;24|) + (QREFELT |$| 110)) + |UPOLYC-;vectorise;SNniV;24|) + (SEQ + (LETT |i| + (SPADCALL |v| (QREFELT |$| 110)) + |UPOLYC-;vectorise;SNniV;24|) + (LETT #1# (QVSIZE |v|) |UPOLYC-;vectorise;SNniV;24|) + G190 + (COND ((|>| |i| #1#) (GO G191))) + (SEQ + (EXIT + (SPADCALL |v| |i| + (SPADCALL |p| + (PROG1 + (LETT #2# (|-| |i| |m|) |UPOLYC-;vectorise;SNniV;24|) + (|check-subtype| + (|>=| #2# 0) + (QUOTE (|NonNegativeInteger|)) + #2#)) + (QREFELT |$| 111)) + (QREFELT |$| 112)))) + (LETT |i| (|+| |i| 1) |UPOLYC-;vectorise;SNniV;24|) + (GO G190) + G191 + (EXIT NIL)) + (EXIT |v|))))) + +(DEFUN |UPOLYC-;retract;SR;25| (|p| |$|) + (COND + ((SPADCALL |p| (QREFELT |$| 9)) (|spadConstant| |$| 106)) + ((ZEROP (SPADCALL |p| (QREFELT |$| 11))) (SPADCALL |p| (QREFELT |$| 53))) + ((QUOTE T) (|error| "Polynomial is not of degree 0")))) + +(DEFUN |UPOLYC-;retractIfCan;SU;26| (|p| |$|) + (COND + ((SPADCALL |p| (QREFELT |$| 9)) (CONS 0 (|spadConstant| |$| 106))) + ((ZEROP (SPADCALL |p| (QREFELT |$| 11))) + (CONS 0 (SPADCALL |p| (QREFELT |$| 53)))) + ((QUOTE T) (CONS 1 "failed")))) + +(DEFUN |UPOLYC-;init;S;27| (|$|) + (SPADCALL (|spadConstant| |$| 117) (QREFELT |$| 30))) + +(DEFUN |UPOLYC-;nextItemInner| (|n| |$|) + (PROG (|nn| |n1| |n2| #1=#:G103337 |n3|) + (RETURN + (SEQ + (COND + ((SPADCALL |n| (QREFELT |$| 9)) + (CONS + 0 + (SPADCALL + (PROG2 + (LETT #1# + (SPADCALL (|spadConstant| |$| 106) (QREFELT |$| 120)) + |UPOLYC-;nextItemInner|) + (QCDR #1#) + (|check-union| (QEQCAR #1# 0) (QREFELT |$| 7) #1#)) + (QREFELT |$| 30)))) + ((ZEROP (SPADCALL |n| (QREFELT |$| 11))) + (SEQ + (LETT |nn| + (SPADCALL (SPADCALL |n| (QREFELT |$| 53)) (QREFELT |$| 120)) + |UPOLYC-;nextItemInner|) + (EXIT + (COND + ((QEQCAR |nn| 1) (CONS 1 "failed")) + ((QUOTE T) + (CONS 0 (SPADCALL (QCDR |nn|) (QREFELT |$| 30)))))))) + ((QUOTE T) + (SEQ + (LETT |n1| + (SPADCALL |n| (QREFELT |$| 55)) + |UPOLYC-;nextItemInner|) + (LETT |n2| + (|UPOLYC-;nextItemInner| |n1| |$|) + |UPOLYC-;nextItemInner|) + (EXIT + (COND + ((QEQCAR |n2| 0) + (CONS + 0 + (SPADCALL + (SPADCALL + (SPADCALL |n| (QREFELT |$| 53)) + (SPADCALL |n| (QREFELT |$| 11)) + (QREFELT |$| 49)) + (QCDR |n2|) + (QREFELT |$| 65)))) + ((|<| + (|+| 1 (SPADCALL |n1| (QREFELT |$| 11))) + (SPADCALL |n| (QREFELT |$| 11))) + (CONS + 0 + (SPADCALL + (SPADCALL + (SPADCALL |n| (QREFELT |$| 53)) + (SPADCALL |n| (QREFELT |$| 11)) + (QREFELT |$| 49)) + (SPADCALL + (PROG2 + (LETT #1# + (SPADCALL + (|spadConstant| |$| 117) + (QREFELT |$| 120)) + |UPOLYC-;nextItemInner|) + (QCDR #1#) + (|check-union| (QEQCAR #1# 0) (QREFELT |$| 7) #1#)) + (|+| 1 (SPADCALL |n1| (QREFELT |$| 11))) + (QREFELT |$| 49)) + (QREFELT |$| 65)))) + ((QUOTE T) + (SEQ + (LETT |n3| + (SPADCALL + (SPADCALL |n| (QREFELT |$| 53)) + (QREFELT |$| 120)) + |UPOLYC-;nextItemInner|) + (EXIT + (COND + ((QEQCAR |n3| 1) (CONS 1 "failed")) + ((QUOTE T) + (CONS + 0 + (SPADCALL + (QCDR |n3|) + (SPADCALL |n| (QREFELT |$| 11)) + (QREFELT |$| 49))))))))))))))))) + +(DEFUN |UPOLYC-;nextItem;SU;29| (|n| |$|) + (PROG (|n1| #1=#:G103350) + (RETURN + (SEQ + (LETT |n1| (|UPOLYC-;nextItemInner| |n| |$|) |UPOLYC-;nextItem;SU;29|) + (EXIT + (COND + ((QEQCAR |n1| 1) + (CONS + 0 + (SPADCALL + (PROG2 + (LETT #1# + (SPADCALL (|spadConstant| |$| 117) (QREFELT |$| 120)) + |UPOLYC-;nextItem;SU;29|) + (QCDR #1#) + (|check-union| (QEQCAR #1# 0) (QREFELT |$| 7) #1#)) + (|+| 1 (SPADCALL |n| (QREFELT |$| 11))) + (QREFELT |$| 49)))) + ((QUOTE T) |n1|))))))) + +(DEFUN |UPOLYC-;content;SSaosS;30| (|p| |v| |$|) + (SPADCALL (SPADCALL |p| (QREFELT |$| 123)) (QREFELT |$| 30))) + +(DEFUN |UPOLYC-;primeFactor| (|p| |q| |$|) + (PROG (#1=#:G103356 |p1|) + (RETURN + (SEQ + (LETT |p1| + (PROG2 + (LETT #1# + (SPADCALL |p| + (SPADCALL |p| |q| (QREFELT |$| 125)) + (QREFELT |$| 126)) + |UPOLYC-;primeFactor|) + (QCDR #1#) + (|check-union| (QEQCAR #1# 0) (QREFELT |$| 6) #1#)) + |UPOLYC-;primeFactor|) + (EXIT + (COND + ((SPADCALL |p1| |p| (QREFELT |$| 127)) |p|) + ((QUOTE T) (|UPOLYC-;primeFactor| |p1| |q| |$|)))))))) + +(DEFUN |UPOLYC-;separate;2SR;32| (|p| |q| |$|) + (PROG (|a| #1=#:G103362) + (RETURN + (SEQ + (LETT |a| + (|UPOLYC-;primeFactor| |p| |q| |$|) + |UPOLYC-;separate;2SR;32|) + (EXIT + (CONS + |a| + (PROG2 + (LETT #1# + (SPADCALL |p| |a| (QREFELT |$| 126)) + |UPOLYC-;separate;2SR;32|) + (QCDR #1#) + (|check-union| (QEQCAR #1# 0) (QREFELT |$| 6) #1#)))))))) + +(DEFUN |UPOLYC-;differentiate;SM2S;33| (|x| |deriv| |x'| |$|) + (PROG (|dg| |lc| #1=#:G103367 |d|) + (RETURN + (SEQ + (LETT |d| (|spadConstant| |$| 60) |UPOLYC-;differentiate;SM2S;33|) + (SEQ G190 + (COND + ((NULL + (|<| 0 + (LETT |dg| + (SPADCALL |x| (QREFELT |$| 11)) + |UPOLYC-;differentiate;SM2S;33|))) + (GO G191))) + (SEQ + (LETT |lc| + (SPADCALL |x| (QREFELT |$| 53)) + |UPOLYC-;differentiate;SM2S;33|) + (LETT |d| + (SPADCALL + (SPADCALL |d| + (SPADCALL |x'| + (SPADCALL + (SPADCALL |dg| |lc| (QREFELT |$| 131)) + (PROG1 + (LETT #1# (|-| |dg| 1) |UPOLYC-;differentiate;SM2S;33|) + (|check-subtype| + (|>=| #1# 0) + (QUOTE (|NonNegativeInteger|)) + #1#)) + (QREFELT |$| 49)) + (QREFELT |$| 71)) + (QREFELT |$| 65)) + (SPADCALL + (SPADCALL |lc| |deriv|) + |dg| + (QREFELT |$| 49)) + (QREFELT |$| 65)) + |UPOLYC-;differentiate;SM2S;33|) + (EXIT + (LETT |x| + (SPADCALL |x| (QREFELT |$| 55)) + |UPOLYC-;differentiate;SM2S;33|))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (EXIT + (SPADCALL |d| + (SPADCALL + (SPADCALL + (SPADCALL |x| (QREFELT |$| 53)) + |deriv|) + (QREFELT |$| 30)) + (QREFELT |$| 65))))))) + +(DEFUN |UPOLYC-;ncdiff| (|n| |x'| |$|) + (PROG (#1=#:G103385 |n1|) + (RETURN + (COND + ((ZEROP |n|) (|spadConstant| |$| 60)) + ((ZEROP + (LETT |n1| + (PROG1 + (LETT #1# (|-| |n| 1) |UPOLYC-;ncdiff|) + (|check-subtype| + (|>=| #1# 0) + (QUOTE (|NonNegativeInteger|)) + #1#)) + |UPOLYC-;ncdiff|)) + |x'|) + ((QUOTE T) + (SPADCALL + (SPADCALL |x'| + (SPADCALL (|spadConstant| |$| 48) |n1| (QREFELT |$| 49)) + (QREFELT |$| 71)) + (SPADCALL + (SPADCALL (|spadConstant| |$| 48) 1 (QREFELT |$| 49)) + (|UPOLYC-;ncdiff| |n1| |x'| |$|) + (QREFELT |$| 71)) + (QREFELT |$| 65))))))) + +(DEFUN |UPOLYC-;differentiate;SM2S;35| (|x| |deriv| |x'| |$|) + (PROG (|dg| |lc| |d|) + (RETURN + (SEQ + (LETT |d| (|spadConstant| |$| 60) |UPOLYC-;differentiate;SM2S;35|) + (SEQ G190 + (COND + ((NULL + (|<| 0 + (LETT |dg| + (SPADCALL |x| (QREFELT |$| 11)) + |UPOLYC-;differentiate;SM2S;35|))) + (GO G191))) + (SEQ + (LETT |lc| + (SPADCALL |x| (QREFELT |$| 53)) + |UPOLYC-;differentiate;SM2S;35|) + (LETT |d| + (SPADCALL + (SPADCALL |d| + (SPADCALL + (SPADCALL |lc| |deriv|) + |dg| + (QREFELT |$| 49)) + (QREFELT |$| 65)) + (SPADCALL |lc| + (|UPOLYC-;ncdiff| |dg| |x'| |$|) + (QREFELT |$| 134)) + (QREFELT |$| 65)) + |UPOLYC-;differentiate;SM2S;35|) + (EXIT + (LETT |x| + (SPADCALL |x| (QREFELT |$| 55)) + |UPOLYC-;differentiate;SM2S;35|))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (EXIT + (SPADCALL |d| + (SPADCALL + (SPADCALL (SPADCALL |x| (QREFELT |$| 53)) |deriv|) + (QREFELT |$| 30)) + (QREFELT |$| 65))))))) + +(DEFUN |UPOLYC-;differentiate;SMS;36| (|x| |deriv| |$|) + (SPADCALL |x| |deriv| (|spadConstant| |$| 47) (QREFELT |$| 135))) + +(DEFUN |UPOLYC-;differentiate;2S;37| (|x| |$|) + (PROG (|dg| #1=#:G103394 |d|) + (RETURN + (SEQ + (LETT |d| (|spadConstant| |$| 60) |UPOLYC-;differentiate;2S;37|) + (SEQ G190 + (COND + ((NULL + (|<| 0 + (LETT |dg| + (SPADCALL |x| (QREFELT |$| 11)) + |UPOLYC-;differentiate;2S;37|))) + (GO G191))) + (SEQ + (LETT |d| + (SPADCALL |d| + (SPADCALL + (SPADCALL |dg| + (SPADCALL |x| (QREFELT |$| 53)) (QREFELT |$| 131)) + (PROG1 + (LETT #1# (|-| |dg| 1) |UPOLYC-;differentiate;2S;37|) + (|check-subtype| + (|>=| #1# 0) + (QUOTE (|NonNegativeInteger|)) + #1#)) + (QREFELT |$| 49)) + (QREFELT |$| 65)) + |UPOLYC-;differentiate;2S;37|) + (EXIT + (LETT |x| + (SPADCALL |x| (QREFELT |$| 55)) + |UPOLYC-;differentiate;2S;37|))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (EXIT |d|))))) + +(DEFUN |UPOLYC-;differentiate;SSaosS;38| (|x| |v| |$|) + (SPADCALL |x| (QREFELT |$| 138))) + +(DEFUN |UPOLYC-;elt;3F;39| (|g| |f| |$|) + (SPADCALL + (SPADCALL + (SPADCALL |g| (QREFELT |$| 141)) + |f| + (QREFELT |$| 143)) + (SPADCALL (SPADCALL |g| (QREFELT |$| 144)) |f| (QREFELT |$| 143)) + (QREFELT |$| 145))) + +(DEFUN |UPOLYC-;pseudoQuotient;3S;40| (|p| |q| |$|) + (PROG (|n| #1=#:G103440 #2=#:G103442) + (RETURN + (SEQ + (LETT |n| + (|+| + (|-| + (SPADCALL |p| (QREFELT |$| 11)) + (SPADCALL |q| (QREFELT |$| 11))) 1) + |UPOLYC-;pseudoQuotient;3S;40|) + (EXIT + (COND + ((|<| |n| 1) (|spadConstant| |$| 60)) + ((QUOTE T) + (PROG2 + (LETT #2# + (SPADCALL + (SPADCALL + (SPADCALL + (SPADCALL + (SPADCALL |q| (QREFELT |$| 53)) + (PROG1 + (LETT #1# |n| |UPOLYC-;pseudoQuotient;3S;40|) + (|check-subtype| + (|>=| #1# 0) + (QUOTE (|NonNegativeInteger|)) + #1#)) + (QREFELT |$| 147)) + |p| + (QREFELT |$| 134)) + (SPADCALL |p| |q| (QREFELT |$| 148)) + (QREFELT |$| 149)) + |q| + (QREFELT |$| 126)) + |UPOLYC-;pseudoQuotient;3S;40|) + (QCDR #2#) + (|check-union| (QEQCAR #2# 0) (QREFELT |$| 6) #2#))))))))) + +(DEFUN |UPOLYC-;pseudoDivide;2SR;41| (|p| |q| |$|) + (PROG (|n| |prem| #1=#:G103448 |lc| #2=#:G103450) + (RETURN + (SEQ + (LETT |n| + (|+| + (|-| + (SPADCALL |p| (QREFELT |$| 11)) + (SPADCALL |q| (QREFELT |$| 11))) 1) + |UPOLYC-;pseudoDivide;2SR;41|) + (EXIT + (COND + ((|<| |n| 1) + (VECTOR (|spadConstant| |$| 48) (|spadConstant| |$| 60) |p|)) + ((QUOTE T) + (SEQ + (LETT |prem| + (SPADCALL |p| |q| (QREFELT |$| 148)) + |UPOLYC-;pseudoDivide;2SR;41|) + (LETT |lc| + (SPADCALL + (SPADCALL |q| (QREFELT |$| 53)) + (PROG1 + (LETT #1# |n| |UPOLYC-;pseudoDivide;2SR;41|) + (|check-subtype| + (|>=| #1# 0) + (QUOTE (|NonNegativeInteger|)) #1#)) + (QREFELT |$| 147)) + |UPOLYC-;pseudoDivide;2SR;41|) + (EXIT + (VECTOR |lc| + (PROG2 + (LETT #2# + (SPADCALL + (SPADCALL + (SPADCALL |lc| |p| (QREFELT |$| 134)) + |prem| + (QREFELT |$| 149)) + |q| + (QREFELT |$| 126)) + |UPOLYC-;pseudoDivide;2SR;41|) + (QCDR #2#) + (|check-union| (QEQCAR #2# 0) (QREFELT |$| 6) #2#)) + |prem|)))))))))) + +(DEFUN |UPOLYC-;composite;FSU;42| (|f| |q| |$|) + (PROG (|n| |d|) + (RETURN + (SEQ + (LETT |n| + (SPADCALL (SPADCALL |f| (QREFELT |$| 141)) |q| (QREFELT |$| 153)) + |UPOLYC-;composite;FSU;42|) + (EXIT + (COND + ((QEQCAR |n| 1) (CONS 1 "failed")) + ((QUOTE T) + (SEQ + (LETT |d| + (SPADCALL + (SPADCALL |f| (QREFELT |$| 144)) |q| (QREFELT |$| 153)) + |UPOLYC-;composite;FSU;42|) + (EXIT + (COND + ((QEQCAR |d| 1) (CONS 1 "failed")) + ((QUOTE T) + (CONS + 0 + (SPADCALL + (QCDR |n|) + (QCDR |d|) + (QREFELT |$| 154)))))))))))))) + +(DEFUN |UPOLYC-;composite;2SU;43| (|p| |q| |$|) + (PROG (|cqr| |v| |u| |w| #1=#:G103476) + (RETURN + (SEQ + (COND + ((SPADCALL |p| (QREFELT |$| 157)) (CONS 0 |p|)) + ((QUOTE T) + (SEQ + (EXIT + (SEQ + (LETT |cqr| + (SPADCALL |p| |q| (QREFELT |$| 158)) + |UPOLYC-;composite;2SU;43|) + (COND + ((SPADCALL (QVELT |cqr| 2) (QREFELT |$| 157)) + (SEQ + (LETT |v| + (SPADCALL + (QVELT |cqr| 2) + (QVELT |cqr| 0) + (QREFELT |$| 159)) + |UPOLYC-;composite;2SU;43|) + (EXIT + (COND + ((QEQCAR |v| 0) + (SEQ + (LETT |u| + (SPADCALL + (QVELT |cqr| 1) + |q| + (QREFELT |$| 153)) + |UPOLYC-;composite;2SU;43|) + (EXIT + (COND + ((QEQCAR |u| 0) + (SEQ + (LETT |w| + (SPADCALL + (QCDR |u|) + (QVELT |cqr| 0) + (QREFELT |$| 159)) + |UPOLYC-;composite;2SU;43|) + (EXIT + (COND + ((QEQCAR |w| 0) + (PROGN + (LETT #1# + (CONS + 0 + (SPADCALL + (QCDR |v|) + (SPADCALL + (SPADCALL + (|spadConstant| |$| 48) + 1 + (QREFELT |$| 49)) + (QCDR |w|) + (QREFELT |$| 71)) + (QREFELT |$| 65))) + |UPOLYC-;composite;2SU;43|) + (GO #1#)))))))))))))))) + (EXIT (CONS 1 "failed")))) + #1# + (EXIT #1#)))))))) + +(DEFUN |UPOLYC-;elt;S2F;44| (|p| |f| |$|) + (PROG (|n| #1=#:G103483 |ans|) + (RETURN + (SEQ + (COND + ((SPADCALL |p| (QREFELT |$| 9)) (|spadConstant| |$| 161)) + ((QUOTE T) + (SEQ + (LETT |ans| + (SPADCALL + (SPADCALL (SPADCALL |p| (QREFELT |$| 53)) (QREFELT |$| 30)) + (QREFELT |$| 162)) + |UPOLYC-;elt;S2F;44|) + (LETT |n| (SPADCALL |p| (QREFELT |$| 11)) |UPOLYC-;elt;S2F;44|) + (SEQ G190 + (COND + ((NULL + (COND + ((SPADCALL + (LETT |p| + (SPADCALL |p| (QREFELT |$| 55)) + |UPOLYC-;elt;S2F;44|) + (QREFELT |$| 9)) + (QUOTE NIL)) + ((QUOTE T) (QUOTE T)))) + (GO G191))) + (SEQ + (EXIT + (LETT |ans| + (SPADCALL + (SPADCALL |ans| + (SPADCALL |f| + (PROG1 + (LETT #1# + (|-| |n| + (LETT |n| + (SPADCALL |p| (QREFELT |$| 11)) + |UPOLYC-;elt;S2F;44|)) + |UPOLYC-;elt;S2F;44|) + (|check-subtype| + (|>=| #1# 0) + (QUOTE (|NonNegativeInteger|)) + #1#)) + (QREFELT |$| 163)) + (QREFELT |$| 164)) + (SPADCALL + (SPADCALL + (SPADCALL |p| (QREFELT |$| 53)) + (QREFELT |$| 30)) + (QREFELT |$| 162)) + (QREFELT |$| 165)) + |UPOLYC-;elt;S2F;44|))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (EXIT + (COND + ((ZEROP |n|) |ans|) + ((QUOTE T) + (SPADCALL |ans| + (SPADCALL |f| |n| (QREFELT |$| 166)) + (QREFELT |$| 164)))))))))))) + +(DEFUN |UPOLYC-;order;2SNni;45| (|p| |q| |$|) + (PROG (|u| #1=#:G103497 |ans|) + (RETURN + (SEQ + (EXIT + (COND + ((SPADCALL |p| (QREFELT |$| 9)) + (|error| "order: arguments must be nonzero")) + ((|<| (SPADCALL |q| (QREFELT |$| 11)) 1) + (|error| "order: place must be non-trivial")) + ((QUOTE T) + (SEQ + (LETT |ans| 0 |UPOLYC-;order;2SNni;45|) + (EXIT + (SEQ G190 + NIL + (SEQ + (LETT |u| + (SPADCALL |p| |q| (QREFELT |$| 126)) + |UPOLYC-;order;2SNni;45|) + (EXIT + (COND + ((QEQCAR |u| 1) + (PROGN + (LETT #1# |ans| |UPOLYC-;order;2SNni;45|) + (GO #1#))) + ((QUOTE T) + (SEQ + (LETT |p| (QCDR |u|) |UPOLYC-;order;2SNni;45|) + (EXIT + (LETT + |ans| + (|+| |ans| 1) + |UPOLYC-;order;2SNni;45|))))))) + NIL + (GO G190) + G191 + (EXIT NIL))))))) + #1# + (EXIT #1#))))) + +(DEFUN |UPOLYC-;squareFree;SF;46| (|p| |$|) + (SPADCALL |p| (QREFELT |$| 170))) + +(DEFUN |UPOLYC-;squareFreePart;2S;47| (|p| |$|) + (SPADCALL |p| (QREFELT |$| 172))) + +(DEFUN |UPOLYC-;gcdPolynomial;3Sup;48| (|pp| |qq| |$|) + (COND + ((SPADCALL |pp| (QREFELT |$| 174)) (SPADCALL |qq| (QREFELT |$| 175))) + ((SPADCALL |qq| (QREFELT |$| 174)) (SPADCALL |pp| (QREFELT |$| 175))) + ((QUOTE T) + (SPADCALL + (SPADCALL + (SPADCALL + (SPADCALL |pp| (QREFELT |$| 176)) + (SPADCALL |qq| (QREFELT |$| 176)) (QREFELT |$| 125)) + (SPADCALL + (SPADCALL + (SPADCALL |pp| (QREFELT |$| 177)) + (SPADCALL |qq| (QREFELT |$| 177)) (QREFELT |$| 178)) + (QREFELT |$| 177)) + (QREFELT |$| 179)) + (QREFELT |$| 175))))) + +(DEFUN |UPOLYC-;squareFreePolynomial;SupF;49| (|pp| |$|) + (SPADCALL |pp| (QREFELT |$| 182))) + +(DEFUN |UPOLYC-;elt;F2R;50| (|f| |r| |$|) + (SPADCALL + (SPADCALL + (SPADCALL |f| (QREFELT |$| 141)) + |r| + (QREFELT |$| 29)) + (SPADCALL (SPADCALL |f| (QREFELT |$| 144)) |r| (QREFELT |$| 29)) + (QREFELT |$| 184))) + +(DEFUN |UPOLYC-;euclideanSize;SNni;51| (|x| |$|) + (COND + ((SPADCALL |x| (QREFELT |$| 9)) + (|error| "euclideanSize called on 0 in Univariate Polynomial")) + ((QUOTE T) (SPADCALL |x| (QREFELT |$| 11))))) + +(DEFUN |UPOLYC-;divide;2SR;52| (|x| |y| |$|) + (PROG (|lc| |f| #1=#:G103510 |n| |quot|) + (RETURN + (SEQ + (COND + ((SPADCALL |y| (QREFELT |$| 9)) + (|error| "division by 0 in Univariate Polynomials")) + ((QUOTE T) + (SEQ + (LETT |quot| (|spadConstant| |$| 60) |UPOLYC-;divide;2SR;52|) + (LETT |lc| + (SPADCALL (SPADCALL |y| (QREFELT |$| 53)) (QREFELT |$| 187)) + |UPOLYC-;divide;2SR;52|) + (SEQ G190 + (COND + ((NULL + (COND + ((OR + (SPADCALL |x| (QREFELT |$| 9)) + (|<| + (SPADCALL |x| (QREFELT |$| 11)) + (SPADCALL |y| (QREFELT |$| 11)))) + (QUOTE NIL)) ((QUOTE T) (QUOTE T)))) + (GO G191))) + (SEQ + (LETT |f| + (SPADCALL |lc| + (SPADCALL |x| (QREFELT |$| 53)) + (QREFELT |$| 188)) + |UPOLYC-;divide;2SR;52|) + (LETT |n| + (PROG1 + (LETT #1# + (|-| + (SPADCALL |x| (QREFELT |$| 11)) + (SPADCALL |y| (QREFELT |$| 11))) + |UPOLYC-;divide;2SR;52|) + (|check-subtype| + (|>=| #1# 0) + (QUOTE (|NonNegativeInteger|)) + #1#)) + |UPOLYC-;divide;2SR;52|) + (LETT |quot| + (SPADCALL |quot| + (SPADCALL |f| |n| (QREFELT |$| 49)) + (QREFELT |$| 65)) + |UPOLYC-;divide;2SR;52|) + (EXIT + (LETT |x| + (SPADCALL |x| + (SPADCALL + (SPADCALL |f| |n| (QREFELT |$| 49)) + |y| + (QREFELT |$| 71)) + (QREFELT |$| 149)) + |UPOLYC-;divide;2SR;52|))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (EXIT (CONS |quot| |x|))))))))) + +(DEFUN |UPOLYC-;integrate;2S;53| (|p| |$|) + (PROG (|l| |d| |ans|) + (RETURN + (SEQ + (LETT |ans| (|spadConstant| |$| 60) |UPOLYC-;integrate;2S;53|) + (SEQ G190 + (COND + ((NULL + (COND + ((SPADCALL |p| (|spadConstant| |$| 60) (QREFELT |$| 127)) + (QUOTE NIL)) + ((QUOTE T) (QUOTE T)))) (GO G191))) + (SEQ + (LETT |l| + (SPADCALL |p| (QREFELT |$| 53)) + |UPOLYC-;integrate;2S;53|) + (LETT |d| + (|+| 1 (SPADCALL |p| (QREFELT |$| 11))) + |UPOLYC-;integrate;2S;53|) + (LETT |ans| + (SPADCALL |ans| + (SPADCALL + (SPADCALL (SPADCALL |d| (QREFELT |$| 191)) (QREFELT |$| 192)) + (SPADCALL |l| |d| (QREFELT |$| 49)) (QREFELT |$| 193)) + (QREFELT |$| 65)) + |UPOLYC-;integrate;2S;53|) + (EXIT + (LETT |p| + (SPADCALL |p| (QREFELT |$| 55)) + |UPOLYC-;integrate;2S;53|))) + NIL + (GO G190) + G191 + (EXIT NIL)) + (EXIT |ans|))))) + +(DEFUN |UnivariatePolynomialCategory&| (|#1| |#2|) + (PROG (|DV$1| |DV$2| |dv$| |$| |pv$|) + (RETURN + (PROGN + (LETT |DV$1| (|devaluate| |#1|) . #1=(|UnivariatePolynomialCategory&|)) + (LETT |DV$2| (|devaluate| |#2|) . #1#) + (LETT |dv$| + (LIST (QUOTE |UnivariatePolynomialCategory&|) |DV$1| |DV$2|) . #1#) + (LETT |$| (GETREFV 201) . #1#) + (QSETREFV |$| 0 |dv$|) + (QSETREFV |$| 3 + (LETT |pv$| + (|buildPredVector| 0 0 + (LIST + (|HasCategory| |#2| + (QUOTE (|Algebra| (|Fraction| (|Integer|))))) + (|HasCategory| |#2| (QUOTE (|Field|))) + (|HasCategory| |#2| (QUOTE (|GcdDomain|))) + (|HasCategory| |#2| (QUOTE (|IntegralDomain|))) + (|HasCategory| |#2| (QUOTE (|CommutativeRing|))) + (|HasCategory| |#2| (QUOTE (|StepThrough|))))) . #1#)) + (|stuffDomainSlots| |$|) + (QSETREFV |$| 6 |#1|) + (QSETREFV |$| 7 |#2|) + (COND + ((|HasCategory| |#2| (QUOTE (|PolynomialFactorizationExplicit|))) + (PROGN + (QSETREFV |$| 81 + (CONS + (|dispatchFunction| + |UPOLYC-;solveLinearPolynomialEquation;LSupU;20|) + |$|)) + (QSETREFV |$| 85 + (CONS + (|dispatchFunction| |UPOLYC-;factorPolynomial;SupF;21|) + |$|)) + (QSETREFV |$| 87 + (CONS + (|dispatchFunction| + |UPOLYC-;factorSquareFreePolynomial;SupF;22|) + |$|)) + (QSETREFV |$| 105 + (CONS (|dispatchFunction| |UPOLYC-;factor;SF;23|) |$|))))) + (COND + ((|testBitVector| |pv$| 6) + (PROGN + (QSETREFV |$| 118 + (CONS (|dispatchFunction| |UPOLYC-;init;S;27|) |$|)) + NIL + (QSETREFV |$| 122 + (CONS (|dispatchFunction| |UPOLYC-;nextItem;SU;29|) |$|))))) + (COND + ((|testBitVector| |pv$| 3) + (PROGN + (QSETREFV |$| 124 + (CONS (|dispatchFunction| |UPOLYC-;content;SSaosS;30|) |$|)) + NIL + (QSETREFV |$| 129 + (CONS (|dispatchFunction| |UPOLYC-;separate;2SR;32|) |$|))))) + (COND + ((|testBitVector| |pv$| 5) + (QSETREFV |$| 133 + (CONS + (|dispatchFunction| |UPOLYC-;differentiate;SM2S;33|) + |$|))) + ((QUOTE T) + (PROGN + (QSETREFV |$| 133 + (CONS + (|dispatchFunction| |UPOLYC-;differentiate;SM2S;35|) + |$|))))) + (COND + ((|testBitVector| |pv$| 4) + (PROGN + (QSETREFV |$| 146 + (CONS (|dispatchFunction| |UPOLYC-;elt;3F;39|) |$|)) + (QSETREFV |$| 150 + (CONS (|dispatchFunction| |UPOLYC-;pseudoQuotient;3S;40|) |$|)) + (QSETREFV |$| 152 + (CONS (|dispatchFunction| |UPOLYC-;pseudoDivide;2SR;41|) |$|)) + (QSETREFV |$| 156 + (CONS (|dispatchFunction| |UPOLYC-;composite;FSU;42|) |$|)) + (QSETREFV |$| 160 + (CONS (|dispatchFunction| |UPOLYC-;composite;2SU;43|) |$|)) + (QSETREFV |$| 167 + (CONS (|dispatchFunction| |UPOLYC-;elt;S2F;44|) |$|)) + (QSETREFV |$| 168 + (CONS (|dispatchFunction| |UPOLYC-;order;2SNni;45|) |$|))))) + (COND + ((|testBitVector| |pv$| 3) + (PROGN + (QSETREFV |$| 171 + (CONS (|dispatchFunction| |UPOLYC-;squareFree;SF;46|) |$|)) + (QSETREFV |$| 173 + (CONS + (|dispatchFunction| |UPOLYC-;squareFreePart;2S;47|) + |$|))))) + (COND + ((|HasCategory| |#2| (QUOTE (|PolynomialFactorizationExplicit|))) + (PROGN + (QSETREFV |$| 180 + (CONS + (|dispatchFunction| |UPOLYC-;gcdPolynomial;3Sup;48|) + |$|)) + (QSETREFV |$| 183 + (CONS + (|dispatchFunction| |UPOLYC-;squareFreePolynomial;SupF;49|) + |$|))))) + (COND + ((|testBitVector| |pv$| 2) + (PROGN + (QSETREFV |$| 185 + (CONS (|dispatchFunction| |UPOLYC-;elt;F2R;50|) |$|)) + (QSETREFV |$| 186 + (CONS + (|dispatchFunction| |UPOLYC-;euclideanSize;SNni;51|) + |$|)) + (QSETREFV |$| 189 + (CONS (|dispatchFunction| |UPOLYC-;divide;2SR;52|) |$|))))) + (COND + ((|testBitVector| |pv$| 1) + (QSETREFV |$| 194 + (CONS + (|dispatchFunction| |UPOLYC-;integrate;2S;53|) + |$|)))) |$|)))) + +(MAKEPROP + (QUOTE |UnivariatePolynomialCategory&|) + (QUOTE |infovec|) + (LIST + (QUOTE + #(NIL NIL NIL NIL NIL NIL + (|local| |#1|) + (|local| |#2|) + (|Boolean|) + (0 . |zero?|) + (|NonNegativeInteger|) + (5 . |degree|) + (|SingletonAsOrderedSet|) + (10 . |create|) + (|List| 12) + |UPOLYC-;variables;SL;1| + |UPOLYC-;degree;SSaosNni;2| + (14 . |totalDegree|) + |UPOLYC-;totalDegree;SLNni;3| + (|List| 10) + |UPOLYC-;degree;SLL;4| + (19 . |eval|) + (|List| |$|) + |UPOLYC-;eval;SLLS;5| + (26 . |elt|) + |UPOLYC-;eval;SSaos2S;6| + (32 . |eval|) + (|List| 7) + |UPOLYC-;eval;SLLS;7| + (39 . |elt|) + (45 . |coerce|) + |UPOLYC-;eval;SSaosRS;8| + (|Equation| 6) + (50 . |lhs|) + (|Union| 12 (QUOTE "failed")) + (55 . |mainVariable|) + (60 . |rhs|) + (|List| 197) + |UPOLYC-;eval;SLS;9| + |UPOLYC-;mainVariable;SU;10| + (65 . |minimumDegree|) + |UPOLYC-;minimumDegree;SSaosNni;11| + |UPOLYC-;minimumDegree;SLL;12| + (70 . |+|) + (|Mapping| 10 10) + (76 . |mapExponents|) + |UPOLYC-;monomial;SSaosNniS;13| + (82 . |One|) + (86 . |One|) + (90 . |monomial|) + |UPOLYC-;coerce;SaosS;14| + (|SparseUnivariatePolynomial| 7) + (96 . |Zero|) + (100 . |leadingCoefficient|) + (105 . |monomial|) + (111 . |reductum|) + (116 . |makeSUP|) + (121 . |+|) + |UPOLYC-;makeSUP;SSup;15| + (127 . |zero?|) + (132 . |Zero|) + (136 . |leadingCoefficient|) + (141 . |degree|) + (146 . |reductum|) + (151 . |unmakeSUP|) + (156 . |+|) + |UPOLYC-;unmakeSUP;SupS;16| + (|Record| (|:| |quotient| |$|) (|:| |remainder| |$|)) + (162 . |monicDivide|) + |UPOLYC-;karatsubaDivide;SNniR;17| + |UPOLYC-;shiftRight;SNniS;18| + (168 . |*|) + |UPOLYC-;shiftLeft;SNniS;19| + (|Union| 74 (QUOTE "failed")) + (|List| 75) + (|SparseUnivariatePolynomial| 6) + (|PolynomialFactorizationByRecursionUnivariate| 7 6) + (174 . |solveLinearPolynomialEquationByRecursion|) + (|Union| 79 (QUOTE "failed")) + (|List| 80) + (|SparseUnivariatePolynomial| |$|) + (180 . |solveLinearPolynomialEquation|) + (|Factored| 75) + (186 . |factorByRecursion|) + (|Factored| 80) + (191 . |factorPolynomial|) + (196 . |factorSquareFreeByRecursion|) + (201 . |factorSquareFreePolynomial|) + (|Factored| |$|) + (206 . |factor|) + (|Factored| 7) + (211 . |unit|) + (|Union| (QUOTE "nil") (QUOTE "sqfr") (QUOTE "irred") (QUOTE "prime")) + (|Record| (|:| |flg| 92) (|:| |fctr| 7) (|:| |xpnt| 109)) + (|List| 93) + (216 . |factorList|) + (|Record| (|:| |flg| 92) (|:| |fctr| 6) (|:| |xpnt| 109)) + (|List| 96) + (|Factored| 6) + (221 . |makeFR|) + (227 . |factorPolynomial|) + (|Mapping| 6 51) + (|Factored| 51) + (|FactoredFunctions2| 51 6) + (232 . |map|) + (238 . |factor|) + (243 . |Zero|) + (|Vector| 7) + (247 . |new|) + (|Integer|) + (253 . |minIndex|) + (258 . |coefficient|) + (264 . |qsetelt!|) + |UPOLYC-;vectorise;SNniV;24| + |UPOLYC-;retract;SR;25| + (|Union| 7 (QUOTE "failed")) + |UPOLYC-;retractIfCan;SU;26| + (271 . |init|) + (275 . |init|) + (|Union| |$| (QUOTE "failed")) + (279 . |nextItem|) + (284 . |One|) + (288 . |nextItem|) + (293 . |content|) + (298 . |content|) + (304 . |gcd|) + (310 . |exquo|) + (316 . |=|) + (|Record| (|:| |primePart| |$|) (|:| |commonPart| |$|)) + (322 . |separate|) + (328 . |Zero|) + (332 . |*|) + (|Mapping| 7 7) + (338 . |differentiate|) + (345 . |*|) + (351 . |differentiate|) + |UPOLYC-;differentiate;SMS;36| + |UPOLYC-;differentiate;2S;37| + (358 . |differentiate|) + |UPOLYC-;differentiate;SSaosS;38| + (|Fraction| 6) + (363 . |numer|) + (|Fraction| |$|) + (368 . |elt|) + (374 . |denom|) + (379 . |/|) + (385 . |elt|) + (391 . |**|) + (397 . |pseudoRemainder|) + (403 . |-|) + (409 . |pseudoQuotient|) + (|Record| (|:| |coef| 7) (|:| |quotient| |$|) (|:| |remainder| |$|)) + (415 . |pseudoDivide|) + (421 . |composite|) + (427 . |/|) + (|Union| 142 (QUOTE "failed")) + (433 . |composite|) + (439 . |ground?|) + (444 . |pseudoDivide|) + (450 . |exquo|) + (456 . |composite|) + (462 . |Zero|) + (466 . |coerce|) + (471 . |**|) + (477 . |*|) + (483 . |+|) + (489 . |**|) + (495 . |elt|) + (501 . |order|) + (|UnivariatePolynomialSquareFree| 7 6) + (507 . |squareFree|) + (512 . |squareFree|) + (517 . |squareFreePart|) + (522 . |squareFreePart|) + (527 . |zero?|) + (532 . |unitCanonical|) + (537 . |content|) + (542 . |primitivePart|) + (547 . |subResultantGcd|) + (553 . |*|) + (559 . |gcdPolynomial|) + (|UnivariatePolynomialSquareFree| 6 75) + (565 . |squareFree|) + (570 . |squareFreePolynomial|) + (575 . |/|) + (581 . |elt|) + (587 . |euclideanSize|) + (592 . |inv|) + (597 . |*|) + (603 . |divide|) + (|Fraction| 109) + (609 . |coerce|) + (614 . |inv|) + (619 . |*|) + (625 . |integrate|) + (|Symbol|) + (|List| 195) + (|Equation| |$|) + (|Union| 109 (QUOTE "failed")) + (|Union| 190 (QUOTE "failed")) + (|OutputForm|))) + (QUOTE + #(|vectorise| 630 |variables| 636 |unmakeSUP| 641 |totalDegree| 646 + |squareFreePolynomial| 652 |squareFreePart| 657 |squareFree| 662 + |solveLinearPolynomialEquation| 667 |shiftRight| 673 |shiftLeft| 679 + |separate| 685 |retractIfCan| 691 |retract| 696 |pseudoQuotient| 701 + |pseudoDivide| 707 |order| 713 |nextItem| 719 |monomial| 724 + |minimumDegree| 731 |makeSUP| 743 |mainVariable| 748 + |karatsubaDivide| 753 |integrate| 759 |init| 764 |gcdPolynomial| 768 + |factorSquareFreePolynomial| 774 |factorPolynomial| 779 |factor| 784 + |eval| 789 |euclideanSize| 823 |elt| 828 |divide| 846 + |differentiate| 852 |degree| 876 |content| 888 |composite| 894 + |coerce| 906)) + (QUOTE NIL) + (CONS + (|makeByteWordVec2| 1 (QUOTE NIL)) + (CONS + (QUOTE #()) + (CONS + (QUOTE #()) + (|makeByteWordVec2| 194 + (QUOTE + (1 6 8 0 9 1 6 10 0 11 0 12 0 13 1 6 10 0 17 3 6 0 0 12 0 21 2 + 6 0 0 0 24 3 6 0 0 12 7 26 2 6 7 0 7 29 1 6 0 7 30 1 32 6 0 33 + 1 6 34 0 35 1 32 6 0 36 1 6 10 0 40 2 10 0 0 0 43 2 6 0 44 0 + 45 0 6 0 47 0 7 0 48 2 6 0 7 10 49 0 51 0 52 1 6 7 0 53 2 51 + 0 7 10 54 1 6 0 0 55 1 6 51 0 56 2 51 0 0 0 57 1 51 8 0 59 0 + 6 0 60 1 51 7 0 61 1 51 10 0 62 1 51 0 0 63 1 6 0 51 64 2 6 0 + 0 0 65 2 6 67 0 0 68 2 6 0 0 0 71 2 76 73 74 75 77 2 0 78 79 + 80 81 1 76 82 75 83 1 0 84 80 85 1 76 82 75 86 1 0 84 80 87 1 + 7 88 0 89 1 90 7 0 91 1 90 94 0 95 2 98 0 6 97 99 1 7 84 80 + 100 2 103 98 101 102 104 1 0 88 0 105 0 7 0 106 2 107 0 10 7 + 108 1 107 109 0 110 2 6 7 0 10 111 3 107 7 0 109 7 112 0 7 0 + 117 0 0 0 118 1 7 119 0 120 0 75 0 121 1 0 119 0 122 1 6 7 0 + 123 2 0 0 0 12 124 2 6 0 0 0 125 2 6 119 0 0 126 2 6 8 0 0 127 + 2 0 128 0 0 129 0 75 0 130 2 7 0 10 0 131 3 0 0 0 132 0 133 2 + 6 0 7 0 134 3 6 0 0 132 0 135 1 6 0 0 138 1 140 6 0 141 2 6 + 142 0 142 143 1 140 6 0 144 2 140 0 0 0 145 2 0 142 142 142 + 146 2 7 0 0 10 147 2 6 0 0 0 148 2 6 0 0 0 149 2 0 0 0 0 150 + 2 0 151 0 0 152 2 6 119 0 0 153 2 140 0 6 6 154 2 0 155 142 0 + 156 1 6 8 0 157 2 6 151 0 0 158 2 6 119 0 7 159 2 0 119 0 0 + 160 0 140 0 161 1 140 0 6 162 2 140 0 0 109 163 2 140 0 0 0 + 164 2 140 0 0 0 165 2 140 0 0 10 166 2 0 142 0 142 167 2 0 10 + 0 0 168 1 169 98 6 170 1 0 88 0 171 1 169 6 6 172 1 0 0 0 173 + 1 75 8 0 174 1 75 0 0 175 1 75 6 0 176 1 75 0 0 177 2 75 0 0 + 0 178 2 75 0 6 0 179 2 0 80 80 80 180 1 181 82 75 182 1 0 84 + 80 183 2 7 0 0 0 184 2 0 7 142 7 185 1 0 10 0 186 1 7 0 0 187 + 2 7 0 0 0 188 2 0 67 0 0 189 1 190 0 109 191 1 190 0 0 192 2 + 6 0 190 0 193 1 0 0 0 194 2 0 107 0 10 113 1 0 14 0 15 1 0 0 + 51 66 2 0 10 0 14 18 1 0 84 80 183 1 0 0 0 173 1 0 88 0 171 2 + 0 78 79 80 81 2 0 0 0 10 70 2 0 0 0 10 72 2 0 128 0 0 129 1 0 + 115 0 116 1 0 7 0 114 2 0 0 0 0 150 2 0 151 0 0 152 2 0 10 0 + 0 168 1 0 119 0 122 3 0 0 0 12 10 46 2 0 19 0 14 42 2 0 10 0 + 12 41 1 0 51 0 58 1 0 34 0 39 2 0 67 0 10 69 1 0 0 0 194 0 0 + 0 118 2 0 80 80 80 180 1 0 84 80 87 1 0 84 80 85 1 0 88 0 105 + 3 0 0 0 12 0 25 3 0 0 0 14 22 23 3 0 0 0 14 27 28 3 0 0 0 12 + 7 31 2 0 0 0 37 38 1 0 10 0 186 2 0 142 0 142 167 2 0 7 142 7 + 185 2 0 142 142 142 146 2 0 67 0 0 189 3 0 0 0 132 0 133 2 0 + 0 0 132 136 1 0 0 0 137 2 0 0 0 12 139 2 0 10 0 12 16 2 0 19 + 0 14 20 2 0 0 0 12 124 2 0 119 0 0 160 2 0 155 142 0 156 1 0 + 0 12 50)))))) + (QUOTE |lookupComplete|))) + +@ +\section{package UPOLYC2 UnivariatePolynomialCategoryFunctions2} +<<package UPOLYC2 UnivariatePolynomialCategoryFunctions2>>= +)abbrev package UPOLYC2 UnivariatePolynomialCategoryFunctions2 +++ Author: +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ Mapping from polynomials over R to polynomials over S +++ given a map from R to S assumed to send zero to zero. + +UnivariatePolynomialCategoryFunctions2(R,PR,S,PS): Exports == Impl where + R, S: Ring + PR : UnivariatePolynomialCategory R + PS : UnivariatePolynomialCategory S + + Exports ==> with + map: (R -> S, PR) -> PS + ++ map(f, p) takes a function f from R to S, + ++ and applies it to each (non-zero) coefficient of a polynomial p + ++ over R, getting a new polynomial over S. + ++ Note: since the map is not applied to zero elements, it may map zero + ++ to zero. + + Impl ==> add + map(f, p) == + ans:PS := 0 + while p ^= 0 repeat + ans := ans + monomial(f leadingCoefficient p, degree p) + p := reductum p + ans + +@ +\section{package COMMUPC CommuteUnivariatePolynomialCategory} +<<package COMMUPC CommuteUnivariatePolynomialCategory>>= +)abbrev package COMMUPC CommuteUnivariatePolynomialCategory +++ Author: Manuel Bronstein +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ A package for swapping the order of two variables in a tower of two +++ UnivariatePolynomialCategory extensions. + +CommuteUnivariatePolynomialCategory(R, UP, UPUP): Exports == Impl where + R : Ring + UP : UnivariatePolynomialCategory R + UPUP: UnivariatePolynomialCategory UP + + N ==> NonNegativeInteger + + Exports ==> with + swap: UPUP -> UPUP + ++ swap(p(x,y)) returns p(y,x). + + Impl ==> add + makePoly: (UP, N) -> UPUP + +-- converts P(x,y) to P(y,x) + swap poly == + ans:UPUP := 0 + while poly ^= 0 repeat + ans := ans + makePoly(leadingCoefficient poly, degree poly) + poly := reductum poly + ans + + makePoly(poly, d) == + ans:UPUP := 0 + while poly ^= 0 repeat + ans := ans + + monomial(monomial(leadingCoefficient poly, d), degree poly) + poly := reductum poly + ans + +@ +\section{License} +<<license>>= +--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. +--All rights reserved. +-- +--Redistribution and use in source and binary forms, with or without +--modification, are permitted provided that the following conditions are +--met: +-- +-- - Redistributions of source code must retain the above copyright +-- notice, this list of conditions and the following disclaimer. +-- +-- - Redistributions in binary form must reproduce the above copyright +-- notice, this list of conditions and the following disclaimer in +-- the documentation and/or other materials provided with the +-- distribution. +-- +-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the +-- names of its contributors may be used to endorse or promote products +-- derived from this software without specific prior written permission. +-- +--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +@ +<<*>>= +<<license>> + +<<category AMR AbelianMonoidRing>> +<<category FAMR FiniteAbelianMonoidRing>> +<<category POLYCAT PolynomialCategory>> +<<package POLYLIFT PolynomialCategoryLifting>> +<<category UPOLYC UnivariatePolynomialCategory>> +<<package UPOLYC2 UnivariatePolynomialCategoryFunctions2>> +<<package COMMUPC CommuteUnivariatePolynomialCategory>> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} |