Polynomial Representation
Polynomial: TYPE = REF PolynomialRec; -- Recursive rep
PolynomialStructure: TYPE = { constant, nonconstant };
PolynomialRec:
TYPE =
RECORD [
numVars: CARDINAL, -- 0 <=> constant variant
data:
SELECT type: PolynomialStructure
FROM
constant => [ value: REF ],
nonconstant => [ leadingTerm: Term, reductum: Polynomial],
the terms of a nonconstant polynomial are expected to be listed in order of decreasing exponent, thus the reductum of a polynomial (if nonzero) is expected to be a polynomial in the same number of variables, of lower degree.
ENDCASE
];
Term:
TYPE =
RECORD [
exponent: CARDINAL,
coefficient: Polynomial
];
ZeroPoly: Polynomial =
NIL;
PolynomialSeq: TYPE = REF PolynomialSeqRec;
PolynomialSeqRec:
TYPE =
RECORD
[SEQUENCE lengthPlus1:[1..4096] OF Polynomial];
Classes for Polynomial Rings
polynomialsOverRingClass:
AC.StructureClass;
-- Class record for all polynomial rings.
polynomialsOverFieldClass: AC.StructureClass; -- Class record for all polynomial rings.
Operations unique to Polynomial Rings
UnivariateMonomialConstructorOp:
TYPE =
PROC [coeff:
REF, exp:
CARDINAL]
RETURNS [out: Polynomial];
returns coeff * var ^ exp. Note that doesn't need to know what coeffRing is.
MultivariateMonomialConstructorOp:
TYPE =
PROC [coeff: Polynomial, exp:
CARDINAL]
RETURNS [out: Polynomial];
returns coeff * var ^ exp. Note that doesn't need to know what coeffRing is.
PolynomialOps: TYPE = REF PolynomialOpsRec; -- prop key is $PolynomialRing. Skew, i.e. noncommutative, fields ok)
PolynomialOpsRec:
TYPE =
RECORD [
univariateMonomial: UnivariateMonomialConstructorOp,
multivariateMonomial: MultivariateMonomialConstructorOp,
differentiate: AC.UnaryOp,
leadingCoefficient: AC.UnaryOp,
mainVariableDegree: AC.ElementRankOp
];
Polynomial Ring Constructors
PolynomialsOverRing:
PROC [coeffRing:
AC.Structure, V:
VARS.VariableSeq]
RETURNS [polynomialRing:
AC.Structure];
A particular polynomialRing is defined by its coefficient domain, and its variables. coeffRing can be a ring, field (although should use PolynomialsOverField for this), or algebra.
PolynomialsOverField:
PROC [coeffField:
AC.Structure, V:
VARS.VariableSeq]
RETURNS [polynomialRing:
AC.Structure];
Eventually this one should fill in euclidean ops, i.e. gcd and degree
Extract Polynomial Operations from Class Property Lists
IsPolynomialRing: PROC [ring: AC.Structure] RETURNS [BOOL];
Extract polynomial ring-specific procs
UnivariateMonomial:
PROC [polynomialRing:
AC.Structure]
RETURNS [UnivariateMonomialConstructorOp];
Error if not a PolynomialRing
MultivariateMonomial:
PROC [polynomialRing:
AC.Structure]
RETURNS [MultivariateMonomialConstructorOp];
Error if not a PolynomialRing.
Differentiate:
PROC [polynomialRing:
AC.Structure]
RETURNS [
AC.UnaryOp];
Error if not a PolynomialRing.
LeadingCoefficient:
PROC [polynomialRing:
AC.Structure]
RETURNS [
AC.UnaryOp];
Leading coeff of the recursive form of this poly.
MainVariableDegree: PROC [polynomialRing: AC.Structure] RETURNS [AC.ElementRankOp];
Conversion and IO
ReadPoly:
PROC [in:
IO.
STREAM, V:
VARS.VariableSeq, coeffRing:
AC.Structure]
RETURNS [poly: Polynomial];
PolyFromRope:
PROC [in: Rope.
ROPE, V:
VARS.VariableSeq, coeffRing:
AC.Structure]
RETURNS [out: Polynomial];
PolyFullRepToRope:
PROC [in: Polynomial, V:
VARS.VariableSeq, coeffRing:
AC.Structure]
RETURNS [out: Rope.
ROPE];
Dump the recursive internal representation in a more reasonable form than SAC-2 rep
PolyToRope:
PROC [in: Polynomial, V:
VARS.VariableSeq, coeffRing:
AC.Structure, termRope: Rope.
ROPE ←
DP.DollarRope]
RETURNS [out: Rope.
ROPE];
Display in a reasonable format
WritePoly:
PROC [in: Polynomial, V:
VARS.VariableSeq, coeffRing:
AC.Structure, out:
IO.
STREAM, termRope: Rope.
ROPE ←
DP.DollarRope];
ReadPolySeq:
PROC [in:
IO.
STREAM, V:
VARS.VariableSeq, coeffRing:
AC.Structure]
RETURNS [seq: PolynomialSeq];
PolySeqFromRope:
PROC [in: Rope.
ROPE, V:
VARS.VariableSeq, coeffRing:
AC.Structure]
RETURNS [out: PolynomialSeq];
PolySeqToRope:
PROC [in: PolynomialSeq, V:
VARS.VariableSeq, coeffRing:
AC.Structure]
RETURNS [out: Rope.
ROPE];
WritePolySeq:
PROC [in: PolynomialSeq, V:
VARS.VariableSeq, coeffRing:
AC.Structure, out:
IO.
STREAM];
PolyFromDPoly:
PROC [in:
DP.DPolynomial, V:
VARS.VariableSeq]
RETURNS [out: Polynomial];
DPolyFromPoly: PROC [in: Polynomial, V: VARS.VariableSeq] RETURNS [out: DP.DPolynomial];
Arithmetic
Add:
PROC [in1, in2: Polynomial, coeffRing:
AC.Structure]
RETURNS [out: Polynomial];
Negate:
PROC [in: Polynomial, coeffRing:
AC.Structure]
RETURNS [out: Polynomial];
Subtract:
PROC [in1, in2: Polynomial, coeffRing:
AC.Structure]
RETURNS [Polynomial];
Multiply:
PROC [in1, in2: Polynomial, coeffRing:
AC.Structure]
RETURNS [out: Polynomial];
Remainder:
PROC [dividend, divisor: Polynomial, polynomialsOverField:
AC.Structure]
RETURNS [Polynomial];
Note that structure arg is poly ring, not coefficient ring
Diff: PROC [in: Polynomial, coeffRing: AC.Structure] RETURNS [out: Polynomial];
Comparison
Equal:
PROC [in1, in2: Polynomial, coeffRing:
AC.Structure]
RETURNS [
BOOL ←
FALSE];
Sign:
PROC [in: Polynomial, coeffRing:
AC.Structure]
RETURNS [Basics.Comparison];
Sign of the leading base coefficient.
Abs:
PROC [in: Polynomial, coeffRing:
AC.Structure]
RETURNS [out: Polynomial];
Compare: PROC [in1, in2: Polynomial, coeffRing: AC.Structure] RETURNS [Basics.Comparison];