\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)
(DEFPARAMETER |PolynomialCategory;CAT| 'NIL)
(DEFPARAMETER |PolynomialCategory;AL| 'NIL)
(DEFUN |PolynomialCategory| (&REST #0=#:G1406 &AUX #1=#:G1404)
(DSETQ #1# #0#)
(LET (#2=#:G1405)
(COND
((SETQ #2#
(|assoc| (|devaluateList| #1#) |PolynomialCategory;AL|))
(CDR #2#))
(T (SETQ |PolynomialCategory;AL|
(|cons5| (CONS (|devaluateList| #1#)
(SETQ #2#
(APPLY #'|PolynomialCategory;| #1#)))
|PolynomialCategory;AL|))
#2#))))
(DEFUN |PolynomialCategory;| (|t#1| |t#2| |t#3|)
(PROG (#0=#:G1403)
(RETURN
(PROG1 (LETT #0#
(|sublisV|
(PAIR '(|t#1| |t#2| |t#3|)
(LIST (|devaluate| |t#1|)
(|devaluate| |t#2|)
(|devaluate| |t#3|)))
(COND
(|PolynomialCategory;CAT|)
('T
(LETT |PolynomialCategory;CAT|
(|Join| (|PartialDifferentialRing|
'|t#3|)
(|FiniteAbelianMonoidRing|
'|t#1| '|t#2|)
(|Evalable| '$)
(|InnerEvalable| '|t#3| '|t#1|)
(|InnerEvalable| '|t#3| '$)
(|RetractableTo| '|t#3|)
(|FullyLinearlyExplicitRingOver|
'|t#1|)
(|mkCategory| '|domain|
'(((|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|))))
'(((|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|))))
'((|Factored| $) (|List| $)
(|List| |t#3|)
(|NonNegativeInteger|)
(|SparseUnivariatePolynomial|
$)
(|SparseUnivariatePolynomial|
|t#1|)
(|List|
(|NonNegativeInteger|)))
NIL))
. #1=(|PolynomialCategory|))))) . #1#)
(SETELT #0# 0
(LIST '|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 (#0=#:G1427 #1=#:G1421 #2=#:G1428 #3=#:G1429 |lvar| #4=#:G1430
|e| #5=#:G1431)
(RETURN
(SEQ (COND
((NULL |l|) |p|)
('T
(SEQ (SEQ (EXIT (SEQ (LETT |e| NIL |POLYCAT-;eval;SLS;1|)
(LETT #0# |l| |POLYCAT-;eval;SLS;1|)
G190
(COND
((OR (ATOM #0#)
(PROGN
(LETT |e| (CAR #0#)
|POLYCAT-;eval;SLS;1|)
NIL))
(GO G191)))
(SEQ
(EXIT
(COND
((QEQCAR
(SPADCALL
(SPADCALL |e|
(|getShellEntry| $ 11))
(|getShellEntry| $ 13))
1)
(PROGN
(LETT #1#
(|error|
"cannot find a variable to evaluate")
|POLYCAT-;eval;SLS;1|)
(GO #1#))))))
(LETT #0# (CDR #0#)
|POLYCAT-;eval;SLS;1|)
(GO G190) G191 (EXIT NIL)))
#1# (EXIT #1#))
(LETT |lvar|
(PROGN
(LETT #2# NIL |POLYCAT-;eval;SLS;1|)
(SEQ (LETT |e| NIL |POLYCAT-;eval;SLS;1|)
(LETT #3# |l| |POLYCAT-;eval;SLS;1|)
G190
(COND
((OR (ATOM #3#)
(PROGN
(LETT |e| (CAR #3#)
|POLYCAT-;eval;SLS;1|)
NIL))
(GO G191)))
(SEQ (EXIT
(LETT #2#
(CONS
(SPADCALL
(SPADCALL |e|
(|getShellEntry| $ 11))
(|getShellEntry| $ 14))
#2#)
|POLYCAT-;eval;SLS;1|)))
(LETT #3# (CDR #3#)
|POLYCAT-;eval;SLS;1|)
(GO G190) G191 (EXIT (NREVERSE0 #2#))))
|POLYCAT-;eval;SLS;1|)
(EXIT (SPADCALL |p| |lvar|
(PROGN
(LETT #4# NIL |POLYCAT-;eval;SLS;1|)
(SEQ (LETT |e| NIL
|POLYCAT-;eval;SLS;1|)
(LETT #5# |l|
|POLYCAT-;eval;SLS;1|)
G190
(COND
((OR (ATOM #5#)
(PROGN
(LETT |e| (CAR #5#)
|POLYCAT-;eval;SLS;1|)
NIL))
(GO G191)))
(SEQ
(EXIT
(LETT #4#
(CONS
(SPADCALL |e|
(|getShellEntry| $ 15))
#4#)
|POLYCAT-;eval;SLS;1|)))
(LETT #5# (CDR #5#)
|POLYCAT-;eval;SLS;1|)
(GO G190) G191
(EXIT (NREVERSE0 #4#))))
(|getShellEntry| $ 18))))))))))
(DEFUN |POLYCAT-;monomials;SL;2| (|p| $)
(PROG (|ml|)
(RETURN
(SEQ (LETT |ml| NIL |POLYCAT-;monomials;SL;2|)
(SEQ G190
(COND
((NULL (SPADCALL |p| (|spadConstant| $ 22)
(|getShellEntry| $ 25)))
(GO G191)))
(SEQ (LETT |ml|
(CONS (SPADCALL |p| (|getShellEntry| $ 26))
|ml|)
|POLYCAT-;monomials;SL;2|)
(EXIT (LETT |p|
(SPADCALL |p| (|getShellEntry| $ 27))
|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| (|getShellEntry| $ 29))
|POLYCAT-;isPlus;SU;3|)))
(CONS 1 "failed"))
('T (CONS 0 |l|))))))
(DEFUN |POLYCAT-;isTimes;SU;4| (|p| $)
(PROG (|lv| #0=#:G1453 |v| #1=#:G1454 |l| |r|)
(RETURN
(SEQ (COND
((OR (NULL (LETT |lv|
(SPADCALL |p| (|getShellEntry| $ 32))
|POLYCAT-;isTimes;SU;4|))
(NULL (SPADCALL |p| (|getShellEntry| $ 33))))
(CONS 1 "failed"))
('T
(SEQ (LETT |l|
(PROGN
(LETT #0# NIL |POLYCAT-;isTimes;SU;4|)
(SEQ (LETT |v| NIL |POLYCAT-;isTimes;SU;4|)
(LETT #1# |lv| |POLYCAT-;isTimes;SU;4|)
G190
(COND
((OR (ATOM #1#)
(PROGN
(LETT |v| (CAR #1#)
|POLYCAT-;isTimes;SU;4|)
NIL))
(GO G191)))
(SEQ (EXIT
(LETT #0#
(CONS
(SPADCALL (|spadConstant| $ 34)
|v|
(SPADCALL |p| |v|
(|getShellEntry| $ 37))
(|getShellEntry| $ 38))
#0#)
|POLYCAT-;isTimes;SU;4|)))
(LETT #1# (CDR #1#)
|POLYCAT-;isTimes;SU;4|)
(GO G190) G191 (EXIT (NREVERSE0 #0#))))
|POLYCAT-;isTimes;SU;4|)
(LETT |r| (SPADCALL |p| (|getShellEntry| $ 39))
|POLYCAT-;isTimes;SU;4|)
(EXIT (COND
((SPADCALL |r| (|spadConstant| $ 35)
(|getShellEntry| $ 40))
(COND
((NULL (CDR |lv|)) (CONS 1 "failed"))
('T (CONS 0 |l|))))
('T
(CONS 0
(CONS (SPADCALL |r|
(|getShellEntry| $ 41))
|l|))))))))))))
(DEFUN |POLYCAT-;isExpt;SU;5| (|p| $)
(PROG (|u| |d|)
(RETURN
(SEQ (LETT |u| (SPADCALL |p| (|getShellEntry| $ 43))
|POLYCAT-;isExpt;SU;5|)
(EXIT (COND
((OR (QEQCAR |u| 1)
(NULL (SPADCALL |p|
(SPADCALL (|spadConstant| $ 34)
(QCDR |u|)
(LETT |d|
(SPADCALL |p| (QCDR |u|)
(|getShellEntry| $ 37))
|POLYCAT-;isExpt;SU;5|)
(|getShellEntry| $ 38))
(|getShellEntry| $ 44))))
(CONS 1 "failed"))
('T (CONS 0 (CONS (QCDR |u|) |d|)))))))))
(DEFUN |POLYCAT-;coefficient;SVarSetNniS;6| (|p| |v| |n| $)
(SPADCALL (SPADCALL |p| |v| (|getShellEntry| $ 49)) |n|
(|getShellEntry| $ 51)))
(DEFUN |POLYCAT-;coefficient;SLLS;7| (|p| |lv| |ln| $)
(COND
((NULL |lv|)
(COND
((NULL |ln|) |p|)
('T (|error| "mismatched lists in coefficient"))))
((NULL |ln|) (|error| "mismatched lists in coefficient"))
('T
(SPADCALL
(SPADCALL
(SPADCALL |p| (|SPADfirst| |lv|) (|getShellEntry| $ 49))
(|SPADfirst| |ln|) (|getShellEntry| $ 51))
(CDR |lv|) (CDR |ln|) (|getShellEntry| $ 54)))))
(DEFUN |POLYCAT-;monomial;SLLS;8| (|p| |lv| |ln| $)
(COND
((NULL |lv|)
(COND
((NULL |ln|) |p|)
('T (|error| "mismatched lists in monomial"))))
((NULL |ln|) (|error| "mismatched lists in monomial"))
('T
(SPADCALL
(SPADCALL |p| (|SPADfirst| |lv|) (|SPADfirst| |ln|)
(|getShellEntry| $ 38))
(CDR |lv|) (CDR |ln|) (|getShellEntry| $ 56)))))
(DEFUN |POLYCAT-;retract;SVarSet;9| (|p| $)
(PROG (#0=#:G1479 |q|)
(RETURN
(SEQ (LETT |q|
(PROG2 (LETT #0# (SPADCALL |p| (|getShellEntry| $ 43))
|POLYCAT-;retract;SVarSet;9|)
(QCDR #0#)
(|check-union| (QEQCAR #0# 0) (|getShellEntry| $ 9)
#0#))
|POLYCAT-;retract;SVarSet;9|)
(EXIT (COND
((SPADCALL (SPADCALL |q| (|getShellEntry| $ 58)) |p|
(|getShellEntry| $ 44))
|q|)
('T (|error| "Polynomial is not a single variable"))))))))
(DEFUN |POLYCAT-;retractIfCan;SU;10| (|p| $)
(PROG (|q| #0=#:G1487)
(RETURN
(SEQ (EXIT (SEQ (SEQ (LETT |q|
(SPADCALL |p| (|getShellEntry| $ 43))
|POLYCAT-;retractIfCan;SU;10|)
(EXIT (COND
((QEQCAR |q| 0)
(COND
((SPADCALL
(SPADCALL (QCDR |q|)
(|getShellEntry| $ 58))
|p| (|getShellEntry| $ 44))
(PROGN
(LETT #0# |q|
|POLYCAT-;retractIfCan;SU;10|)
(GO #0#))))))))
(EXIT (CONS 1 "failed"))))
#0# (EXIT #0#)))))
(DEFUN |POLYCAT-;mkPrim| (|p| $)
(SPADCALL (|spadConstant| $ 35) (SPADCALL |p| (|getShellEntry| $ 61))
(|getShellEntry| $ 62)))
(DEFUN |POLYCAT-;primitiveMonomials;SL;12| (|p| $)
(PROG (#0=#:G1492 |q| #1=#:G1493)
(RETURN
(SEQ (PROGN
(LETT #0# NIL |POLYCAT-;primitiveMonomials;SL;12|)
(SEQ (LETT |q| NIL |POLYCAT-;primitiveMonomials;SL;12|)
(LETT #1# (SPADCALL |p| (|getShellEntry| $ 29))
|POLYCAT-;primitiveMonomials;SL;12|)
G190
(COND
((OR (ATOM #1#)
(PROGN
(LETT |q| (CAR #1#)
|POLYCAT-;primitiveMonomials;SL;12|)
NIL))
(GO G191)))
(SEQ (EXIT (LETT #0#
(CONS (|POLYCAT-;mkPrim| |q| $) #0#)
|POLYCAT-;primitiveMonomials;SL;12|)))
(LETT #1# (CDR #1#)
|POLYCAT-;primitiveMonomials;SL;12|)
(GO G190) G191 (EXIT (NREVERSE0 #0#))))))))
(DEFUN |POLYCAT-;totalDegree;SNni;13| (|p| $)
(PROG (#0=#:G1495 |d| |u|)
(RETURN
(SEQ (COND
((SPADCALL |p| (|getShellEntry| $ 64)) 0)
('T
(SEQ (LETT |u|
(SPADCALL |p|
(PROG2 (LETT #0#
(SPADCALL |p|
(|getShellEntry| $ 43))
|POLYCAT-;totalDegree;SNni;13|)
(QCDR #0#)
(|check-union| (QEQCAR #0# 0)
(|getShellEntry| $ 9) #0#))
(|getShellEntry| $ 49))
|POLYCAT-;totalDegree;SNni;13|)
(LETT |d| 0 |POLYCAT-;totalDegree;SNni;13|)
(SEQ G190
(COND
((NULL (SPADCALL |u| (|spadConstant| $ 65)
(|getShellEntry| $ 66)))
(GO G191)))
(SEQ (LETT |d|
(MAX |d|
(+
(SPADCALL |u|
(|getShellEntry| $ 67))
(SPADCALL
(SPADCALL |u|
(|getShellEntry| $ 68))
(|getShellEntry| $ 69))))
|POLYCAT-;totalDegree;SNni;13|)
(EXIT (LETT |u|
(SPADCALL |u|
(|getShellEntry| $ 70))
|POLYCAT-;totalDegree;SNni;13|)))
NIL (GO G190) G191 (EXIT NIL))
(EXIT |d|))))))))
(DEFUN |POLYCAT-;totalDegree;SLNni;14| (|p| |lv| $)
(PROG (#0=#:G1503 |v| |w| |d| |u|)
(RETURN
(SEQ (COND
((SPADCALL |p| (|getShellEntry| $ 64)) 0)
('T
(SEQ (LETT |u|
(SPADCALL |p|
(LETT |v|
(PROG2
(LETT #0#
(SPADCALL |p|
(|getShellEntry| $ 43))
|POLYCAT-;totalDegree;SLNni;14|)
(QCDR #0#)
(|check-union| (QEQCAR #0# 0)
(|getShellEntry| $ 9) #0#))
|POLYCAT-;totalDegree;SLNni;14|)
(|getShellEntry| $ 49))
|POLYCAT-;totalDegree;SLNni;14|)
(LETT |d| 0 |POLYCAT-;totalDegree;SLNni;14|)
(LETT |w| 0 |POLYCAT-;totalDegree;SLNni;14|)
(COND
((SPADCALL |v| |lv| (|getShellEntry| $ 72))
(LETT |w| 1 |POLYCAT-;totalDegree;SLNni;14|)))
(SEQ G190
(COND
((NULL (SPADCALL |u| (|spadConstant| $ 65)
(|getShellEntry| $ 66)))
(GO G191)))
(SEQ (LETT |d|
(MAX |d|
(+
(* |w|
(SPADCALL |u|
(|getShellEntry| $ 67)))
(SPADCALL
(SPADCALL |u|
(|getShellEntry| $ 68))
|lv| (|getShellEntry| $ 73))))
|POLYCAT-;totalDegree;SLNni;14|)
(EXIT (LETT |u|
(SPADCALL |u|
(|getShellEntry| $ 70))
|POLYCAT-;totalDegree;SLNni;14|)))
NIL (GO G190) G191 (EXIT NIL))
(EXIT |d|))))))))
(DEFUN |POLYCAT-;resultant;2SVarSetS;15| (|p1| |p2| |mvar| $)
(SPADCALL (SPADCALL |p1| |mvar| (|getShellEntry| $ 49))
(SPADCALL |p2| |mvar| (|getShellEntry| $ 49))
(|getShellEntry| $ 75)))
(DEFUN |POLYCAT-;discriminant;SVarSetS;16| (|p| |var| $)
(SPADCALL (SPADCALL |p| |var| (|getShellEntry| $ 49))
(|getShellEntry| $ 77)))
(DEFUN |POLYCAT-;allMonoms| (|l| $)
(PROG (#0=#:G1515 |p| #1=#:G1516)
(RETURN
(SEQ (SPADCALL
(SPADCALL
(PROGN
(LETT #0# NIL |POLYCAT-;allMonoms|)
(SEQ (LETT |p| NIL |POLYCAT-;allMonoms|)
(LETT #1# |l| |POLYCAT-;allMonoms|) G190
(COND
((OR (ATOM #1#)
(PROGN
(LETT |p| (CAR #1#)
|POLYCAT-;allMonoms|)
NIL))
(GO G191)))
(SEQ (EXIT (LETT #0#
(CONS
(SPADCALL |p|
(|getShellEntry| $ 79))
#0#)
|POLYCAT-;allMonoms|)))
(LETT #1# (CDR #1#) |POLYCAT-;allMonoms|)
(GO G190) G191 (EXIT (NREVERSE0 #0#))))
(|getShellEntry| $ 81))
(|getShellEntry| $ 82))))))
(DEFUN |POLYCAT-;P2R| (|p| |b| |n| $)
(PROG (|w| |bj| #0=#:G1521 |i| #1=#:G1520)
(RETURN
(SEQ (LETT |w|
(SPADCALL |n| (|spadConstant| $ 23)
(|getShellEntry| $ 84))
|POLYCAT-;P2R|)
(SEQ (LETT |bj| NIL |POLYCAT-;P2R|)
(LETT #0# |b| |POLYCAT-;P2R|)
(LETT |i| (SPADCALL |w| (|getShellEntry| $ 86))
|POLYCAT-;P2R|)
(LETT #1# (QVSIZE |w|) |POLYCAT-;P2R|) G190
(COND
((OR (> |i| #1#) (ATOM #0#)
(PROGN
(LETT |bj| (CAR #0#) |POLYCAT-;P2R|)
NIL))
(GO G191)))
(SEQ (EXIT (SPADCALL |w| |i|
(SPADCALL |p| |bj|
(|getShellEntry| $ 87))
(|getShellEntry| $ 88))))
(LETT |i|
(PROG1 (+ |i| 1)
(LETT #0# (CDR #0#) |POLYCAT-;P2R|))
|POLYCAT-;P2R|)
(GO G190) G191 (EXIT NIL))
(EXIT |w|)))))
(DEFUN |POLYCAT-;eq2R| (|l| |b| $)
(PROG (#0=#:G1525 |bj| #1=#:G1526 #2=#:G1527 |p| #3=#:G1528)
(RETURN
(SEQ (SPADCALL
(PROGN
(LETT #0# NIL |POLYCAT-;eq2R|)
(SEQ (LETT |bj| NIL |POLYCAT-;eq2R|)
(LETT #1# |b| |POLYCAT-;eq2R|) G190
(COND
((OR (ATOM #1#)
(PROGN
(LETT |bj| (CAR #1#) |POLYCAT-;eq2R|)
NIL))
(GO G191)))
(SEQ (EXIT (LETT #0#
(CONS
(PROGN
(LETT #2# NIL
|POLYCAT-;eq2R|)
(SEQ
(LETT |p| NIL
|POLYCAT-;eq2R|)
(LETT #3# |l|
|POLYCAT-;eq2R|)
G190
(COND
((OR (ATOM #3#)
(PROGN
(LETT |p| (CAR #3#)
|POLYCAT-;eq2R|)
NIL))
(GO G191)))
(SEQ
(EXIT
(LETT #2#
(CONS
(SPADCALL |p| |bj|
(|getShellEntry| $ 87))
#2#)
|POLYCAT-;eq2R|)))
(LETT #3# (CDR #3#)
|POLYCAT-;eq2R|)
(GO G190) G191
(EXIT (NREVERSE0 #2#))))
#0#)
|POLYCAT-;eq2R|)))
(LETT #1# (CDR #1#) |POLYCAT-;eq2R|) (GO G190)
G191 (EXIT (NREVERSE0 #0#))))
(|getShellEntry| $ 92))))))
(DEFUN |POLYCAT-;reducedSystem;MM;20| (|m| $)
(PROG (#0=#:G1537 |r| #1=#:G1538 |b| #2=#:G1539 |bj| #3=#:G1540 |d|
|mm| |l|)
(RETURN
(SEQ (LETT |l| (SPADCALL |m| (|getShellEntry| $ 95))
|POLYCAT-;reducedSystem;MM;20|)
(LETT |b|
(SPADCALL
(SPADCALL
(PROGN
(LETT #0# NIL
|POLYCAT-;reducedSystem;MM;20|)
(SEQ (LETT |r| NIL
|POLYCAT-;reducedSystem;MM;20|)
(LETT #1# |l|
|POLYCAT-;reducedSystem;MM;20|)
G190
(COND
((OR (ATOM #1#)
(PROGN
(LETT |r| (CAR #1#)
|POLYCAT-;reducedSystem;MM;20|)
NIL))
(GO G191)))
(SEQ (EXIT
(LETT #0#
(CONS
(|POLYCAT-;allMonoms| |r| $)
#0#)
|POLYCAT-;reducedSystem;MM;20|)))
(LETT #1# (CDR #1#)
|POLYCAT-;reducedSystem;MM;20|)
(GO G190) G191 (EXIT (NREVERSE0 #0#))))
(|getShellEntry| $ 81))
(|getShellEntry| $ 82))
|POLYCAT-;reducedSystem;MM;20|)
(LETT |d|
(PROGN
(LETT #2# NIL |POLYCAT-;reducedSystem;MM;20|)
(SEQ (LETT |bj| NIL |POLYCAT-;reducedSystem;MM;20|)
(LETT #3# |b| |POLYCAT-;reducedSystem;MM;20|)
G190
(COND
((OR (ATOM #3#)
(PROGN
(LETT |bj| (CAR #3#)
|POLYCAT-;reducedSystem;MM;20|)
NIL))
(GO G191)))
(SEQ (EXIT (LETT #2#
(CONS
(SPADCALL |bj|
(|getShellEntry| $ 61))
#2#)
|POLYCAT-;reducedSystem;MM;20|)))
(LETT #3# (CDR #3#)
|POLYCAT-;reducedSystem;MM;20|)
(GO G190) G191 (EXIT (NREVERSE0 #2#))))
|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 (SPADCALL (NULL |l|) (|getShellEntry| $ 96)))
(GO G191)))
(SEQ (LETT |mm|
(SPADCALL |mm|
(|POLYCAT-;eq2R| (|SPADfirst| |l|) |d|
$)
(|getShellEntry| $ 97))
|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 (#0=#:G1551 |s| #1=#:G1552 |b| #2=#:G1553 |bj| #3=#:G1554 |d|
|n| |mm| |w| |l| |r|)
(RETURN
(SEQ (LETT |l| (SPADCALL |m| (|getShellEntry| $ 95))
|POLYCAT-;reducedSystem;MVR;21|)
(LETT |r| (SPADCALL |v| (|getShellEntry| $ 101))
|POLYCAT-;reducedSystem;MVR;21|)
(LETT |b|
(SPADCALL
(SPADCALL (|POLYCAT-;allMonoms| |r| $)
(SPADCALL
(PROGN
(LETT #0# NIL
|POLYCAT-;reducedSystem;MVR;21|)
(SEQ (LETT |s| NIL
|POLYCAT-;reducedSystem;MVR;21|)
(LETT #1# |l|
|POLYCAT-;reducedSystem;MVR;21|)
G190
(COND
((OR (ATOM #1#)
(PROGN
(LETT |s| (CAR #1#)
|POLYCAT-;reducedSystem;MVR;21|)
NIL))
(GO G191)))
(SEQ
(EXIT
(LETT #0#
(CONS
(|POLYCAT-;allMonoms| |s| $)
#0#)
|POLYCAT-;reducedSystem;MVR;21|)))
(LETT #1# (CDR #1#)
|POLYCAT-;reducedSystem;MVR;21|)
(GO G190) G191
(EXIT (NREVERSE0 #0#))))
(|getShellEntry| $ 81))
(|getShellEntry| $ 102))
(|getShellEntry| $ 82))
|POLYCAT-;reducedSystem;MVR;21|)
(LETT |d|
(PROGN
(LETT #2# NIL |POLYCAT-;reducedSystem;MVR;21|)
(SEQ (LETT |bj| NIL |POLYCAT-;reducedSystem;MVR;21|)
(LETT #3# |b| |POLYCAT-;reducedSystem;MVR;21|)
G190
(COND
((OR (ATOM #3#)
(PROGN
(LETT |bj| (CAR #3#)
|POLYCAT-;reducedSystem;MVR;21|)
NIL))
(GO G191)))
(SEQ (EXIT (LETT #2#
(CONS
(SPADCALL |bj|
(|getShellEntry| $ 61))
#2#)
|POLYCAT-;reducedSystem;MVR;21|)))
(LETT #3# (CDR #3#)
|POLYCAT-;reducedSystem;MVR;21|)
(GO G190) G191 (EXIT (NREVERSE0 #2#))))
|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 (SPADCALL (NULL |l|) (|getShellEntry| $ 96)))
(GO G191)))
(SEQ (LETT |mm|
(SPADCALL |mm|
(|POLYCAT-;eq2R| (|SPADfirst| |l|) |d|
$)
(|getShellEntry| $ 97))
|POLYCAT-;reducedSystem;MVR;21|)
(LETT |w|
(SPADCALL |w|
(|POLYCAT-;P2R| (|SPADfirst| |r|) |d|
|n| $)
(|getShellEntry| $ 103))
|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| (|getShellEntry| $ 108)))
(DEFUN |POLYCAT-;solveLinearPolynomialEquation;LSupU;23| (|lpp| |pp| $)
(SPADCALL |lpp| |pp| (|getShellEntry| $ 113)))
(DEFUN |POLYCAT-;factorPolynomial;SupF;24| (|pp| $)
(SPADCALL |pp| (|getShellEntry| $ 118)))
(DEFUN |POLYCAT-;factorSquareFreePolynomial;SupF;25| (|pp| $)
(SPADCALL |pp| (|getShellEntry| $ 121)))
(DEFUN |POLYCAT-;factor;SF;26| (|p| $)
(PROG (|v| |ansR| #0=#:G1596 |w| #1=#:G1597 |up| |ansSUP| #2=#:G1598
|ww| #3=#:G1599)
(RETURN
(SEQ (LETT |v| (SPADCALL |p| (|getShellEntry| $ 43))
|POLYCAT-;factor;SF;26|)
(EXIT (COND
((QEQCAR |v| 1)
(SEQ (LETT |ansR|
(SPADCALL
(SPADCALL |p|
(|getShellEntry| $ 39))
(|getShellEntry| $ 124))
|POLYCAT-;factor;SF;26|)
(EXIT (SPADCALL
(SPADCALL
(SPADCALL |ansR|
(|getShellEntry| $ 126))
(|getShellEntry| $ 41))
(PROGN
(LETT #0# NIL
|POLYCAT-;factor;SF;26|)
(SEQ
(LETT |w| NIL
|POLYCAT-;factor;SF;26|)
(LETT #1#
(SPADCALL |ansR|
(|getShellEntry| $ 130))
|POLYCAT-;factor;SF;26|)
G190
(COND
((OR (ATOM #1#)
(PROGN
(LETT |w| (CAR #1#)
|POLYCAT-;factor;SF;26|)
NIL))
(GO G191)))
(SEQ
(EXIT
(LETT #0#
(CONS
(VECTOR (QVELT |w| 0)
(SPADCALL (QVELT |w| 1)
(|getShellEntry| $ 41))
(QVELT |w| 2))
#0#)
|POLYCAT-;factor;SF;26|)))
(LETT #1# (CDR #1#)
|POLYCAT-;factor;SF;26|)
(GO G190) G191
(EXIT (NREVERSE0 #0#))))
(|getShellEntry| $ 134)))))
('T
(SEQ (LETT |up|
(SPADCALL |p| (QCDR |v|)
(|getShellEntry| $ 49))
|POLYCAT-;factor;SF;26|)
(LETT |ansSUP|
(SPADCALL |up| (|getShellEntry| $ 118))
|POLYCAT-;factor;SF;26|)
(EXIT (SPADCALL
(SPADCALL
(SPADCALL |ansSUP|
(|getShellEntry| $ 135))
(QCDR |v|) (|getShellEntry| $ 136))
(PROGN
(LETT #2# NIL
|POLYCAT-;factor;SF;26|)
(SEQ
(LETT |ww| NIL
|POLYCAT-;factor;SF;26|)
(LETT #3#
(SPADCALL |ansSUP|
(|getShellEntry| $ 139))
|POLYCAT-;factor;SF;26|)
G190
(COND
((OR (ATOM #3#)
(PROGN
(LETT |ww| (CAR #3#)
|POLYCAT-;factor;SF;26|)
NIL))
(GO G191)))
(SEQ
(EXIT
(LETT #2#
(CONS
(VECTOR (QVELT |ww| 0)
(SPADCALL (QVELT |ww| 1)
(QCDR |v|)
(|getShellEntry| $ 136))
(QVELT |ww| 2))
#2#)
|POLYCAT-;factor;SF;26|)))
(LETT #3# (CDR #3#)
|POLYCAT-;factor;SF;26|)
(GO G190) G191
(EXIT (NREVERSE0 #2#))))
(|getShellEntry| $ 134)))))))))))
(DEFUN |POLYCAT-;conditionP;MU;27| (|mat| $)
(PROG (|ll| #0=#:G1634 |z| #1=#:G1635 |ch| |l| #2=#:G1636 #3=#:G1637
#4=#:G1606 #5=#:G1604 #6=#:G1605 #7=#:G1638 |vars| |degs|
#8=#:G1639 |d| #9=#:G1640 |nd| #10=#:G1633 #11=#:G1613
|deg1| |redmons| #12=#:G1641 |v| #13=#:G1643 |u|
#14=#:G1642 |llR| |monslist| |ans| #15=#:G1644
#16=#:G1645 |mons| #17=#:G1646 |m| #18=#:G1647 |i|
#19=#:G1629 #20=#:G1627 #21=#:G1628)
(RETURN
(SEQ (EXIT (SEQ (LETT |ll|
(SPADCALL
(SPADCALL |mat|
(|getShellEntry| $ 141))
(|getShellEntry| $ 95))
|POLYCAT-;conditionP;MU;27|)
(LETT |llR|
(PROGN
(LETT #0# NIL
|POLYCAT-;conditionP;MU;27|)
(SEQ (LETT |z| NIL
|POLYCAT-;conditionP;MU;27|)
(LETT #1# (|SPADfirst| |ll|)
|POLYCAT-;conditionP;MU;27|)
G190
(COND
((OR (ATOM #1#)
(PROGN
(LETT |z| (CAR #1#)
|POLYCAT-;conditionP;MU;27|)
NIL))
(GO G191)))
(SEQ
(EXIT
(LETT #0# (CONS NIL #0#)
|POLYCAT-;conditionP;MU;27|)))
(LETT #1# (CDR #1#)
|POLYCAT-;conditionP;MU;27|)
(GO G190) G191
(EXIT (NREVERSE0 #0#))))
|POLYCAT-;conditionP;MU;27|)
(LETT |monslist| NIL |POLYCAT-;conditionP;MU;27|)
(LETT |ch| (SPADCALL (|getShellEntry| $ 142))
|POLYCAT-;conditionP;MU;27|)
(SEQ (LETT |l| NIL |POLYCAT-;conditionP;MU;27|)
(LETT #2# |ll| |POLYCAT-;conditionP;MU;27|)
G190
(COND
((OR (ATOM #2#)
(PROGN
(LETT |l| (CAR #2#)
|POLYCAT-;conditionP;MU;27|)
NIL))
(GO G191)))
(SEQ (LETT |mons|
(PROGN
(LETT #6# NIL
|POLYCAT-;conditionP;MU;27|)
(SEQ
(LETT |u| NIL
|POLYCAT-;conditionP;MU;27|)
(LETT #3# |l|
|POLYCAT-;conditionP;MU;27|)
G190
(COND
((OR (ATOM #3#)
(PROGN
(LETT |u| (CAR #3#)
|POLYCAT-;conditionP;MU;27|)
NIL))
(GO G191)))
(SEQ
(EXIT
(PROGN
(LETT #4#
(SPADCALL |u|
(|getShellEntry| $ 79))
|POLYCAT-;conditionP;MU;27|)
(COND
(#6#
(LETT #5#
(SPADCALL #5# #4#
(|getShellEntry| $
143))
|POLYCAT-;conditionP;MU;27|))
('T
(PROGN
(LETT #5# #4#
|POLYCAT-;conditionP;MU;27|)
(LETT #6# 'T
|POLYCAT-;conditionP;MU;27|)))))))
(LETT #3# (CDR #3#)
|POLYCAT-;conditionP;MU;27|)
(GO G190) G191 (EXIT NIL))
(COND
(#6# #5#)
('T
(|IdentityError|
'|setUnion|))))
|POLYCAT-;conditionP;MU;27|)
(LETT |redmons| NIL
|POLYCAT-;conditionP;MU;27|)
(SEQ (LETT |m| NIL
|POLYCAT-;conditionP;MU;27|)
(LETT #7# |mons|
|POLYCAT-;conditionP;MU;27|)
G190
(COND
((OR (ATOM #7#)
(PROGN
(LETT |m| (CAR #7#)
|POLYCAT-;conditionP;MU;27|)
NIL))
(GO G191)))
(SEQ
(LETT |vars|
(SPADCALL |m|
(|getShellEntry| $ 32))
|POLYCAT-;conditionP;MU;27|)
(LETT |degs|
(SPADCALL |m| |vars|
(|getShellEntry| $ 144))
|POLYCAT-;conditionP;MU;27|)
(LETT |deg1|
(PROGN
(LETT #8# NIL
|POLYCAT-;conditionP;MU;27|)
(SEQ
(LETT |d| NIL
|POLYCAT-;conditionP;MU;27|)
(LETT #9# |degs|
|POLYCAT-;conditionP;MU;27|)
G190
(COND
((OR (ATOM #9#)
(PROGN
(LETT |d| (CAR #9#)
|POLYCAT-;conditionP;MU;27|)
NIL))
(GO G191)))
(SEQ
(EXIT
(LETT #8#
(CONS
(SEQ
(LETT |nd|
(SPADCALL |d| |ch|
(|getShellEntry| $
146))
|POLYCAT-;conditionP;MU;27|)
(EXIT
(COND
((QEQCAR |nd| 1)
(PROGN
(LETT #10#
(CONS 1 "failed")
|POLYCAT-;conditionP;MU;27|)
(GO #10#)))
('T
(PROG1
(LETT #11#
(QCDR |nd|)
|POLYCAT-;conditionP;MU;27|)
(|check-subtype|
(>= #11# 0)
'(|NonNegativeInteger|)
#11#))))))
#8#)
|POLYCAT-;conditionP;MU;27|)))
(LETT #9# (CDR #9#)
|POLYCAT-;conditionP;MU;27|)
(GO G190) G191
(EXIT (NREVERSE0 #8#))))
|POLYCAT-;conditionP;MU;27|)
(LETT |redmons|
(CONS
(SPADCALL (|spadConstant| $ 34)
|vars| |deg1|
(|getShellEntry| $ 56))
|redmons|)
|POLYCAT-;conditionP;MU;27|)
(EXIT
(LETT |llR|
(PROGN
(LETT #12# NIL
|POLYCAT-;conditionP;MU;27|)
(SEQ
(LETT |v| NIL
|POLYCAT-;conditionP;MU;27|)
(LETT #13# |llR|
|POLYCAT-;conditionP;MU;27|)
(LETT |u| NIL
|POLYCAT-;conditionP;MU;27|)
(LETT #14# |l|
|POLYCAT-;conditionP;MU;27|)
G190
(COND
((OR (ATOM #14#)
(PROGN
(LETT |u| (CAR #14#)
|POLYCAT-;conditionP;MU;27|)
NIL)
(ATOM #13#)
(PROGN
(LETT |v| (CAR #13#)
|POLYCAT-;conditionP;MU;27|)
NIL))
(GO G191)))
(SEQ
(EXIT
(LETT #12#
(CONS
(CONS
(SPADCALL
(SPADCALL |u| |vars|
|degs|
(|getShellEntry| $
54))
(|getShellEntry| $
147))
|v|)
#12#)
|POLYCAT-;conditionP;MU;27|)))
(LETT #14#
(PROG1 (CDR #14#)
(LETT #13# (CDR #13#)
|POLYCAT-;conditionP;MU;27|))
|POLYCAT-;conditionP;MU;27|)
(GO G190) G191
(EXIT (NREVERSE0 #12#))))
|POLYCAT-;conditionP;MU;27|)))
(LETT #7# (CDR #7#)
|POLYCAT-;conditionP;MU;27|)
(GO G190) G191 (EXIT NIL))
(EXIT (LETT |monslist|
(CONS |redmons| |monslist|)
|POLYCAT-;conditionP;MU;27|)))
(LETT #2# (CDR #2#)
|POLYCAT-;conditionP;MU;27|)
(GO G190) G191 (EXIT NIL))
(LETT |ans|
(SPADCALL
(SPADCALL
(SPADCALL |llR|
(|getShellEntry| $ 92))
(|getShellEntry| $ 148))
(|getShellEntry| $ 150))
|POLYCAT-;conditionP;MU;27|)
(EXIT (COND
((QEQCAR |ans| 1) (CONS 1 "failed"))
('T
(SEQ (LETT |i| 0
|POLYCAT-;conditionP;MU;27|)
(EXIT
(CONS 0
(PRIMVEC2ARR
(PROGN
(LETT #15#
(GETREFV (SIZE |monslist|))
|POLYCAT-;conditionP;MU;27|)
(SEQ
(LETT #16# 0
|POLYCAT-;conditionP;MU;27|)
(LETT |mons| NIL
|POLYCAT-;conditionP;MU;27|)
(LETT #17# |monslist|
|POLYCAT-;conditionP;MU;27|)
G190
(COND
((OR (ATOM #17#)
(PROGN
(LETT |mons| (CAR #17#)
|POLYCAT-;conditionP;MU;27|)
NIL))
(GO G191)))
(SEQ
(EXIT
(SETELT #15# #16#
(PROGN
(LETT #21# NIL
|POLYCAT-;conditionP;MU;27|)
(SEQ
(LETT |m| NIL
|POLYCAT-;conditionP;MU;27|)
(LETT #18# |mons|
|POLYCAT-;conditionP;MU;27|)
G190
(COND
((OR (ATOM #18#)
(PROGN
(LETT |m|
(CAR #18#)
|POLYCAT-;conditionP;MU;27|)
NIL))
(GO G191)))
(SEQ
(EXIT
(PROGN
(LETT #19#
(SPADCALL |m|
(SPADCALL
(SPADCALL
(QCDR |ans|)
(LETT |i|
(+ |i| 1)
|POLYCAT-;conditionP;MU;27|)
(|getShellEntry|
$ 151))
(|getShellEntry|
$ 41))
(|getShellEntry|
$ 152))
|POLYCAT-;conditionP;MU;27|)
(COND
(#21#
(LETT #20#
(SPADCALL #20#
#19#
(|getShellEntry|
$ 153))
|POLYCAT-;conditionP;MU;27|))
('T
(PROGN
(LETT #20#
#19#
|POLYCAT-;conditionP;MU;27|)
(LETT #21# 'T
|POLYCAT-;conditionP;MU;27|)))))))
(LETT #18# (CDR #18#)
|POLYCAT-;conditionP;MU;27|)
(GO G190) G191
(EXIT NIL))
(COND
(#21# #20#)
('T
(|spadConstant| $ 22)))))))
(LETT #17#
(PROG1 (CDR #17#)
(LETT #16# (QSADD1 #16#)
|POLYCAT-;conditionP;MU;27|))
|POLYCAT-;conditionP;MU;27|)
(GO G190) G191 (EXIT NIL))
#15#))))))))))
#10# (EXIT #10#)))))
(DEFUN |POLYCAT-;charthRoot;SU;28| (|p| $)
(PROG (|vars| |ans| |ch|)
(RETURN
(SEQ (LETT |vars| (SPADCALL |p| (|getShellEntry| $ 32))
|POLYCAT-;charthRoot;SU;28|)
(EXIT (COND
((NULL |vars|)
(SEQ (LETT |ans|
(SPADCALL
(SPADCALL |p|
(|getShellEntry| $ 147))
(|getShellEntry| $ 155))
|POLYCAT-;charthRoot;SU;28|)
(EXIT (COND
((QEQCAR |ans| 1) (CONS 1 "failed"))
('T
(CONS 0
(SPADCALL (QCDR |ans|)
(|getShellEntry| $ 41))))))))
('T
(SEQ (LETT |ch| (SPADCALL (|getShellEntry| $ 142))
|POLYCAT-;charthRoot;SU;28|)
(EXIT (|POLYCAT-;charthRootlv| |p| |vars| |ch|
$))))))))))
(DEFUN |POLYCAT-;charthRootlv| (|p| |vars| |ch| $)
(PROG (|v| |dd| |cp| |d| #0=#:G1668 |ans| |ansx| #1=#:G1675)
(RETURN
(SEQ (EXIT (COND
((NULL |vars|)
(SEQ (LETT |ans|
(SPADCALL
(SPADCALL |p|
(|getShellEntry| $ 147))
(|getShellEntry| $ 155))
|POLYCAT-;charthRootlv|)
(EXIT (COND
((QEQCAR |ans| 1) (CONS 1 "failed"))
('T
(CONS 0
(SPADCALL (QCDR |ans|)
(|getShellEntry| $ 41))))))))
('T
(SEQ (LETT |v| (|SPADfirst| |vars|)
|POLYCAT-;charthRootlv|)
(LETT |vars| (CDR |vars|)
|POLYCAT-;charthRootlv|)
(LETT |d|
(SPADCALL |p| |v|
(|getShellEntry| $ 37))
|POLYCAT-;charthRootlv|)
(LETT |ans| (|spadConstant| $ 22)
|POLYCAT-;charthRootlv|)
(SEQ G190 (COND ((NULL (< 0 |d|)) (GO G191)))
(SEQ (LETT |dd|
(SPADCALL |d| |ch|
(|getShellEntry| $ 146))
|POLYCAT-;charthRootlv|)
(EXIT
(COND
((QEQCAR |dd| 1)
(PROGN
(LETT #1# (CONS 1 "failed")
|POLYCAT-;charthRootlv|)
(GO #1#)))
('T
(SEQ
(LETT |cp|
(SPADCALL |p| |v| |d|
(|getShellEntry| $ 158))
|POLYCAT-;charthRootlv|)
(LETT |p|
(SPADCALL |p|
(SPADCALL |cp| |v| |d|
(|getShellEntry| $ 38))
(|getShellEntry| $ 159))
|POLYCAT-;charthRootlv|)
(LETT |ansx|
(|POLYCAT-;charthRootlv| |cp|
|vars| |ch| $)
|POLYCAT-;charthRootlv|)
(EXIT
(COND
((QEQCAR |ansx| 1)
(PROGN
(LETT #1#
(CONS 1 "failed")
|POLYCAT-;charthRootlv|)
(GO #1#)))
('T
(SEQ
(LETT |d|
(SPADCALL |p| |v|
(|getShellEntry| $ 37))
|POLYCAT-;charthRootlv|)
(EXIT
(LETT |ans|
(SPADCALL |ans|
(SPADCALL (QCDR |ansx|)
|v|
(PROG1
(LETT #0# (QCDR |dd|)
|POLYCAT-;charthRootlv|)
(|check-subtype|
(>= #0# 0)
'(|NonNegativeInteger|)
#0#))
(|getShellEntry| $ 38))
(|getShellEntry| $ 153))
|POLYCAT-;charthRootlv|)))))))))))
NIL (GO G190) G191 (EXIT NIL))
(LETT |ansx|
(|POLYCAT-;charthRootlv| |p| |vars| |ch|
$)
|POLYCAT-;charthRootlv|)
(EXIT (COND
((QEQCAR |ansx| 1)
(PROGN
(LETT #1# (CONS 1 "failed")
|POLYCAT-;charthRootlv|)
(GO #1#)))
('T
(PROGN
(LETT #1#
(CONS 0
(SPADCALL |ans| (QCDR |ansx|)
(|getShellEntry| $ 153)))
|POLYCAT-;charthRootlv|)
(GO #1#)))))))))
#1# (EXIT #1#)))))
(DEFUN |POLYCAT-;monicDivide;2SVarSetR;30| (|p1| |p2| |mvar| $)
(PROG (|result|)
(RETURN
(SEQ (LETT |result|
(SPADCALL
(SPADCALL |p1| |mvar| (|getShellEntry| $ 49))
(SPADCALL |p2| |mvar| (|getShellEntry| $ 49))
(|getShellEntry| $ 161))
|POLYCAT-;monicDivide;2SVarSetR;30|)
(EXIT (CONS (SPADCALL (QCAR |result|) |mvar|
(|getShellEntry| $ 136))
(SPADCALL (QCDR |result|) |mvar|
(|getShellEntry| $ 136))))))))
(DEFUN |POLYCAT-;squareFree;SF;31| (|p| $)
(SPADCALL |p| (|getShellEntry| $ 164)))
(DEFUN |POLYCAT-;squareFree;SF;32| (|p| $)
(SPADCALL |p| (|getShellEntry| $ 167)))
(DEFUN |POLYCAT-;squareFree;SF;33| (|p| $)
(SPADCALL |p| (|getShellEntry| $ 167)))
(DEFUN |POLYCAT-;squareFreePart;2S;34| (|p| $)
(PROG (|s| |f| #0=#:G1691 #1=#:G1689 #2=#:G1687 #3=#:G1688)
(RETURN
(SEQ (SPADCALL
(SPADCALL
(LETT |s| (SPADCALL |p| (|getShellEntry| $ 168))
|POLYCAT-;squareFreePart;2S;34|)
(|getShellEntry| $ 169))
(PROGN
(LETT #3# NIL |POLYCAT-;squareFreePart;2S;34|)
(SEQ (LETT |f| NIL |POLYCAT-;squareFreePart;2S;34|)
(LETT #0# (SPADCALL |s| (|getShellEntry| $ 172))
|POLYCAT-;squareFreePart;2S;34|)
G190
(COND
((OR (ATOM #0#)
(PROGN
(LETT |f| (CAR #0#)
|POLYCAT-;squareFreePart;2S;34|)
NIL))
(GO G191)))
(SEQ (EXIT (PROGN
(LETT #1# (QCAR |f|)
|POLYCAT-;squareFreePart;2S;34|)
(COND
(#3#
(LETT #2#
(SPADCALL #2# #1#
(|getShellEntry| $ 152))
|POLYCAT-;squareFreePart;2S;34|))
('T
(PROGN
(LETT #2# #1#
|POLYCAT-;squareFreePart;2S;34|)
(LETT #3# 'T
|POLYCAT-;squareFreePart;2S;34|)))))))
(LETT #0# (CDR #0#)
|POLYCAT-;squareFreePart;2S;34|)
(GO G190) G191 (EXIT NIL))
(COND (#3# #2#) ('T (|spadConstant| $ 34))))
(|getShellEntry| $ 152))))))
(DEFUN |POLYCAT-;content;SVarSetS;35| (|p| |v| $)
(SPADCALL (SPADCALL |p| |v| (|getShellEntry| $ 49))
(|getShellEntry| $ 174)))
(DEFUN |POLYCAT-;primitivePart;2S;36| (|p| $)
(PROG (#0=#:G1694)
(RETURN
(QVELT (SPADCALL
(PROG2 (LETT #0#
(SPADCALL |p|
(SPADCALL |p|
(|getShellEntry| $ 176))
(|getShellEntry| $ 177))
|POLYCAT-;primitivePart;2S;36|)
(QCDR #0#)
(|check-union| (QEQCAR #0# 0) (|getShellEntry| $ 6)
#0#))
(|getShellEntry| $ 179))
1))))
(DEFUN |POLYCAT-;primitivePart;SVarSetS;37| (|p| |v| $)
(PROG (#0=#:G1700)
(RETURN
(QVELT (SPADCALL
(PROG2 (LETT #0#
(SPADCALL |p|
(SPADCALL |p| |v|
(|getShellEntry| $ 181))
(|getShellEntry| $ 182))
|POLYCAT-;primitivePart;SVarSetS;37|)
(QCDR #0#)
(|check-union| (QEQCAR #0# 0) (|getShellEntry| $ 6)
#0#))
(|getShellEntry| $ 179))
1))))
(DEFUN |POLYCAT-;<;2SB;38| (|p| |q| $)
(PROG (|dp| |dq|)
(RETURN
(SEQ (LETT |dp| (SPADCALL |p| (|getShellEntry| $ 61))
|POLYCAT-;<;2SB;38|)
(LETT |dq| (SPADCALL |q| (|getShellEntry| $ 61))
|POLYCAT-;<;2SB;38|)
(EXIT (COND
((SPADCALL |dp| |dq| (|getShellEntry| $ 184))
(SPADCALL (|spadConstant| $ 23)
(SPADCALL |q| (|getShellEntry| $ 39))
(|getShellEntry| $ 185)))
((SPADCALL |dq| |dp| (|getShellEntry| $ 184))
(SPADCALL (SPADCALL |p| (|getShellEntry| $ 39))
(|spadConstant| $ 23) (|getShellEntry| $ 185)))
('T
(SPADCALL
(SPADCALL (SPADCALL |p| |q|
(|getShellEntry| $ 159))
(|getShellEntry| $ 39))
(|spadConstant| $ 23) (|getShellEntry| $ 185)))))))))
(DEFUN |POLYCAT-;patternMatch;SP2Pmr;39| (|p| |pat| |l| $)
(SPADCALL |p| |pat| |l| (|getShellEntry| $ 190)))
(DEFUN |POLYCAT-;patternMatch;SP2Pmr;40| (|p| |pat| |l| $)
(SPADCALL |p| |pat| |l| (|getShellEntry| $ 197)))
(DEFUN |POLYCAT-;convert;SP;41| (|x| $)
(SPADCALL (ELT $ 200) (ELT $ 201) |x| (|getShellEntry| $ 205)))
(DEFUN |POLYCAT-;convert;SP;42| (|x| $)
(SPADCALL (ELT $ 207) (ELT $ 208) |x| (|getShellEntry| $ 212)))
(DEFUN |POLYCAT-;convert;SIf;43| (|p| $)
(SPADCALL (ELT $ 215) (ELT $ 216) |p| (|getShellEntry| $ 220)))
(DEFUN |PolynomialCategory&| (|#1| |#2| |#3| |#4|)
(PROG (|dv$1| |dv$2| |dv$3| |dv$4| |dv$| $ |pv$|)
(RETURN
(PROGN
(LETT |dv$1| (|devaluate| |#1|) . #0=(|PolynomialCategory&|))
(LETT |dv$2| (|devaluate| |#2|) . #0#)
(LETT |dv$3| (|devaluate| |#3|) . #0#)
(LETT |dv$4| (|devaluate| |#4|) . #0#)
(LETT |dv$|
(LIST '|PolynomialCategory&| |dv$1| |dv$2| |dv$3| |dv$4|) . #0#)
(LETT $ (|newShell| 229) . #0#)
(|setShellEntry| $ 0 |dv$|)
(|setShellEntry| $ 3
(LETT |pv$|
(|buildPredVector| 0 0
(LIST (|HasCategory| |#2|
'(|PolynomialFactorizationExplicit|))
(|HasAttribute| |#2|
'|canonicalUnitNormal|)
(|HasCategory| |#2| '(|GcdDomain|))
(|HasCategory| |#2| '(|CommutativeRing|))
(|HasCategory| |#4|
'(|PatternMatchable| (|Float|)))
(|HasCategory| |#2|
'(|PatternMatchable| (|Float|)))
(|HasCategory| |#4|
'(|PatternMatchable| (|Integer|)))
(|HasCategory| |#2|
'(|PatternMatchable| (|Integer|)))
(|HasCategory| |#4|
'(|ConvertibleTo|
(|Pattern| (|Float|))))
(|HasCategory| |#2|
'(|ConvertibleTo|
(|Pattern| (|Float|))))
(|HasCategory| |#4|
'(|ConvertibleTo|
(|Pattern| (|Integer|))))
(|HasCategory| |#2|
'(|ConvertibleTo|
(|Pattern| (|Integer|))))
(|HasCategory| |#4|
'(|ConvertibleTo| (|InputForm|)))
(|HasCategory| |#2|
'(|ConvertibleTo| (|InputForm|)))
(|HasCategory| |#2| '(|OrderedSet|)))) . #0#))
(|stuffDomainSlots| $)
(|setShellEntry| $ 6 |#1|)
(|setShellEntry| $ 7 |#2|)
(|setShellEntry| $ 8 |#3|)
(|setShellEntry| $ 9 |#4|)
(COND
((|testBitVector| |pv$| 4)
(PROGN
(|setShellEntry| $ 76
(CONS (|dispatchFunction|
|POLYCAT-;resultant;2SVarSetS;15|)
$))
(|setShellEntry| $ 78
(CONS (|dispatchFunction|
|POLYCAT-;discriminant;SVarSetS;16|)
$)))))
(COND
((|HasCategory| |#2| '(|IntegralDomain|))
(PROGN
(|setShellEntry| $ 99
(CONS (|dispatchFunction|
|POLYCAT-;reducedSystem;MM;20|)
$))
(|setShellEntry| $ 106
(CONS (|dispatchFunction|
|POLYCAT-;reducedSystem;MVR;21|)
$)))))
(COND
((|testBitVector| |pv$| 1)
(PROGN
(|setShellEntry| $ 109
(CONS (|dispatchFunction|
|POLYCAT-;gcdPolynomial;3Sup;22|)
$))
(|setShellEntry| $ 116
(CONS (|dispatchFunction|
|POLYCAT-;solveLinearPolynomialEquation;LSupU;23|)
$))
(|setShellEntry| $ 120
(CONS (|dispatchFunction|
|POLYCAT-;factorPolynomial;SupF;24|)
$))
(|setShellEntry| $ 122
(CONS (|dispatchFunction|
|POLYCAT-;factorSquareFreePolynomial;SupF;25|)
$))
(|setShellEntry| $ 140
(CONS (|dispatchFunction| |POLYCAT-;factor;SF;26|) $))
(COND
((|HasCategory| |#2| '(|CharacteristicNonZero|))
(PROGN
(|setShellEntry| $ 154
(CONS (|dispatchFunction|
|POLYCAT-;conditionP;MU;27|)
$))))))))
(COND
((|HasCategory| |#2| '(|CharacteristicNonZero|))
(PROGN
(|setShellEntry| $ 156
(CONS (|dispatchFunction| |POLYCAT-;charthRoot;SU;28|)
$)))))
(COND
((|testBitVector| |pv$| 3)
(PROGN
(COND
((|HasCategory| |#2| '(|EuclideanDomain|))
(COND
((|HasCategory| |#2| '(|CharacteristicZero|))
(|setShellEntry| $ 165
(CONS (|dispatchFunction|
|POLYCAT-;squareFree;SF;31|)
$)))
('T
(|setShellEntry| $ 165
(CONS (|dispatchFunction|
|POLYCAT-;squareFree;SF;32|)
$)))))
('T
(|setShellEntry| $ 165
(CONS (|dispatchFunction|
|POLYCAT-;squareFree;SF;33|)
$))))
(|setShellEntry| $ 173
(CONS (|dispatchFunction|
|POLYCAT-;squareFreePart;2S;34|)
$))
(|setShellEntry| $ 175
(CONS (|dispatchFunction|
|POLYCAT-;content;SVarSetS;35|)
$))
(|setShellEntry| $ 180
(CONS (|dispatchFunction|
|POLYCAT-;primitivePart;2S;36|)
$))
(|setShellEntry| $ 183
(CONS (|dispatchFunction|
|POLYCAT-;primitivePart;SVarSetS;37|)
$)))))
(COND
((|testBitVector| |pv$| 15)
(PROGN
(|setShellEntry| $ 186
(CONS (|dispatchFunction| |POLYCAT-;<;2SB;38|) $))
(COND
((|testBitVector| |pv$| 8)
(COND
((|testBitVector| |pv$| 7)
(|setShellEntry| $ 192
(CONS (|dispatchFunction|
|POLYCAT-;patternMatch;SP2Pmr;39|)
$))))))
(COND
((|testBitVector| |pv$| 6)
(COND
((|testBitVector| |pv$| 5)
(|setShellEntry| $ 199
(CONS (|dispatchFunction|
|POLYCAT-;patternMatch;SP2Pmr;40|)
$)))))))))
(COND
((|testBitVector| |pv$| 12)
(COND
((|testBitVector| |pv$| 11)
(|setShellEntry| $ 206
(CONS (|dispatchFunction| |POLYCAT-;convert;SP;41|)
$))))))
(COND
((|testBitVector| |pv$| 10)
(COND
((|testBitVector| |pv$| 9)
(|setShellEntry| $ 213
(CONS (|dispatchFunction| |POLYCAT-;convert;SP;42|)
$))))))
(COND
((|testBitVector| |pv$| 14)
(COND
((|testBitVector| |pv$| 13)
(|setShellEntry| $ 221
(CONS (|dispatchFunction| |POLYCAT-;convert;SIf;43|)
$))))))
$))))
(MAKEPROP '|PolynomialCategory&| '|infovec|
(LIST '#(NIL NIL NIL NIL NIL NIL (|local| |#1|) (|local| |#2|)
(|local| |#3|) (|local| |#4|) (|Equation| 6) (0 . |lhs|)
(|Union| 9 '"failed") (5 . |retractIfCan|)
(10 . |retract|) (15 . |rhs|) (|List| 9) (|List| $)
(20 . |eval|) (|Equation| $) (|List| 19)
|POLYCAT-;eval;SLS;1| (27 . |Zero|) (31 . |Zero|)
(|Boolean|) (35 . ~=) (41 . |leadingMonomial|)
(46 . |reductum|) |POLYCAT-;monomials;SL;2|
(51 . |monomials|) (|Union| 17 '"failed")
|POLYCAT-;isPlus;SU;3| (56 . |variables|)
(61 . |monomial?|) (66 . |One|) (70 . |One|)
(|NonNegativeInteger|) (74 . |degree|) (80 . |monomial|)
(87 . |leadingCoefficient|) (92 . =) (98 . |coerce|)
|POLYCAT-;isTimes;SU;4| (103 . |mainVariable|) (108 . =)
(|Record| (|:| |var| 9) (|:| |exponent| 36))
(|Union| 45 '"failed") |POLYCAT-;isExpt;SU;5|
(|SparseUnivariatePolynomial| $) (114 . |univariate|)
(|SparseUnivariatePolynomial| 6) (120 . |coefficient|)
|POLYCAT-;coefficient;SVarSetNniS;6| (|List| 36)
(126 . |coefficient|) |POLYCAT-;coefficient;SLLS;7|
(133 . |monomial|) |POLYCAT-;monomial;SLLS;8|
(140 . |coerce|) |POLYCAT-;retract;SVarSet;9|
|POLYCAT-;retractIfCan;SU;10| (145 . |degree|)
(150 . |monomial|) |POLYCAT-;primitiveMonomials;SL;12|
(156 . |ground?|) (161 . |Zero|) (165 . ~=)
(171 . |degree|) (176 . |leadingCoefficient|)
(181 . |totalDegree|) (186 . |reductum|)
|POLYCAT-;totalDegree;SNni;13| (191 . |member?|)
(197 . |totalDegree|) |POLYCAT-;totalDegree;SLNni;14|
(203 . |resultant|) (209 . |resultant|)
(216 . |discriminant|) (221 . |discriminant|)
(227 . |primitiveMonomials|) (|List| 6) (232 . |concat|)
(237 . |removeDuplicates!|) (|Vector| 7) (242 . |new|)
(|Integer|) (248 . |minIndex|) (253 . |coefficient|)
(259 . |qsetelt!|) (|List| 7) (|List| 89) (|Matrix| 7)
(266 . |matrix|) (|List| 80) (|Matrix| 6)
(271 . |listOfLists|) (276 . |not|) (281 . |vertConcat|)
(|Matrix| $) (287 . |reducedSystem|) (|Vector| 6)
(292 . |entries|) (297 . |concat|) (303 . |concat|)
(|Record| (|:| |mat| 91) (|:| |vec| 83)) (|Vector| $)
(309 . |reducedSystem|)
(|GeneralPolynomialGcdPackage| 8 9 7 6)
(315 . |gcdPolynomial|) (321 . |gcdPolynomial|)
(|List| 50) (|Union| 110 '"failed")
(|PolynomialFactorizationByRecursion| 7 8 9 6)
(327 . |solveLinearPolynomialEquationByRecursion|)
(|List| 48) (|Union| 114 '"failed")
(333 . |solveLinearPolynomialEquation|) (|Factored| 50)
(339 . |factorByRecursion|) (|Factored| 48)
(344 . |factorPolynomial|)
(349 . |factorSquareFreeByRecursion|)
(354 . |factorSquareFreePolynomial|) (|Factored| $)
(359 . |factor|) (|Factored| 7) (364 . |unit|)
(|Union| '"nil" '"sqfr" '"irred" '"prime")
(|Record| (|:| |flg| 127) (|:| |fctr| 7) (|:| |xpnt| 85))
(|List| 128) (369 . |factorList|)
(|Record| (|:| |flg| 127) (|:| |fctr| 6) (|:| |xpnt| 85))
(|List| 131) (|Factored| 6) (374 . |makeFR|)
(380 . |unit|) (385 . |multivariate|)
(|Record| (|:| |flg| 127) (|:| |fctr| 50) (|:| |xpnt| 85))
(|List| 137) (391 . |factorList|) (396 . |factor|)
(401 . |transpose|) (406 . |characteristic|)
(410 . |setUnion|) (416 . |degree|) (|Union| $ '"failed")
(422 . |exquo|) (428 . |ground|) (433 . |transpose|)
(|Union| 105 '"failed") (438 . |conditionP|) (443 . |elt|)
(449 . *) (455 . +) (461 . |conditionP|)
(466 . |charthRoot|) (471 . |charthRoot|) (476 . |Zero|)
(480 . |coefficient|) (487 . -)
(|Record| (|:| |quotient| $) (|:| |remainder| $))
(493 . |monicDivide|) |POLYCAT-;monicDivide;2SVarSetR;30|
(|MultivariateSquareFree| 8 9 7 6) (499 . |squareFree|)
(504 . |squareFree|) (|PolynomialSquareFree| 9 8 7 6)
(509 . |squareFree|) (514 . |squareFree|) (519 . |unit|)
(|Record| (|:| |factor| 6) (|:| |exponent| 85))
(|List| 170) (524 . |factors|) (529 . |squareFreePart|)
(534 . |content|) (539 . |content|) (545 . |content|)
(550 . |exquo|)
(|Record| (|:| |unit| $) (|:| |canonical| $)
(|:| |associate| $))
(556 . |unitNormal|) (561 . |primitivePart|)
(566 . |content|) (572 . |exquo|) (578 . |primitivePart|)
(584 . <) (590 . <) (596 . <) (|PatternMatchResult| 85 6)
(|Pattern| 85)
(|PatternMatchPolynomialCategory| 85 8 9 7 6)
(602 . |patternMatch|) (|PatternMatchResult| 85 $)
(609 . |patternMatch|) (|Float|)
(|PatternMatchResult| 193 6) (|Pattern| 193)
(|PatternMatchPolynomialCategory| 193 8 9 7 6)
(616 . |patternMatch|) (|PatternMatchResult| 193 $)
(623 . |patternMatch|) (630 . |convert|) (635 . |convert|)
(|Mapping| 188 9) (|Mapping| 188 7)
(|PolynomialCategoryLifting| 8 9 7 6 188) (640 . |map|)
(647 . |convert|) (652 . |convert|) (657 . |convert|)
(|Mapping| 195 9) (|Mapping| 195 7)
(|PolynomialCategoryLifting| 8 9 7 6 195) (662 . |map|)
(669 . |convert|) (|InputForm|) (674 . |convert|)
(679 . |convert|) (|Mapping| 214 9) (|Mapping| 214 7)
(|PolynomialCategoryLifting| 8 9 7 6 214) (684 . |map|)
(691 . |convert|) (|Matrix| 85) (|Vector| 85)
(|Record| (|:| |mat| 222) (|:| |vec| 223))
(|Union| 85 '"failed") (|Fraction| 85)
(|Union| 226 '"failed") (|Union| 7 '"failed"))
'#(|totalDegree| 696 |squareFreePart| 707 |squareFree| 712
|solveLinearPolynomialEquation| 717 |retractIfCan| 723
|retract| 728 |resultant| 733 |reducedSystem| 740
|primitivePart| 751 |primitiveMonomials| 762
|patternMatch| 767 |monomials| 781 |monomial| 786
|monicDivide| 793 |isTimes| 800 |isPlus| 805 |isExpt| 810
|gcdPolynomial| 815 |factorSquareFreePolynomial| 821
|factorPolynomial| 826 |factor| 831 |eval| 836
|discriminant| 842 |convert| 848 |content| 863
|conditionP| 869 |coefficient| 874 |charthRoot| 888 < 893)
'NIL
(CONS (|makeByteWordVec2| 1 'NIL)
(CONS '#()
(CONS '#()
(|makeByteWordVec2| 221
'(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 22 0
7 0 23 2 6 24 0 0 25 1 6 0 0 26 1 6 0
0 27 1 6 17 0 29 1 6 16 0 32 1 6 24 0
33 0 6 0 34 0 7 0 35 2 6 36 0 9 37 3
6 0 0 9 36 38 1 6 7 0 39 2 7 24 0 0
40 1 6 0 7 41 1 6 12 0 43 2 6 24 0 0
44 2 6 48 0 9 49 2 50 6 0 36 51 3 6 0
0 16 53 54 3 6 0 0 16 53 56 1 6 0 9
58 1 6 8 0 61 2 6 0 7 8 62 1 6 24 0
64 0 50 0 65 2 50 24 0 0 66 1 50 36 0
67 1 50 6 0 68 1 6 36 0 69 1 50 0 0
70 2 16 24 9 0 72 2 6 36 0 16 73 2 50
6 0 0 75 3 0 0 0 0 9 76 1 50 6 0 77 2
0 0 0 9 78 1 6 17 0 79 1 80 0 17 81 1
80 0 0 82 2 83 0 36 7 84 1 83 85 0 86
2 6 7 0 8 87 3 83 7 0 85 7 88 1 91 0
90 92 1 94 93 0 95 1 24 0 0 96 2 91 0
0 0 97 1 0 91 98 99 1 100 80 0 101 2
80 0 0 0 102 2 83 0 0 0 103 2 0 104
98 105 106 2 107 50 50 50 108 2 0 48
48 48 109 2 112 111 110 50 113 2 0
115 114 48 116 1 112 117 50 118 1 0
119 48 120 1 112 117 50 121 1 0 119
48 122 1 7 123 0 124 1 125 7 0 126 1
125 129 0 130 2 133 0 6 132 134 1 117
50 0 135 2 6 0 48 9 136 1 117 138 0
139 1 0 123 0 140 1 94 0 0 141 0 6 36
142 2 80 0 0 0 143 2 6 53 0 16 144 2
85 145 0 0 146 1 6 7 0 147 1 91 0 0
148 1 7 149 98 150 2 83 7 0 85 151 2
6 0 0 0 152 2 6 0 0 0 153 1 0 149 98
154 1 7 145 0 155 1 0 145 0 156 0 8 0
157 3 6 0 0 9 36 158 2 6 0 0 0 159 2
50 160 0 0 161 1 163 133 6 164 1 0
123 0 165 1 166 133 6 167 1 6 123 0
168 1 133 6 0 169 1 133 171 0 172 1 0
0 0 173 1 50 6 0 174 2 0 0 0 9 175 1
6 7 0 176 2 6 145 0 7 177 1 6 178 0
179 1 0 0 0 180 2 6 0 0 9 181 2 6 145
0 0 182 2 0 0 0 9 183 2 8 24 0 0 184
2 7 24 0 0 185 2 0 24 0 0 186 3 189
187 6 188 187 190 3 0 191 0 188 191
192 3 196 194 6 195 194 197 3 0 198 0
195 198 199 1 9 188 0 200 1 7 188 0
201 3 204 188 202 203 6 205 1 0 188 0
206 1 9 195 0 207 1 7 195 0 208 3 211
195 209 210 6 212 1 0 195 0 213 1 9
214 0 215 1 7 214 0 216 3 219 214 217
218 6 220 1 0 214 0 221 2 0 36 0 16
74 1 0 36 0 71 1 0 0 0 173 1 0 123 0
165 2 0 115 114 48 116 1 0 12 0 60 1
0 9 0 59 3 0 0 0 0 9 76 1 0 91 98 99
2 0 104 98 105 106 2 0 0 0 9 183 1 0
0 0 180 1 0 17 0 63 3 0 191 0 188 191
192 3 0 198 0 195 198 199 1 0 17 0 28
3 0 0 0 16 53 57 3 0 160 0 0 9 162 1
0 30 0 42 1 0 30 0 31 1 0 46 0 47 2 0
48 48 48 109 1 0 119 48 122 1 0 119
48 120 1 0 123 0 140 2 0 0 0 20 21 2
0 0 0 9 78 1 0 214 0 221 1 0 188 0
206 1 0 195 0 213 2 0 0 0 9 175 1 0
149 98 154 3 0 0 0 16 53 55 3 0 0 0 9
36 52 1 0 145 0 156 2 0 24 0 0 186)))))
'|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)
(DEFPARAMETER |UnivariatePolynomialCategory;CAT| 'NIL)
(DEFPARAMETER |UnivariatePolynomialCategory;AL| 'NIL)
(DEFUN |UnivariatePolynomialCategory| (#0=#:G1424)
(LET (#1=#:G1425)
(COND
((SETQ #1#
(|assoc| (|devaluate| #0#)
|UnivariatePolynomialCategory;AL|))
(CDR #1#))
(T (SETQ |UnivariatePolynomialCategory;AL|
(|cons5| (CONS (|devaluate| #0#)
(SETQ #1#
(|UnivariatePolynomialCategory;|
#0#)))
|UnivariatePolynomialCategory;AL|))
#1#))))
(DEFUN |UnivariatePolynomialCategory;| (|t#1|)
(PROG (#0=#:G1423)
(RETURN
(PROG1 (LETT #0#
(|sublisV|
(PAIR '(|t#1|) (LIST (|devaluate| |t#1|)))
(|sublisV|
(PAIR '(#1=#:G1421 #2=#:G1422)
(LIST '(|NonNegativeInteger|)
'(|SingletonAsOrderedSet|)))
(COND
(|UnivariatePolynomialCategory;CAT|)
('T
(LETT |UnivariatePolynomialCategory;CAT|
(|Join|
(|PolynomialCategory| '|t#1| '#1#
'#2#)
(|Eltable| '|t#1| '|t#1|)
(|Eltable| '$ '$)
(|DifferentialRing|)
(|DifferentialExtension| '|t#1|)
(|mkCategory| '|domain|
'(((|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|))))))
'(((|StepThrough|)
(|has| |t#1| (|StepThrough|)))
((|Eltable| (|Fraction| $)
(|Fraction| $))
(|has| |t#1|
(|IntegralDomain|)))
((|EuclideanDomain|)
(|has| |t#1| (|Field|)))
(|additiveValuation|
(|has| |t#1| (|Field|))))
'((|Fraction| $)
(|NonNegativeInteger|)
(|SparseUnivariatePolynomial|
|t#1|)
(|Vector| |t#1|))
NIL))
. #3=(|UnivariatePolynomialCategory|)))))) . #3#)
(SETELT #0# 0
(LIST '|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| (|getShellEntry| $ 9))
(ZEROP (SPADCALL |p| (|getShellEntry| $ 11))))
NIL)
('T (LIST (SPADCALL (|getShellEntry| $ 13))))))
(DEFUN |UPOLYC-;degree;SSaosNni;2| (|p| |v| $)
(SPADCALL |p| (|getShellEntry| $ 11)))
(DEFUN |UPOLYC-;totalDegree;SLNni;3| (|p| |lv| $)
(COND ((NULL |lv|) 0) ('T (SPADCALL |p| (|getShellEntry| $ 17)))))
(DEFUN |UPOLYC-;degree;SLL;4| (|p| |lv| $)
(COND
((NULL |lv|) NIL)
('T (LIST (SPADCALL |p| (|getShellEntry| $ 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"))
('T
(SPADCALL |p| (|SPADfirst| |lv|) (|SPADfirst| |lq|)
(|getShellEntry| $ 21)))))
(DEFUN |UPOLYC-;eval;SSaos2S;6| (|p| |v| |q| $)
(SPADCALL |p| |q| (|getShellEntry| $ 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"))
('T
(SPADCALL |p| (|SPADfirst| |lv|) (|SPADfirst| |lr|)
(|getShellEntry| $ 26)))))
(DEFUN |UPOLYC-;eval;SSaosRS;8| (|p| |v| |r| $)
(SPADCALL (SPADCALL |p| |r| (|getShellEntry| $ 29))
(|getShellEntry| $ 30)))
(DEFUN |UPOLYC-;eval;SLS;9| (|p| |le| $)
(COND
((NULL |le|) |p|)
((NULL (NULL (CDR |le|)))
(|error| "can only eval a univariate polynomial once"))
('T
(COND
((QEQCAR (SPADCALL
(SPADCALL (|SPADfirst| |le|)
(|getShellEntry| $ 33))
(|getShellEntry| $ 35))
1)
|p|)
('T
(SPADCALL |p|
(SPADCALL (|SPADfirst| |le|) (|getShellEntry| $ 36))
(|getShellEntry| $ 24)))))))
(DEFUN |UPOLYC-;mainVariable;SU;10| (|p| $)
(COND
((ZEROP (SPADCALL |p| (|getShellEntry| $ 11))) (CONS 1 "failed"))
('T (CONS 0 (SPADCALL (|getShellEntry| $ 13))))))
(DEFUN |UPOLYC-;minimumDegree;SSaosNni;11| (|p| |v| $)
(SPADCALL |p| (|getShellEntry| $ 41)))
(DEFUN |UPOLYC-;minimumDegree;SLL;12| (|p| |lv| $)
(COND
((NULL |lv|) NIL)
('T (LIST (SPADCALL |p| (|getShellEntry| $ 41))))))
(DEFUN |UPOLYC-;monomial;SSaosNniS;13| (|p| |v| |n| $)
(SPADCALL (CONS #'|UPOLYC-;monomial;SSaosNniS;13!0| (VECTOR $ |n|))
|p| (|getShellEntry| $ 46)))
(DEFUN |UPOLYC-;monomial;SSaosNniS;13!0| (|#1| $$)
(SPADCALL |#1| (|getShellEntry| $$ 1)
(|getShellEntry| (|getShellEntry| $$ 0) 44)))
(DEFUN |UPOLYC-;coerce;SaosS;14| (|v| $)
(SPADCALL (|spadConstant| $ 49) 1 (|getShellEntry| $ 50)))
(DEFUN |UPOLYC-;makeSUP;SSup;15| (|p| $)
(COND
((SPADCALL |p| (|getShellEntry| $ 9)) (|spadConstant| $ 53))
('T
(SPADCALL
(SPADCALL (SPADCALL |p| (|getShellEntry| $ 54))
(SPADCALL |p| (|getShellEntry| $ 11))
(|getShellEntry| $ 55))
(SPADCALL (SPADCALL |p| (|getShellEntry| $ 56))
(|getShellEntry| $ 57))
(|getShellEntry| $ 58)))))
(DEFUN |UPOLYC-;unmakeSUP;SupS;16| (|sp| $)
(COND
((SPADCALL |sp| (|getShellEntry| $ 60)) (|spadConstant| $ 61))
('T
(SPADCALL
(SPADCALL (SPADCALL |sp| (|getShellEntry| $ 62))
(SPADCALL |sp| (|getShellEntry| $ 63))
(|getShellEntry| $ 50))
(SPADCALL (SPADCALL |sp| (|getShellEntry| $ 64))
(|getShellEntry| $ 65))
(|getShellEntry| $ 66)))))
(DEFUN |UPOLYC-;karatsubaDivide;SNniR;17| (|p| |n| $)
(SPADCALL |p|
(SPADCALL (|spadConstant| $ 49) |n| (|getShellEntry| $ 50))
(|getShellEntry| $ 69)))
(DEFUN |UPOLYC-;shiftRight;SNniS;18| (|p| |n| $)
(QCAR (SPADCALL |p|
(SPADCALL (|spadConstant| $ 49) |n| (|getShellEntry| $ 50))
(|getShellEntry| $ 69))))
(DEFUN |UPOLYC-;shiftLeft;SNniS;19| (|p| |n| $)
(SPADCALL |p|
(SPADCALL (|spadConstant| $ 49) |n| (|getShellEntry| $ 50))
(|getShellEntry| $ 72)))
(DEFUN |UPOLYC-;solveLinearPolynomialEquation;LSupU;20| (|lpp| |pp| $)
(SPADCALL |lpp| |pp| (|getShellEntry| $ 78)))
(DEFUN |UPOLYC-;factorPolynomial;SupF;21| (|pp| $)
(SPADCALL |pp| (|getShellEntry| $ 84)))
(DEFUN |UPOLYC-;factorSquareFreePolynomial;SupF;22| (|pp| $)
(SPADCALL |pp| (|getShellEntry| $ 87)))
(DEFUN |UPOLYC-;factor;SF;23| (|p| $)
(PROG (|ansR| #0=#:G1516 |w| #1=#:G1517)
(RETURN
(SEQ (COND
((ZEROP (SPADCALL |p| (|getShellEntry| $ 11)))
(SEQ (LETT |ansR|
(SPADCALL
(SPADCALL |p| (|getShellEntry| $ 54))
(|getShellEntry| $ 90))
|UPOLYC-;factor;SF;23|)
(EXIT (SPADCALL
(SPADCALL
(SPADCALL |ansR|
(|getShellEntry| $ 92))
(|getShellEntry| $ 30))
(PROGN
(LETT #0# NIL |UPOLYC-;factor;SF;23|)
(SEQ (LETT |w| NIL
|UPOLYC-;factor;SF;23|)
(LETT #1#
(SPADCALL |ansR|
(|getShellEntry| $ 97))
|UPOLYC-;factor;SF;23|)
G190
(COND
((OR (ATOM #1#)
(PROGN
(LETT |w| (CAR #1#)
|UPOLYC-;factor;SF;23|)
NIL))
(GO G191)))
(SEQ
(EXIT
(LETT #0#
(CONS
(VECTOR (QVELT |w| 0)
(SPADCALL (QVELT |w| 1)
(|getShellEntry| $ 30))
(QVELT |w| 2))
#0#)
|UPOLYC-;factor;SF;23|)))
(LETT #1# (CDR #1#)
|UPOLYC-;factor;SF;23|)
(GO G190) G191
(EXIT (NREVERSE0 #0#))))
(|getShellEntry| $ 101)))))
('T
(SPADCALL (ELT $ 65)
(SPADCALL (SPADCALL |p| (|getShellEntry| $ 57))
(|getShellEntry| $ 102))
(|getShellEntry| $ 106))))))))
(DEFUN |UPOLYC-;vectorise;SNniV;24| (|p| |n| $)
(PROG (|v| |m| |i| #0=#:G1522 #1=#:G1518)
(RETURN
(SEQ (LETT |m|
(SPADCALL
(LETT |v|
(SPADCALL |n| (|spadConstant| $ 108)
(|getShellEntry| $ 110))
|UPOLYC-;vectorise;SNniV;24|)
(|getShellEntry| $ 111))
|UPOLYC-;vectorise;SNniV;24|)
(SEQ (LETT |i| (SPADCALL |v| (|getShellEntry| $ 111))
|UPOLYC-;vectorise;SNniV;24|)
(LETT #0# (QVSIZE |v|) |UPOLYC-;vectorise;SNniV;24|)
G190 (COND ((> |i| #0#) (GO G191)))
(SEQ (EXIT (SPADCALL |v| |i|
(SPADCALL |p|
(PROG1
(LETT #1# (- |i| |m|)
|UPOLYC-;vectorise;SNniV;24|)
(|check-subtype| (>= #1# 0)
'(|NonNegativeInteger|)
#1#))
(|getShellEntry| $ 112))
(|getShellEntry| $ 113))))
(LETT |i| (+ |i| 1) |UPOLYC-;vectorise;SNniV;24|)
(GO G190) G191 (EXIT NIL))
(EXIT |v|)))))
(DEFUN |UPOLYC-;retract;SR;25| (|p| $)
(COND
((SPADCALL |p| (|getShellEntry| $ 9)) (|spadConstant| $ 108))
((ZEROP (SPADCALL |p| (|getShellEntry| $ 11)))
(SPADCALL |p| (|getShellEntry| $ 54)))
('T (|error| "Polynomial is not of degree 0"))))
(DEFUN |UPOLYC-;retractIfCan;SU;26| (|p| $)
(COND
((SPADCALL |p| (|getShellEntry| $ 9))
(CONS 0 (|spadConstant| $ 108)))
((ZEROP (SPADCALL |p| (|getShellEntry| $ 11)))
(CONS 0 (SPADCALL |p| (|getShellEntry| $ 54))))
('T (CONS 1 "failed"))))
(DEFUN |UPOLYC-;init;S;27| ($)
(SPADCALL (|spadConstant| $ 118) (|getShellEntry| $ 30)))
(DEFUN |UPOLYC-;nextItemInner| (|n| $)
(PROG (|nn| |n1| |n2| #0=#:G1543 |n3|)
(RETURN
(SEQ (COND
((SPADCALL |n| (|getShellEntry| $ 9))
(CONS 0
(SPADCALL
(PROG2 (LETT #0#
(SPADCALL (|spadConstant| $ 108)
(|getShellEntry| $ 121))
|UPOLYC-;nextItemInner|)
(QCDR #0#)
(|check-union| (QEQCAR #0# 0)
(|getShellEntry| $ 7) #0#))
(|getShellEntry| $ 30))))
((ZEROP (SPADCALL |n| (|getShellEntry| $ 11)))
(SEQ (LETT |nn|
(SPADCALL
(SPADCALL |n| (|getShellEntry| $ 54))
(|getShellEntry| $ 121))
|UPOLYC-;nextItemInner|)
(EXIT (COND
((QEQCAR |nn| 1) (CONS 1 "failed"))
('T
(CONS 0
(SPADCALL (QCDR |nn|)
(|getShellEntry| $ 30))))))))
('T
(SEQ (LETT |n1| (SPADCALL |n| (|getShellEntry| $ 56))
|UPOLYC-;nextItemInner|)
(LETT |n2| (|UPOLYC-;nextItemInner| |n1| $)
|UPOLYC-;nextItemInner|)
(EXIT (COND
((QEQCAR |n2| 0)
(CONS 0
(SPADCALL
(SPADCALL
(SPADCALL |n|
(|getShellEntry| $ 54))
(SPADCALL |n|
(|getShellEntry| $ 11))
(|getShellEntry| $ 50))
(QCDR |n2|)
(|getShellEntry| $ 66))))
((< (+ 1
(SPADCALL |n1|
(|getShellEntry| $ 11)))
(SPADCALL |n| (|getShellEntry| $ 11)))
(CONS 0
(SPADCALL
(SPADCALL
(SPADCALL |n|
(|getShellEntry| $ 54))
(SPADCALL |n|
(|getShellEntry| $ 11))
(|getShellEntry| $ 50))
(SPADCALL
(PROG2
(LETT #0#
(SPADCALL
(|spadConstant| $ 118)
(|getShellEntry| $ 121))
|UPOLYC-;nextItemInner|)
(QCDR #0#)
(|check-union| (QEQCAR #0# 0)
(|getShellEntry| $ 7) #0#))
(+ 1
(SPADCALL |n1|
(|getShellEntry| $ 11)))
(|getShellEntry| $ 50))
(|getShellEntry| $ 66))))
('T
(SEQ (LETT |n3|
(SPADCALL
(SPADCALL |n|
(|getShellEntry| $ 54))
(|getShellEntry| $ 121))
|UPOLYC-;nextItemInner|)
(EXIT (COND
((QEQCAR |n3| 1)
(CONS 1 "failed"))
('T
(CONS 0
(SPADCALL (QCDR |n3|)
(SPADCALL |n|
(|getShellEntry| $ 11))
(|getShellEntry| $ 50)))))))))))))))))
(DEFUN |UPOLYC-;nextItem;SU;29| (|n| $)
(PROG (|n1| #0=#:G1556)
(RETURN
(SEQ (LETT |n1| (|UPOLYC-;nextItemInner| |n| $)
|UPOLYC-;nextItem;SU;29|)
(EXIT (COND
((QEQCAR |n1| 1)
(CONS 0
(SPADCALL
(PROG2 (LETT #0#
(SPADCALL (|spadConstant| $ 118)
(|getShellEntry| $ 121))
|UPOLYC-;nextItem;SU;29|)
(QCDR #0#)
(|check-union| (QEQCAR #0# 0)
(|getShellEntry| $ 7) #0#))
(+ 1
(SPADCALL |n| (|getShellEntry| $ 11)))
(|getShellEntry| $ 50))))
('T |n1|)))))))
(DEFUN |UPOLYC-;content;SSaosS;30| (|p| |v| $)
(SPADCALL (SPADCALL |p| (|getShellEntry| $ 124))
(|getShellEntry| $ 30)))
(DEFUN |UPOLYC-;primeFactor| (|p| |q| $)
(PROG (#0=#:G1562 |p1|)
(RETURN
(SEQ (LETT |p1|
(PROG2 (LETT #0#
(SPADCALL |p|
(SPADCALL |p| |q|
(|getShellEntry| $ 126))
(|getShellEntry| $ 127))
|UPOLYC-;primeFactor|)
(QCDR #0#)
(|check-union| (QEQCAR #0# 0) (|getShellEntry| $ 6)
#0#))
|UPOLYC-;primeFactor|)
(EXIT (COND
((SPADCALL |p1| |p| (|getShellEntry| $ 128)) |p|)
('T (|UPOLYC-;primeFactor| |p1| |q| $))))))))
(DEFUN |UPOLYC-;separate;2SR;32| (|p| |q| $)
(PROG (|a| #0=#:G1568)
(RETURN
(SEQ (LETT |a| (|UPOLYC-;primeFactor| |p| |q| $)
|UPOLYC-;separate;2SR;32|)
(EXIT (CONS |a|
(PROG2 (LETT #0#
(SPADCALL |p| |a|
(|getShellEntry| $ 127))
|UPOLYC-;separate;2SR;32|)
(QCDR #0#)
(|check-union| (QEQCAR #0# 0)
(|getShellEntry| $ 6) #0#))))))))
(DEFUN |UPOLYC-;differentiate;SM2S;33| (|x| |deriv| |x'| $)
(PROG (|dg| |lc| #0=#:G1573 |d|)
(RETURN
(SEQ (LETT |d| (|spadConstant| $ 61)
|UPOLYC-;differentiate;SM2S;33|)
(SEQ G190
(COND
((NULL (< 0
(LETT |dg|
(SPADCALL |x| (|getShellEntry| $ 11))
|UPOLYC-;differentiate;SM2S;33|)))
(GO G191)))
(SEQ (LETT |lc| (SPADCALL |x| (|getShellEntry| $ 54))
|UPOLYC-;differentiate;SM2S;33|)
(LETT |d|
(SPADCALL
(SPADCALL |d|
(SPADCALL |x'|
(SPADCALL
(SPADCALL |dg| |lc|
(|getShellEntry| $ 132))
(PROG1
(LETT #0# (- |dg| 1)
|UPOLYC-;differentiate;SM2S;33|)
(|check-subtype| (>= #0# 0)
'(|NonNegativeInteger|) #0#))
(|getShellEntry| $ 50))
(|getShellEntry| $ 72))
(|getShellEntry| $ 66))
(SPADCALL (SPADCALL |lc| |deriv|) |dg|
(|getShellEntry| $ 50))
(|getShellEntry| $ 66))
|UPOLYC-;differentiate;SM2S;33|)
(EXIT (LETT |x|
(SPADCALL |x| (|getShellEntry| $ 56))
|UPOLYC-;differentiate;SM2S;33|)))
NIL (GO G190) G191 (EXIT NIL))
(EXIT (SPADCALL |d|
(SPADCALL
(SPADCALL
(SPADCALL |x| (|getShellEntry| $ 54))
|deriv|)
(|getShellEntry| $ 30))
(|getShellEntry| $ 66)))))))
(DEFUN |UPOLYC-;ncdiff| (|n| |x'| $)
(PROG (#0=#:G1591 |n1|)
(RETURN
(COND
((ZEROP |n|) (|spadConstant| $ 61))
((ZEROP (LETT |n1|
(PROG1 (LETT #0# (- |n| 1) |UPOLYC-;ncdiff|)
(|check-subtype| (>= #0# 0)
'(|NonNegativeInteger|) #0#))
|UPOLYC-;ncdiff|))
|x'|)
('T
(SPADCALL
(SPADCALL |x'|
(SPADCALL (|spadConstant| $ 49) |n1|
(|getShellEntry| $ 50))
(|getShellEntry| $ 72))
(SPADCALL
(SPADCALL (|spadConstant| $ 49) 1
(|getShellEntry| $ 50))
(|UPOLYC-;ncdiff| |n1| |x'| $) (|getShellEntry| $ 72))
(|getShellEntry| $ 66)))))))
(DEFUN |UPOLYC-;differentiate;SM2S;35| (|x| |deriv| |x'| $)
(PROG (|dg| |lc| |d|)
(RETURN
(SEQ (LETT |d| (|spadConstant| $ 61)
|UPOLYC-;differentiate;SM2S;35|)
(SEQ G190
(COND
((NULL (< 0
(LETT |dg|
(SPADCALL |x| (|getShellEntry| $ 11))
|UPOLYC-;differentiate;SM2S;35|)))
(GO G191)))
(SEQ (LETT |lc| (SPADCALL |x| (|getShellEntry| $ 54))
|UPOLYC-;differentiate;SM2S;35|)
(LETT |d|
(SPADCALL
(SPADCALL |d|
(SPADCALL (SPADCALL |lc| |deriv|)
|dg| (|getShellEntry| $ 50))
(|getShellEntry| $ 66))
(SPADCALL |lc|
(|UPOLYC-;ncdiff| |dg| |x'| $)
(|getShellEntry| $ 135))
(|getShellEntry| $ 66))
|UPOLYC-;differentiate;SM2S;35|)
(EXIT (LETT |x|
(SPADCALL |x| (|getShellEntry| $ 56))
|UPOLYC-;differentiate;SM2S;35|)))
NIL (GO G190) G191 (EXIT NIL))
(EXIT (SPADCALL |d|
(SPADCALL
(SPADCALL
(SPADCALL |x| (|getShellEntry| $ 54))
|deriv|)
(|getShellEntry| $ 30))
(|getShellEntry| $ 66)))))))
(DEFUN |UPOLYC-;differentiate;SMS;36| (|x| |deriv| $)
(SPADCALL |x| |deriv| (|spadConstant| $ 48) (|getShellEntry| $ 136)))
(DEFUN |UPOLYC-;differentiate;2S;37| (|x| $)
(PROG (|dg| #0=#:G1600 |d|)
(RETURN
(SEQ (LETT |d| (|spadConstant| $ 61)
|UPOLYC-;differentiate;2S;37|)
(SEQ G190
(COND
((NULL (< 0
(LETT |dg|
(SPADCALL |x| (|getShellEntry| $ 11))
|UPOLYC-;differentiate;2S;37|)))
(GO G191)))
(SEQ (LETT |d|
(SPADCALL |d|
(SPADCALL
(SPADCALL |dg|
(SPADCALL |x|
(|getShellEntry| $ 54))
(|getShellEntry| $ 132))
(PROG1
(LETT #0# (- |dg| 1)
|UPOLYC-;differentiate;2S;37|)
(|check-subtype| (>= #0# 0)
'(|NonNegativeInteger|) #0#))
(|getShellEntry| $ 50))
(|getShellEntry| $ 66))
|UPOLYC-;differentiate;2S;37|)
(EXIT (LETT |x|
(SPADCALL |x| (|getShellEntry| $ 56))
|UPOLYC-;differentiate;2S;37|)))
NIL (GO G190) G191 (EXIT NIL))
(EXIT |d|)))))
(DEFUN |UPOLYC-;differentiate;SSaosS;38| (|x| |v| $)
(SPADCALL |x| (|getShellEntry| $ 139)))
(DEFUN |UPOLYC-;elt;3F;39| (|g| |f| $)
(SPADCALL
(SPADCALL (SPADCALL |g| (|getShellEntry| $ 142)) |f|
(|getShellEntry| $ 144))
(SPADCALL (SPADCALL |g| (|getShellEntry| $ 145)) |f|
(|getShellEntry| $ 144))
(|getShellEntry| $ 146)))
(DEFUN |UPOLYC-;pseudoQuotient;3S;40| (|p| |q| $)
(PROG (|n| #0=#:G1646 #1=#:G1648)
(RETURN
(SEQ (LETT |n|
(+ (- (SPADCALL |p| (|getShellEntry| $ 11))
(SPADCALL |q| (|getShellEntry| $ 11)))
1)
|UPOLYC-;pseudoQuotient;3S;40|)
(EXIT (COND
((< |n| 1) (|spadConstant| $ 61))
('T
(PROG2 (LETT #1#
(SPADCALL
(SPADCALL
(SPADCALL
(SPADCALL
(SPADCALL |q|
(|getShellEntry| $ 54))
(PROG1
(LETT #0# |n|
|UPOLYC-;pseudoQuotient;3S;40|)
(|check-subtype| (>= #0# 0)
'(|NonNegativeInteger|) #0#))
(|getShellEntry| $ 148))
|p| (|getShellEntry| $ 135))
(SPADCALL |p| |q|
(|getShellEntry| $ 149))
(|getShellEntry| $ 150))
|q| (|getShellEntry| $ 127))
|UPOLYC-;pseudoQuotient;3S;40|)
(QCDR #1#)
(|check-union| (QEQCAR #1# 0)
(|getShellEntry| $ 6) #1#)))))))))
(DEFUN |UPOLYC-;pseudoDivide;2SR;41| (|p| |q| $)
(PROG (|n| |prem| #0=#:G1654 |lc| #1=#:G1656)
(RETURN
(SEQ (LETT |n|
(+ (- (SPADCALL |p| (|getShellEntry| $ 11))
(SPADCALL |q| (|getShellEntry| $ 11)))
1)
|UPOLYC-;pseudoDivide;2SR;41|)
(EXIT (COND
((< |n| 1)
(VECTOR (|spadConstant| $ 49) (|spadConstant| $ 61)
|p|))
('T
(SEQ (LETT |prem|
(SPADCALL |p| |q|
(|getShellEntry| $ 149))
|UPOLYC-;pseudoDivide;2SR;41|)
(LETT |lc|
(SPADCALL
(SPADCALL |q|
(|getShellEntry| $ 54))
(PROG1
(LETT #0# |n|
|UPOLYC-;pseudoDivide;2SR;41|)
(|check-subtype| (>= #0# 0)
'(|NonNegativeInteger|) #0#))
(|getShellEntry| $ 148))
|UPOLYC-;pseudoDivide;2SR;41|)
(EXIT (VECTOR |lc|
(PROG2
(LETT #1#
(SPADCALL
(SPADCALL
(SPADCALL |lc| |p|
(|getShellEntry| $ 135))
|prem|
(|getShellEntry| $ 150))
|q| (|getShellEntry| $ 127))
|UPOLYC-;pseudoDivide;2SR;41|)
(QCDR #1#)
(|check-union| (QEQCAR #1# 0)
(|getShellEntry| $ 6) #1#))
|prem|))))))))))
(DEFUN |UPOLYC-;composite;FSU;42| (|f| |q| $)
(PROG (|n| |d|)
(RETURN
(SEQ (LETT |n|
(SPADCALL (SPADCALL |f| (|getShellEntry| $ 142)) |q|
(|getShellEntry| $ 154))
|UPOLYC-;composite;FSU;42|)
(EXIT (COND
((QEQCAR |n| 1) (CONS 1 "failed"))
('T
(SEQ (LETT |d|
(SPADCALL
(SPADCALL |f|
(|getShellEntry| $ 145))
|q| (|getShellEntry| $ 154))
|UPOLYC-;composite;FSU;42|)
(EXIT (COND
((QEQCAR |d| 1) (CONS 1 "failed"))
('T
(CONS 0
(SPADCALL (QCDR |n|) (QCDR |d|)
(|getShellEntry| $ 155))))))))))))))
(DEFUN |UPOLYC-;composite;2SU;43| (|p| |q| $)
(PROG (|cqr| |v| |u| |w| #0=#:G1682)
(RETURN
(SEQ (COND
((SPADCALL |p| (|getShellEntry| $ 158)) (CONS 0 |p|))
('T
(SEQ (EXIT (SEQ (LETT |cqr|
(SPADCALL |p| |q|
(|getShellEntry| $ 159))
|UPOLYC-;composite;2SU;43|)
(COND
((SPADCALL (QVELT |cqr| 2)
(|getShellEntry| $ 158))
(SEQ (LETT |v|
(SPADCALL (QVELT |cqr| 2)
(QVELT |cqr| 0)
(|getShellEntry| $ 160))
|UPOLYC-;composite;2SU;43|)
(EXIT
(COND
((QEQCAR |v| 0)
(SEQ
(LETT |u|
(SPADCALL (QVELT |cqr| 1)
|q|
(|getShellEntry| $ 154))
|UPOLYC-;composite;2SU;43|)
(EXIT
(COND
((QEQCAR |u| 0)
(SEQ
(LETT |w|
(SPADCALL (QCDR |u|)
(QVELT |cqr| 0)
(|getShellEntry| $
160))
|UPOLYC-;composite;2SU;43|)
(EXIT
(COND
((QEQCAR |w| 0)
(PROGN
(LETT #0#
(CONS 0
(SPADCALL
(QCDR |v|)
(SPADCALL
(SPADCALL
(|spadConstant|
$ 49)
1
(|getShellEntry|
$ 50))
(QCDR |w|)
(|getShellEntry|
$ 72))
(|getShellEntry|
$ 66)))
|UPOLYC-;composite;2SU;43|)
(GO #0#))))))))))))))))
(EXIT (CONS 1 "failed"))))
#0# (EXIT #0#))))))))
(DEFUN |UPOLYC-;elt;S2F;44| (|p| |f| $)
(PROG (|n| #0=#:G1688 |ans|)
(RETURN
(SEQ (COND
((SPADCALL |p| (|getShellEntry| $ 9))
(|spadConstant| $ 162))
('T
(SEQ (LETT |ans|
(SPADCALL
(SPADCALL
(SPADCALL |p| (|getShellEntry| $ 54))
(|getShellEntry| $ 30))
(|getShellEntry| $ 163))
|UPOLYC-;elt;S2F;44|)
(LETT |n| (SPADCALL |p| (|getShellEntry| $ 11))
|UPOLYC-;elt;S2F;44|)
(SEQ G190
(COND
((NULL (SPADCALL
(SPADCALL
(LETT |p|
(SPADCALL |p|
(|getShellEntry| $ 56))
|UPOLYC-;elt;S2F;44|)
(|getShellEntry| $ 9))
(|getShellEntry| $ 164)))
(GO G191)))
(SEQ (EXIT (LETT |ans|
(SPADCALL
(SPADCALL |ans|
(SPADCALL |f|
(PROG1
(LETT #0#
(- |n|
(LETT |n|
(SPADCALL |p|
(|getShellEntry| $ 11))
|UPOLYC-;elt;S2F;44|))
|UPOLYC-;elt;S2F;44|)
(|check-subtype| (>= #0# 0)
'(|NonNegativeInteger|) #0#))
(|getShellEntry| $ 165))
(|getShellEntry| $ 166))
(SPADCALL
(SPADCALL
(SPADCALL |p|
(|getShellEntry| $ 54))
(|getShellEntry| $ 30))
(|getShellEntry| $ 163))
(|getShellEntry| $ 167))
|UPOLYC-;elt;S2F;44|)))
NIL (GO G190) G191 (EXIT NIL))
(EXIT (COND
((ZEROP |n|) |ans|)
('T
(SPADCALL |ans|
(SPADCALL |f| |n|
(|getShellEntry| $ 168))
(|getShellEntry| $ 166))))))))))))
(DEFUN |UPOLYC-;order;2SNni;45| (|p| |q| $)
(PROG (|u| #0=#:G1702 |ans|)
(RETURN
(SEQ (EXIT (COND
((SPADCALL |p| (|getShellEntry| $ 9))
(|error| "order: arguments must be nonzero"))
((< (SPADCALL |q| (|getShellEntry| $ 11)) 1)
(|error| "order: place must be non-trivial"))
('T
(SEQ (LETT |ans| 0 |UPOLYC-;order;2SNni;45|)
(EXIT (SEQ G190 NIL
(SEQ
(LETT |u|
(SPADCALL |p| |q|
(|getShellEntry| $ 127))
|UPOLYC-;order;2SNni;45|)
(EXIT
(COND
((QEQCAR |u| 1)
(PROGN
(LETT #0# |ans|
|UPOLYC-;order;2SNni;45|)
(GO #0#)))
('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)))))))
#0# (EXIT #0#)))))
(DEFUN |UPOLYC-;squareFree;SF;46| (|p| $)
(SPADCALL |p| (|getShellEntry| $ 172)))
(DEFUN |UPOLYC-;squareFreePart;2S;47| (|p| $)
(SPADCALL |p| (|getShellEntry| $ 174)))
(DEFUN |UPOLYC-;gcdPolynomial;3Sup;48| (|pp| |qq| $)
(COND
((SPADCALL |pp| (|getShellEntry| $ 176))
(SPADCALL |qq| (|getShellEntry| $ 177)))
((SPADCALL |qq| (|getShellEntry| $ 176))
(SPADCALL |pp| (|getShellEntry| $ 177)))
('T
(SPADCALL
(SPADCALL
(SPADCALL (SPADCALL |pp| (|getShellEntry| $ 178))
(SPADCALL |qq| (|getShellEntry| $ 178))
(|getShellEntry| $ 126))
(SPADCALL
(SPADCALL (SPADCALL |pp| (|getShellEntry| $ 179))
(SPADCALL |qq| (|getShellEntry| $ 179))
(|getShellEntry| $ 180))
(|getShellEntry| $ 179))
(|getShellEntry| $ 181))
(|getShellEntry| $ 177)))))
(DEFUN |UPOLYC-;squareFreePolynomial;SupF;49| (|pp| $)
(SPADCALL |pp| (|getShellEntry| $ 184)))
(DEFUN |UPOLYC-;elt;F2R;50| (|f| |r| $)
(SPADCALL
(SPADCALL (SPADCALL |f| (|getShellEntry| $ 142)) |r|
(|getShellEntry| $ 29))
(SPADCALL (SPADCALL |f| (|getShellEntry| $ 145)) |r|
(|getShellEntry| $ 29))
(|getShellEntry| $ 186)))
(DEFUN |UPOLYC-;euclideanSize;SNni;51| (|x| $)
(COND
((SPADCALL |x| (|getShellEntry| $ 9))
(|error| "euclideanSize called on 0 in Univariate Polynomial"))
('T (SPADCALL |x| (|getShellEntry| $ 11)))))
(DEFUN |UPOLYC-;divide;2SR;52| (|x| |y| $)
(PROG (|lc| |f| #0=#:G1714 |n| |quot|)
(RETURN
(SEQ (COND
((SPADCALL |y| (|getShellEntry| $ 9))
(|error| "division by 0 in Univariate Polynomials"))
('T
(SEQ (LETT |quot| (|spadConstant| $ 61)
|UPOLYC-;divide;2SR;52|)
(LETT |lc|
(SPADCALL
(SPADCALL |y| (|getShellEntry| $ 54))
(|getShellEntry| $ 189))
|UPOLYC-;divide;2SR;52|)
(SEQ G190
(COND
((NULL (COND
((SPADCALL |x|
(|getShellEntry| $ 9))
'NIL)
('T
(SPADCALL
(<
(SPADCALL |x|
(|getShellEntry| $ 11))
(SPADCALL |y|
(|getShellEntry| $ 11)))
(|getShellEntry| $ 164)))))
(GO G191)))
(SEQ (LETT |f|
(SPADCALL |lc|
(SPADCALL |x|
(|getShellEntry| $ 54))
(|getShellEntry| $ 190))
|UPOLYC-;divide;2SR;52|)
(LETT |n|
(PROG1
(LETT #0#
(-
(SPADCALL |x|
(|getShellEntry| $ 11))
(SPADCALL |y|
(|getShellEntry| $ 11)))
|UPOLYC-;divide;2SR;52|)
(|check-subtype| (>= #0# 0)
'(|NonNegativeInteger|) #0#))
|UPOLYC-;divide;2SR;52|)
(LETT |quot|
(SPADCALL |quot|
(SPADCALL |f| |n|
(|getShellEntry| $ 50))
(|getShellEntry| $ 66))
|UPOLYC-;divide;2SR;52|)
(EXIT (LETT |x|
(SPADCALL |x|
(SPADCALL
(SPADCALL |f| |n|
(|getShellEntry| $ 50))
|y| (|getShellEntry| $ 72))
(|getShellEntry| $ 150))
|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| $ 61) |UPOLYC-;integrate;2S;53|)
(SEQ G190
(COND
((NULL (SPADCALL |p| (|spadConstant| $ 61)
(|getShellEntry| $ 192)))
(GO G191)))
(SEQ (LETT |l| (SPADCALL |p| (|getShellEntry| $ 54))
|UPOLYC-;integrate;2S;53|)
(LETT |d|
(+ 1 (SPADCALL |p| (|getShellEntry| $ 11)))
|UPOLYC-;integrate;2S;53|)
(LETT |ans|
(SPADCALL |ans|
(SPADCALL
(SPADCALL
(SPADCALL |d|
(|getShellEntry| $ 194))
(|getShellEntry| $ 195))
(SPADCALL |l| |d|
(|getShellEntry| $ 50))
(|getShellEntry| $ 196))
(|getShellEntry| $ 66))
|UPOLYC-;integrate;2S;53|)
(EXIT (LETT |p|
(SPADCALL |p| (|getShellEntry| $ 56))
|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|)
. #0=(|UnivariatePolynomialCategory&|))
(LETT |dv$2| (|devaluate| |#2|) . #0#)
(LETT |dv$|
(LIST '|UnivariatePolynomialCategory&| |dv$1| |dv$2|) . #0#)
(LETT $ (|newShell| 203) . #0#)
(|setShellEntry| $ 0 |dv$|)
(|setShellEntry| $ 3
(LETT |pv$|
(|buildPredVector| 0 0
(LIST (|HasCategory| |#2|
'(|Algebra| (|Fraction| (|Integer|))))
(|HasCategory| |#2| '(|Field|))
(|HasCategory| |#2| '(|GcdDomain|))
(|HasCategory| |#2| '(|IntegralDomain|))
(|HasCategory| |#2| '(|CommutativeRing|))
(|HasCategory| |#2| '(|StepThrough|)))) . #0#))
(|stuffDomainSlots| $)
(|setShellEntry| $ 6 |#1|)
(|setShellEntry| $ 7 |#2|)
(COND
((|HasCategory| |#2| '(|PolynomialFactorizationExplicit|))
(PROGN
(|setShellEntry| $ 82
(CONS (|dispatchFunction|
|UPOLYC-;solveLinearPolynomialEquation;LSupU;20|)
$))
(|setShellEntry| $ 86
(CONS (|dispatchFunction|
|UPOLYC-;factorPolynomial;SupF;21|)
$))
(|setShellEntry| $ 88
(CONS (|dispatchFunction|
|UPOLYC-;factorSquareFreePolynomial;SupF;22|)
$))
(|setShellEntry| $ 107
(CONS (|dispatchFunction| |UPOLYC-;factor;SF;23|) $)))))
(COND
((|testBitVector| |pv$| 6)
(PROGN
(|setShellEntry| $ 119
(CONS (|dispatchFunction| |UPOLYC-;init;S;27|) $))
NIL
(|setShellEntry| $ 123
(CONS (|dispatchFunction| |UPOLYC-;nextItem;SU;29|) $)))))
(COND
((|testBitVector| |pv$| 3)
(PROGN
(|setShellEntry| $ 125
(CONS (|dispatchFunction| |UPOLYC-;content;SSaosS;30|)
$))
NIL
(|setShellEntry| $ 130
(CONS (|dispatchFunction| |UPOLYC-;separate;2SR;32|)
$)))))
(COND
((|testBitVector| |pv$| 5)
(|setShellEntry| $ 134
(CONS (|dispatchFunction|
|UPOLYC-;differentiate;SM2S;33|)
$)))
('T
(PROGN
(|setShellEntry| $ 134
(CONS (|dispatchFunction|
|UPOLYC-;differentiate;SM2S;35|)
$)))))
(COND
((|testBitVector| |pv$| 4)
(PROGN
(|setShellEntry| $ 147
(CONS (|dispatchFunction| |UPOLYC-;elt;3F;39|) $))
(|setShellEntry| $ 151
(CONS (|dispatchFunction|
|UPOLYC-;pseudoQuotient;3S;40|)
$))
(|setShellEntry| $ 153
(CONS (|dispatchFunction|
|UPOLYC-;pseudoDivide;2SR;41|)
$))
(|setShellEntry| $ 157
(CONS (|dispatchFunction| |UPOLYC-;composite;FSU;42|)
$))
(|setShellEntry| $ 161
(CONS (|dispatchFunction| |UPOLYC-;composite;2SU;43|)
$))
(|setShellEntry| $ 169
(CONS (|dispatchFunction| |UPOLYC-;elt;S2F;44|) $))
(|setShellEntry| $ 170
(CONS (|dispatchFunction| |UPOLYC-;order;2SNni;45|) $)))))
(COND
((|testBitVector| |pv$| 3)
(PROGN
(|setShellEntry| $ 173
(CONS (|dispatchFunction| |UPOLYC-;squareFree;SF;46|)
$))
(|setShellEntry| $ 175
(CONS (|dispatchFunction|
|UPOLYC-;squareFreePart;2S;47|)
$)))))
(COND
((|HasCategory| |#2| '(|PolynomialFactorizationExplicit|))
(PROGN
(|setShellEntry| $ 182
(CONS (|dispatchFunction|
|UPOLYC-;gcdPolynomial;3Sup;48|)
$))
(|setShellEntry| $ 185
(CONS (|dispatchFunction|
|UPOLYC-;squareFreePolynomial;SupF;49|)
$)))))
(COND
((|testBitVector| |pv$| 2)
(PROGN
(|setShellEntry| $ 187
(CONS (|dispatchFunction| |UPOLYC-;elt;F2R;50|) $))
(|setShellEntry| $ 188
(CONS (|dispatchFunction|
|UPOLYC-;euclideanSize;SNni;51|)
$))
(|setShellEntry| $ 191
(CONS (|dispatchFunction| |UPOLYC-;divide;2SR;52|) $)))))
(COND
((|testBitVector| |pv$| 1)
(|setShellEntry| $ 197
(CONS (|dispatchFunction| |UPOLYC-;integrate;2S;53|) $))))
$))))
(MAKEPROP '|UnivariatePolynomialCategory&| '|infovec|
(LIST '#(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 '"failed") (55 . |mainVariable|) (60 . |rhs|)
(|Equation| $) (|List| 37) |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|
(|SparseUnivariatePolynomial| 6) (|List| 74)
(|Union| 75 '"failed")
(|PolynomialFactorizationByRecursionUnivariate| 7 6)
(174 . |solveLinearPolynomialEquationByRecursion|)
(|SparseUnivariatePolynomial| $) (|List| 79)
(|Union| 80 '"failed")
(180 . |solveLinearPolynomialEquation|) (|Factored| 74)
(186 . |factorByRecursion|) (|Factored| 79)
(191 . |factorPolynomial|)
(196 . |factorSquareFreeByRecursion|)
(201 . |factorSquareFreePolynomial|) (|Factored| $)
(206 . |factor|) (|Factored| 7) (211 . |unit|)
(|Union| '"nil" '"sqfr" '"irred" '"prime") (|Integer|)
(|Record| (|:| |flg| 93) (|:| |fctr| 7) (|:| |xpnt| 94))
(|List| 95) (216 . |factorList|)
(|Record| (|:| |flg| 93) (|:| |fctr| 6) (|:| |xpnt| 94))
(|List| 98) (|Factored| 6) (221 . |makeFR|)
(227 . |factorPolynomial|) (|Mapping| 6 52)
(|Factored| 52) (|FactoredFunctions2| 52 6) (232 . |map|)
(238 . |factor|) (243 . |Zero|) (|Vector| 7) (247 . |new|)
(253 . |minIndex|) (258 . |coefficient|)
(264 . |qsetelt!|) |UPOLYC-;vectorise;SNniV;24|
|UPOLYC-;retract;SR;25| (|Union| 7 '"failed")
|UPOLYC-;retractIfCan;SU;26| (271 . |init|) (275 . |init|)
(|Union| $ '"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| 143 '"failed") (433 . |composite|)
(439 . |ground?|) (444 . |pseudoDivide|) (450 . |exquo|)
(456 . |composite|) (462 . |Zero|) (466 . |coerce|)
(471 . |not|) (476 . **) (482 . *) (488 . +) (494 . **)
(500 . |elt|) (506 . |order|)
(|UnivariatePolynomialSquareFree| 7 6)
(512 . |squareFree|) (517 . |squareFree|)
(522 . |squareFreePart|) (527 . |squareFreePart|)
(532 . |zero?|) (537 . |unitCanonical|) (542 . |content|)
(547 . |primitivePart|) (552 . |subResultantGcd|)
(558 . *) (564 . |gcdPolynomial|)
(|UnivariatePolynomialSquareFree| 6 74)
(570 . |squareFree|) (575 . |squareFreePolynomial|)
(580 . /) (586 . |elt|) (592 . |euclideanSize|)
(597 . |inv|) (602 . *) (608 . |divide|) (614 . ~=)
(|Fraction| 94) (620 . |coerce|) (625 . |inv|) (630 . *)
(636 . |integrate|) (|Symbol|) (|List| 198)
(|Union| 94 '"failed") (|Union| 193 '"failed")
(|OutputForm|))
'#(|vectorise| 641 |variables| 647 |unmakeSUP| 652
|totalDegree| 657 |squareFreePolynomial| 663
|squareFreePart| 668 |squareFree| 673
|solveLinearPolynomialEquation| 678 |shiftRight| 684
|shiftLeft| 690 |separate| 696 |retractIfCan| 702
|retract| 707 |pseudoQuotient| 712 |pseudoDivide| 718
|order| 724 |nextItem| 730 |monomial| 735 |minimumDegree|
742 |makeSUP| 754 |mainVariable| 759 |karatsubaDivide| 764
|integrate| 770 |init| 775 |gcdPolynomial| 779
|factorSquareFreePolynomial| 785 |factorPolynomial| 790
|factor| 795 |eval| 800 |euclideanSize| 834 |elt| 839
|divide| 857 |differentiate| 863 |degree| 887 |content|
899 |composite| 905 |coerce| 917)
'NIL
(CONS (|makeByteWordVec2| 1 'NIL)
(CONS '#()
(CONS '#()
(|makeByteWordVec2| 197
'(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 41 2 10 0 0 0 44 2 6 0 45
0 46 0 6 0 48 0 7 0 49 2 6 0 7 10 50
0 52 0 53 1 6 7 0 54 2 52 0 7 10 55 1
6 0 0 56 1 6 52 0 57 2 52 0 0 0 58 1
52 8 0 60 0 6 0 61 1 52 7 0 62 1 52
10 0 63 1 52 0 0 64 1 6 0 52 65 2 6 0
0 0 66 2 6 68 0 0 69 2 6 0 0 0 72 2
77 76 75 74 78 2 0 81 80 79 82 1 77
83 74 84 1 0 85 79 86 1 77 83 74 87 1
0 85 79 88 1 7 89 0 90 1 91 7 0 92 1
91 96 0 97 2 100 0 6 99 101 1 7 85 79
102 2 105 100 103 104 106 1 0 89 0
107 0 7 0 108 2 109 0 10 7 110 1 109
94 0 111 2 6 7 0 10 112 3 109 7 0 94
7 113 0 7 0 118 0 0 0 119 1 7 120 0
121 0 74 0 122 1 0 120 0 123 1 6 7 0
124 2 0 0 0 12 125 2 6 0 0 0 126 2 6
120 0 0 127 2 6 8 0 0 128 2 0 129 0 0
130 0 74 0 131 2 7 0 10 0 132 3 0 0 0
133 0 134 2 6 0 7 0 135 3 6 0 0 133 0
136 1 6 0 0 139 1 141 6 0 142 2 6 143
0 143 144 1 141 6 0 145 2 141 0 0 0
146 2 0 143 143 143 147 2 7 0 0 10
148 2 6 0 0 0 149 2 6 0 0 0 150 2 0 0
0 0 151 2 0 152 0 0 153 2 6 120 0 0
154 2 141 0 6 6 155 2 0 156 143 0 157
1 6 8 0 158 2 6 152 0 0 159 2 6 120 0
7 160 2 0 120 0 0 161 0 141 0 162 1
141 0 6 163 1 8 0 0 164 2 141 0 0 94
165 2 141 0 0 0 166 2 141 0 0 0 167 2
141 0 0 10 168 2 0 143 0 143 169 2 0
10 0 0 170 1 171 100 6 172 1 0 89 0
173 1 171 6 6 174 1 0 0 0 175 1 74 8
0 176 1 74 0 0 177 1 74 6 0 178 1 74
0 0 179 2 74 0 0 0 180 2 74 0 6 0 181
2 0 79 79 79 182 1 183 83 74 184 1 0
85 79 185 2 7 0 0 0 186 2 0 7 143 7
187 1 0 10 0 188 1 7 0 0 189 2 7 0 0
0 190 2 0 68 0 0 191 2 6 8 0 0 192 1
193 0 94 194 1 193 0 0 195 2 6 0 193
0 196 1 0 0 0 197 2 0 109 0 10 114 1
0 14 0 15 1 0 0 52 67 2 0 10 0 14 18
1 0 85 79 185 1 0 0 0 175 1 0 89 0
173 2 0 81 80 79 82 2 0 0 0 10 71 2 0
0 0 10 73 2 0 129 0 0 130 1 0 116 0
117 1 0 7 0 115 2 0 0 0 0 151 2 0 152
0 0 153 2 0 10 0 0 170 1 0 120 0 123
3 0 0 0 12 10 47 2 0 19 0 14 43 2 0
10 0 12 42 1 0 52 0 59 1 0 34 0 40 2
0 68 0 10 70 1 0 0 0 197 0 0 0 119 2
0 79 79 79 182 1 0 85 79 88 1 0 85 79
86 1 0 89 0 107 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 38 39 1 0 10 0 188 2
0 143 0 143 169 2 0 7 143 7 187 2 0
143 143 143 147 2 0 68 0 0 191 3 0 0
0 133 0 134 2 0 0 0 133 137 1 0 0 0
138 2 0 0 0 12 140 2 0 10 0 12 16 2 0
19 0 14 20 2 0 0 0 12 125 2 0 120 0 0
161 2 0 156 143 0 157 1 0 0 12 51)))))
'|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}