PolynomialsImpl.mesa
Last Edited by: Arnon, June 10, 1985 4:19:22 pm PDT
DIRECTORY
Rope,
Convert USING [RopeFromCard],
IO,
BigCardinals,
RatNums,
Polynomials;
PolynomialsImpl:
CEDAR PROGRAM
IMPORTS Rope, Convert, IO, RatNums
EXPORTS Polynomials =
BEGIN OPEN RN: RatNums, Polynomials;
***** Arithmetic *****
PolynomialAdd:
PUBLIC PROC [in1, in2: Polynomial]
RETURNS [out: Polynomial] ~ {
previousOutTerm, outTerm, tail: Polynomial;
termToAdd: BOOL;
IF in1 = ZeroPoly THEN RETURN[ in2];
IF in2 = ZeroPoly THEN RETURN[ in1];
IF in1.numVars # in2.numVars THEN ERROR;
WITH in1
SELECT FROM
input1:
REF PolynomialRec.constant => {
WITH in2
SELECT FROM
input2:
REF PolynomialRec.constant => {
val: RN.RatNum ← RN.RatNumAdd[input1.value, input2.value];
IF RN.RatNumZero[val] THEN RETURN;
out ←
NEW[PolynomialRec ← [
numVars: 0,
data: constant[value: val]
] ];
RETURN;
};
ENDCASE => ERROR;
};
input1:
REF PolynomialRec.nonconstant => {
WITH in2
SELECT FROM
input2:
REF PolynomialRec.nonconstant => {
out ← previousOutTerm ← ZeroPoly;
WHILE input1 # ZeroPoly
AND input2 # ZeroPoly
DO
termToAdd ← TRUE;
SELECT input1.leadingTerm.exponent
FROM
< input2.leadingTerm.exponent => {
outTerm ←
NEW[PolynomialRec ← [
numVars: input2.numVars,
data: nonconstant[leadingTerm: input2.leadingTerm, reductum: ZeroPoly]
] ];
input2 ← NARROW[ input2.reductum ];
};
> input2.leadingTerm.exponent => {
outTerm ←
NEW[PolynomialRec ← [
numVars: input1.numVars,
data: nonconstant [leadingTerm: input1.leadingTerm, reductum: ZeroPoly ]
] ];
input1 ← NARROW[ input1.reductum ];
};
= input2.leadingTerm.exponent => {
coeff: Polynomial ← PolynomialAdd[
input1.leadingTerm.coefficient,
input2.leadingTerm.coefficient
];
IF coeff # ZeroPoly
THEN
outTerm ←
NEW[PolynomialRec ← [
numVars: input1.numVars,
data: nonconstant [ leadingTerm: [ exponent: input2.leadingTerm.exponent,
coefficient: coeff ],
reductum: ZeroPoly ]
] ]
input1 ← NARROW[ input1.reductum ];
input2 ← NARROW[ input2.reductum ];
};
ENDCASE;
IF termToAdd
THEN IF previousOutTerm # ZeroPoly
THEN {
WITH previousOutTerm
SELECT FROM
previousOutTermVariant:
REF PolynomialRec.nonconstant => {
previousOutTermVariant.reductum ← outTerm;
previousOutTerm ← outTerm;
};
ENDCASE => ERROR;
}
ELSE out ← previousOutTerm ← outTerm;
ENDLOOP;
IF input1 = ZeroPoly THEN tail ← input2 ELSE tail ← input1;
IF out # ZeroPoly
THEN WITH previousOutTerm
SELECT FROM
previousOutTermVariant: REF PolynomialRec.nonconstant => previousOutTermVariant.reductum ← tail;
ENDCASE => ERROR
ELSE out ← tail;
};
ENDCASE => ERROR;
};
ENDCASE;
};
PolynomialNegate:
PUBLIC PROC [in: Polynomial]
RETURNS [out: Polynomial] ~ {
outTerm, previousOutTerm: Polynomial;
IF in = ZeroPoly THEN RETURN[ZeroPoly];
WITH in
SELECT FROM
input:
REF PolynomialRec.constant => {
out ←
NEW[PolynomialRec ← [
numVars: 0,
data: constant[value: RN.RatNumNegate[input.value] ]
] ];
RETURN;
};
input:
REF PolynomialRec.nonconstant => {
previousOutTerm ← ZeroPoly;
WHILE input # ZeroPoly
DO
outTerm ←
NEW[PolynomialRec ← [
numVars: input.numVars,
data: nonconstant[leadingTerm: [
exponent: input.leadingTerm.exponent,
coefficient: PolynomialNegate[input.leadingTerm.coefficient]
],
reductum: ZeroPoly ]
] ];
input ← NARROW[input.reductum ];
IF previousOutTerm # ZeroPoly
THEN {
WITH previousOutTerm
SELECT FROM
previousOutTermVariant:
REF PolynomialRec.nonconstant => {
previousOutTermVariant.reductum ← outTerm;
previousOutTerm ← outTerm;
};
ENDCASE => ERROR;
}
ELSE out ← previousOutTerm ← outTerm;
ENDLOOP;
};
ENDCASE;
};
PolynomialSubtract:
PUBLIC PROC [in1, in2: Polynomial]
RETURNS [Polynomial] ~ {
RETURN[ PolynomialAdd[ in1, PolynomialNegate[ in2] ] ];
};
PolynomialMultiply:
PUBLIC PROC [in1, in2: Polynomial]
RETURNS [out: Polynomial] ~ {
previousOutSummandTerm, outSummandTerm, outSummand: Polynomial;
IF in1 = ZeroPoly OR in2 = ZeroPoly THEN RETURN[ZeroPoly];
IF in1.numVars # in2.numVars THEN ERROR;
WITH in1
SELECT FROM
input1:
REF PolynomialRec.constant => {
WITH in2
SELECT FROM
input2:
REF PolynomialRec.constant => {
val: RN.RatNum ← RN.RatNumMultiply[input1.value, input2.value];
out ←
NEW[PolynomialRec ← [
numVars: 0,
data: constant[value: val]
] ];
RETURN;
};
ENDCASE => ERROR;
};
input1:
REF PolynomialRec.nonconstant => {
WITH in2
SELECT FROM
input2:
REF PolynomialRec.nonconstant => {
scratchInput1: REF PolynomialRec.nonconstant;
out ← ZeroPoly;
WHILE input2 # ZeroPoly
DO
previousOutSummandTerm ← ZeroPoly;
scratchInput1 ← input1;
WHILE scratchInput1 # ZeroPoly
DO
coeff: Polynomial ← PolynomialMultiply[
scratchInput1.leadingTerm.coefficient,
input2.leadingTerm.coefficient
];
outSummandTerm ←
NEW[PolynomialRec ← [
numVars: scratchInput1.numVars,
data: nonconstant [ leadingTerm: [
exponent: scratchInput1.leadingTerm.exponent + input2.leadingTerm.exponent,
coefficient: coeff ],
reductum: ZeroPoly ]
] ];
IF previousOutSummandTerm # ZeroPoly
THEN
WITH previousOutSummandTerm
SELECT FROM
previousOutSummandTermVariant:
REF PolynomialRec.nonconstant => {
previousOutSummandTermVariant.reductum ← outSummandTerm;
previousOutSummandTerm ← outSummandTerm;
};
ENDCASE => ERROR
ELSE outSummand ← previousOutSummandTerm ← outSummandTerm;
scratchInput1 ← NARROW[ scratchInput1.reductum ];
ENDLOOP;
out ← PolynomialAdd[out, outSummand];
input2 ← NARROW[ input2.reductum ];
ENDLOOP;
};
ENDCASE => ERROR
};
ENDCASE;
};
***** Constructors *****
UnivariateMonomial:
PUBLIC PROC [coeff:
RN.RatNum, exp:
CARDINAL]
RETURNS [out: Polynomial] = {
RETURN[
NEW[ PolynomialRec ← [
numVars: 1,
data: nonconstant [ leadingTerm: [ exponent: exp,
coefficient:
NEW[ PolynomialRec ← [
numVars: 0,
data: constant [ coeff ]
] ] ],
reductum: ZeroPoly ]
] ] ];
};
MultivariateMonomial:
PUBLIC PROC [coeff: Polynomial, exp:
CARDINAL]
RETURNS [out: Polynomial] = {
RETURN[
NEW[ PolynomialRec ← [
numVars: coeff.numVars + 1,
data: nonconstant [ leadingTerm: [ exponent: exp,
coefficient: coeff ],
reductum: ZeroPoly ]
] ] ];
};
MakePolynomialZero:
PUBLIC PROC RETURNS [out: Polynomial ← ZeroPoly] = {};
Construct Polynomial representation for zero
***** Conversion and I/O - Public Routines *****
Variable Lists
ReadVariableList:
PUBLIC PROC [in:
IO.
STREAM]
RETURNS [V: VariableList] ~ {
puncChar: CHAR;
nextV: Rope.ROPE;
ReadVLFail: PUBLIC ERROR [subclass: ATOM ← $Unspecified] = CODE;
W, VTail: VariableList;
V ← NIL;
[]← in.SkipWhitespace[];
puncChar ← in.GetChar[ ];
[]← in.SkipWhitespace[];
IF puncChar # '( THEN ReadVLFail[$LeftParenExpected];
WHILE puncChar # ')
DO
nextV ← IO.GetID[in];
[]← in.SkipWhitespace[];
IF V=
NIL THEN VTail ← V ←
LIST[nextV]
ELSE
{ W ← LIST[nextV]; VTail.rest ← W; VTail ← W };
puncChar ← in.GetChar[ ];
[]← in.SkipWhitespace[];
IF puncChar # ') THEN IF puncChar # ', THEN ReadVLFail[$CommaExpected];
ENDLOOP;
};
VariableListFromRope:
PUBLIC PROC [in: Rope.
ROPE]
RETURNS [V: VariableList]={
VLStream: IO.STREAM ← IO.RIS[in];
RETURN[ ReadVariableList[ VLStream ] ];
};
VariableListToRope:
PUBLIC PROC [V: VariableList]
RETURNS [out: Rope.
ROPE]={
out ← "(";
WHILE V#
NIL DO
out ← Rope.Concat[ out, V.first ];
V ← V.rest;
IF V#NIL THEN out ← Rope.Concat[ out, "," ];
ENDLOOP;
out ← Rope.Concat[ out, ")" ];
};
WriteVariableList:
PUBLIC PROC [V: VariableList, out:
IO.
STREAM] = {
Write in a reasonable format
VLRope: Rope.ROPE ← VariableListToRope[V];
out.PutF["\n %g \n", IO.rope[VLRope] ];
};
ReadDPolynomial:
PUBLIC PROC [in:
IO.
STREAM, V: VariableList]
RETURNS [poly: DPolynomial] = {
legalTermStartSeen: BOOL;
coeff: RN.RatNum;
sign: INTEGER;
exponent: CARDINAL;
degreeVec: DegreeVector;
variable: Rope.ROPE;
varIndex: CARDINAL;
ReadDPFail: PUBLIC ERROR [subclass: ATOM ← $Unspecified] = CODE;
exponentChar1, exponentChar2: CHAR;
ok: BOOL;
poly ← NIL;
[]← in.SkipWhitespace[];
IF in.PeekChar[] = '0
THEN {
[] ← in.GetChar[]; -- toss it
[]← in.SkipWhitespace[];
IF in.GetChar[] = '$ THEN { poly← ZeroDPoly; RETURN } ELSE ReadDPFail[$UnexpectedCharacter];
};
DO -- the terms of a nonzero polynomial
legalTermStartSeen ← FALSE;
sign ← 1; -- default term (+1)
coeff ← RN.RatNumFromSmallCards[1,1,1];
degreeVec ← NIL;
[]← in.SkipWhitespace[];
IF in.PeekChar[] = '-
THEN {
sign ← -1;
[] ← in.GetChar[]; -- toss it
[]← in.SkipWhitespace[];
}
ELSE IF in.PeekChar[] = '+
THEN {
[] ← in.GetChar[]; -- toss it
[]← in.SkipWhitespace[];
};
SELECT in.PeekChar[]
FROM
IN ['0..'9] => {
-- coefficient present this term
legalTermStartSeen ← TRUE;
[coeff, ok] ← RN.ReadRatNum[in];
[]← in.SkipWhitespace[];
IF NOT ok THEN ReadDPFail[$BadCoefficient];
IF RN.RatNumZero[coeff] THEN ReadDPFail[$ZeroCoefficient];
};
ENDCASE;
IF sign < 1 THEN coeff ← RN.RatNumNegate[coeff]; -- if sign < 1, then negate either coeff read or default coeff of 1
WHILE Letter[in.PeekChar[] ]
DO -- variables present this term
legalTermStartSeen ← TRUE;
exponent ← 1;
variable ← in.GetID[];
[]← in.SkipWhitespace[];
varIndex ← VariableIndex[variable, V];
IF varIndex = 0 THEN ReadDPFail[$UnknownVariable];
IF in.PeekChar[] = '*
OR in.PeekChar[] = '^
THEN {
-- allow either ** or ^
exponentChar1 ← in.GetChar[];
IF exponentChar1 ='*
THEN {
exponentChar2 ← in.GetChar[];
IF exponentChar2 # '* THEN ReadDPFail[$SingleAsteriskExponent];
};
[]← in.SkipWhitespace[];
SELECT in.PeekChar[]
FROM
IN ['0..'9] => {
exponent ← in.GetCard;
[]← in.SkipWhitespace[];
IF exponent = 0 THEN ReadDPFail[$ZeroExponent];
};
ENDCASE=> ReadDPFail[$NonNumericExponent];
};
[ok, degreeVec] ← DVInsertVariablePower[varIndex, exponent, degreeVec];
IF NOT ok THEN ReadDPFail[$RepeatedVariable];
ENDLOOP; -- end of this term
IF legalTermStartSeen
THEN {
-- if we arrive here, we saw a complete legal term
[ok, poly] ← DPInsertTerm[coeff, degreeVec, poly];
IF NOT ok THEN ReadDPFail[$RepeatedMonomial];
}
ELSE ReadDPFail[$UnexpectedCharacter];
IF in.PeekChar[] = '$ THEN RETURN;
ENDLOOP;
};
DPolynomialFromRope:
PUBLIC PROC [in: Rope.
ROPE, V: VariableList]
RETURNS [out: DPolynomial] = {
stream: IO.STREAM ← IO.RIS[in];
out ← ReadDPolynomial[stream, V];
};
DPolynomialToRope:
PUBLIC PROC [in: DPolynomial, V: VariableList]
RETURNS [out: Rope.
ROPE]={
One: RN.RatNum = RN.RatNumFromSmallCards[1,1,1];
firstTerm: BOOL ← TRUE;
trivialMonomial: BOOL;
coeff, coeffAbs: RN.RatNum;
degreeVec: DegreeVector;
coeffSign: RN.Sign;
exponent, index: CARDINAL;
IF in = ZeroDPoly THEN RETURN["0 $"];
out ← "";
WHILE in#
NIL DO
[coeff, degreeVec] ← in.first; in ← in.rest;
coeffSign ← coeff.sign;
coeffAbs ← RN.RatNumABS[coeff];
IF coeffSign=NEGATIVE THEN out ← Rope.Concat[out,"- "] ELSE IF NOT firstTerm THEN out ← Rope.Concat[out,"+ "];
firstTerm ← FALSE;
IF NOT RN.RatNumEqual[coeffAbs, One] THEN out ← Rope.Cat[out, RN.RatNumToRatRope[coeffAbs], " "];
trivialMonomial ← TRUE;
degreeVec ← DVReverse[degreeVec];
WHILE degreeVec#
NIL DO
trivialMonomial ← FALSE;
exponent ← degreeVec.first; degreeVec ← degreeVec.rest;
index ← degreeVec.first; degreeVec ← degreeVec.rest;
out ← Rope.Concat[out, Variable[V, index] ];
IF exponent>1 THEN out ← Rope.Cat[out, "^", Convert.RopeFromCard[exponent]];
out ← Rope.Concat[out," "];
ENDLOOP;
IF trivialMonomial AND RN.RatNumEqual[coeffAbs, One] THEN out ← Rope.Cat[out, RN.RatNumToRatRope[coeffAbs], " "];
ENDLOOP;
out ← Rope.Concat[out,"$"];
};
WriteDPolynomial:
PUBLIC PROC [in: DPolynomial, V: VariableList, out:
IO.
STREAM] = {
polyRope: Rope.ROPE ← DPolynomialToRope[in, V];
out.PutF["\n %g \n", IO.rope[polyRope] ];
};
PolyFromDPoly:
PUBLIC PROC [in: DPolynomial, V: VariableList]
RETURNS [out: Polynomial] = {
numVars: CARDINAL = NumVars[V]; -- we need V arg to get this number
termDegree: CARDINAL; -- degree in main variable of current (output) term
outTermDCoefficient: DPolynomial; -- output term coefficient, still in DP rep
outTermCoefficient: Polynomial; -- output term coefficient, converted to P rep
outTerm: Polynomial; -- completed output term
previousTerm: Polynomial;
IF in = ZeroDPoly THEN RETURN[ZeroPoly];
IF numVars=0
THEN {
out ←
NEW[PolynomialRec ← [
numVars: 0,
data: constant[value: in.first.coefficient]
] ];
RETURN;
};
previousTerm ← ZeroPoly;
WHILE in#
NIL DO
termDegree ← DVDegree[in.first.degreeVector, numVars]; -- degree in main variable
outTermDCoefficient ← LIST[ [in.first.coefficient, DVRemoveMainVariablePower[in.first.degreeVector, numVars] ] ];
in ← in.rest;
WHILE in#
NIL AND DVDegree[in.first.degreeVector, numVars] = termDegree
DO
outTermDCoefficient ← CONS[ [in.first.coefficient, DVRemoveMainVariablePower[in.first.degreeVector, numVars] ], outTermDCoefficient];
in ← in.rest;
ENDLOOP;
outTermDCoefficient ← DPReverse[ outTermDCoefficient ];
outTermCoefficient ← PolyFromDPoly[ outTermDCoefficient, VLRemoveMainVariable[V] ];
outTerm ←
NEW[PolynomialRec ← [
numVars: numVars,
data: nonconstant [ leadingTerm: [ exponent: termDegree,
coefficient: outTermCoefficient ],
reductum: ZeroPoly ]
] ];
IF previousTerm # ZeroPoly
THEN {
WITH previousTerm
SELECT FROM
previousTermVariant:
REF PolynomialRec.nonconstant => {
previousTermVariant.reductum ← outTerm;
previousTerm ← outTerm;
};
ENDCASE => ERROR;
}
ELSE out ← previousTerm ← outTerm;
ENDLOOP;
};
DPolyFromPoly:
PUBLIC PROC [in: Polynomial, V: VariableList]
RETURNS [out: DPolynomial] ~ {
numVars: CARDINAL = NumVars[V]; -- we need V arg to get this number
inTermDegree: CARDINAL; -- degree in main variable of current (input) term
inTermDPolynomial: DPolynomial;
IF in = ZeroPoly THEN RETURN[ZeroDPoly];
IF numVars#in.numVars THEN ERROR; -- consistency check
WITH in
SELECT FROM
input: REF PolynomialRec.constant => RETURN[ LIST[ [input.value, NIL] ] ];
input:
REF PolynomialRec.nonconstant => {
out ← ZeroDPoly;
WHILE input # ZeroPoly
DO
inTermDegree ← input.leadingTerm.exponent;
inTermDPolynomial ← DPolyFromPoly[input.leadingTerm.coefficient, VLRemoveMainVariable[V] ];
WHILE inTermDPolynomial#
NIL DO
out ← CONS[ [ inTermDPolynomial.first.coefficient, DVAddMainVariablePower[inTermDPolynomial.first.degreeVector, numVars, inTermDegree] ], out];
inTermDPolynomial ← inTermDPolynomial.rest;
ENDLOOP;
input ← NARROW[ input.reductum ];
ENDLOOP;
out ← DPReverse[out];
};
ENDCASE;
};
ReadPolynomial:
PUBLIC PROC [in:
IO.
STREAM, V: VariableList]
RETURNS [poly: Polynomial] = {
RETURN[ PolyFromDPoly[ ReadDPolynomial[in, V], V ] ];
};
PolynomialFromRope:
PUBLIC PROC [in: Rope.
ROPE, V: VariableList]
RETURNS [out: Polynomial] = {
stream: IO.STREAM ← IO.RIS[in];
out ← ReadPolynomial[stream, V];
};
PolynomialSAC2RepToRope:
PUBLIC PROC [in: Polynomial]
RETURNS [out: Rope.
ROPE] = {
Dump the internal representation in SAC2 list format
IF in = ZeroPoly THEN RETURN[ "()"];
WITH in
SELECT FROM
input:
REF PolynomialRec.constant =>
RETURN[ RN.RatNumToRatRope[input.value, FALSE, TRUE] ]; -- show denom of 1
input:
REF PolynomialRec.nonconstant => {
out ← "( ";
WHILE input # ZeroPoly
DO
out ← Rope.Cat[ out,
Convert.RopeFromCard[input.leadingTerm.exponent],
", ",
PolynomialSAC2RepToRope[ input.leadingTerm.coefficient]
];
input ← NARROW[ input.reductum ];
IF input # ZeroPoly THEN out ← Rope.Concat[ out, ", " ];
ENDLOOP;
RETURN[ Rope.Concat[ out, " )" ] ];
};
ENDCASE;
};
PolynomialToRope:
PUBLIC PROC [in: Polynomial, V: VariableList]
RETURNS [out: Rope.
ROPE] = {
Write in a reasonable form
numVars: CARDINAL = NumVars[V]; -- we need V arg to get this number
IF in = ZeroPoly THEN RETURN["0"];
WITH in
SELECT FROM
input:
REF PolynomialRec.constant => {
IF RN.RatNumPositive[input.value] THEN out ← " + " ELSE out ← "";
out ← "";
RETURN[ Rope.Concat[ out, RN.RatNumToRatRope[input.value] ] ];
};
input:
REF PolynomialRec.nonconstant => {
out ← "( ";
WHILE input # ZeroPoly
DO
out ← Rope.Cat[ out,
PolynomialToRope[ input.leadingTerm.coefficient, VLRemoveMainVariable[V]],
" ",
Variable[V, numVars],
Rope.Cat["^", Convert.RopeFromCard[input.leadingTerm.exponent] ]
];
input ← NARROW[ input.reductum ];
IF input # ZeroPoly THEN out ← Rope.Concat[ out, " + " ];
ENDLOOP;
RETURN[ Rope.Concat[ out, " )" ] ];
};
ENDCASE;
};
WritePolynomial:
PUBLIC PROC [in: Polynomial, V: VariableList, out:
IO.
STREAM] = {
Write in a reasonable format
polyRope: Rope.ROPE ← PolynomialToRope[in, V];
out.PutF["\n %g \n", IO.rope[polyRope] ];
};
***** Conversion and I/O - Private Routines *****
Variable Lists
VariableIndex:
PROC [var: Rope.
ROPE, V: VariableList ]
RETURNS [index:
CARDINAL] ~ {
v: Rope.ROPE;
index ← 1;
WHILE V#
NIL DO
v ← V.first; V← V.rest;
IF Rope.Equal[var, v] THEN RETURN;
index ← index+1;
ENDLOOP;
index ← 0;
};
Variable:
PROC [V: VariableList, index:
CARDINAL]
RETURNS [var: Rope.
ROPE] ~ {
FOR i: CARDINAL IN [1..index-1] DO V ← V.rest; ENDLOOP;
RETURN[ V.first ];
};
VLRemoveMainVariable:
PROC [V: VariableList]
RETURNS [VariableList] ~ {
RETURN[VLReverse[ VLReverse[V].rest ] ];
};
NumVars:
PROC [V: VariableList]
RETURNS [r:
CARDINAL] ~ {
Length of V
r ← 0;
WHILE V#
NIL DO
r ← r+1; V ← V.rest;
ENDLOOP;
};
Letter:
PROC [C:
CHAR]
RETURNS [
BOOL] ~
INLINE {
RETURN[ (0 <= C - 'A AND C - 'A < 26) OR (0 <= C - 'a AND C - 'a < 26)];
};
VLReverse:
PROC [list: VariableList]
RETURNS[val: VariableList] = {
val ← NIL;
UNTIL list =
NIL DO
val ← CONS[list.first, val];
list ← list.rest;
ENDLOOP;
RETURN[val];
}; -- of Reverse
Degree Vectors
DVInsertVariablePower:
PROC [varIndex, exponent:
CARDINAL, inDegreeVec: DegreeVector]
RETURNS [ok:
BOOL, outDegreeVec: DegreeVector] ~ {
Variable varIndex raised to the exponent power is recorded in inDegreeVec. NOT ok if the variable already occurs (and inDegreeVec unchanged). If the variable doesn't yet occur, then ok; if exponent = 0, inDegreeVec unchanged, otherwise outDegreeVec is inDegreeVec with (varIndex, exponent) inserted.
DVInsertVariablePower is an insertion sort.
nextIndex, nextExponent: CARDINAL;
degreeVec: DegreeVector ← inDegreeVec;
outDegreeVec ← inDegreeVec;
ok ← TRUE;
IF inDegreeVec=
NIL THEN {
IF exponent=0
THEN RETURN ELSE {
outDegreeVec←CONS[varIndex, CONS[ exponent, NIL] ];
RETURN
}
};
nextIndex ← degreeVec.first; degreeVec ← degreeVec.rest;
nextExponent ← degreeVec.first; degreeVec ← degreeVec.rest;
SELECT varIndex
FROM
= nextIndex => { ok ← FALSE; RETURN };
> nextIndex =>
IF exponent=0
THEN RETURN ELSE {
outDegreeVec←CONS[varIndex, CONS[exponent, inDegreeVec] ];
RETURN
};
ENDCASE;
outDegreeVec ← CONS[nextExponent, CONS[nextIndex, NIL]];
WHILE degreeVec#
NIL DO
nextIndex ← degreeVec.first; degreeVec ← degreeVec.rest;
nextExponent ← degreeVec.first; degreeVec ← degreeVec.rest;
SELECT varIndex
FROM
= nextIndex => { outDegreeVec ← inDegreeVec;ok ← FALSE; RETURN };
> nextIndex =>
IF exponent=0
THEN
{ outDegreeVec ← inDegreeVec; RETURN }
ELSE {
outDegreeVec𡤍VCons4[nextExponent, nextIndex, exponent, varIndex, outDegreeVec];
outDegreeVec ← DVReverse[outDegreeVec];
outDegreeVec ← DVNconc[outDegreeVec, degreeVec];
RETURN
};
ENDCASE;
outDegreeVec ← CONS[nextExponent, CONS[nextIndex, outDegreeVec]];
ENDLOOP;
outDegreeVec ← CONS[exponent, CONS[varIndex, outDegreeVec]];
outDegreeVec ← DVReverse[outDegreeVec];
};
DVCompare:
PROC [dv1, dv2: DegreeVector]
RETURNS [ [-1..1] ] ~ {
index1, index2, exponent1, exponent2: CARDINAL;
WHILE dv1#
NIL AND dv2#
NIL DO
index1 ← dv1.first; dv1 ← dv1.rest;
exponent1 ← dv1.first; dv1 ← dv1.rest;
index2 ← dv2.first; dv2 ← dv2.rest;
exponent2 ← dv2.first; dv2 ← dv2.rest;
IF index1 > index2 THEN RETURN[1];
IF index1 < index2 THEN RETURN[-1];
IF exponent1 > exponent2 THEN RETURN[1];
IF exponent1 < exponent2 THEN RETURN[-1];
ENDLOOP;
IF dv1#NIL THEN RETURN[1];
IF dv2#NIL THEN RETURN[-1];
RETURN[0];
};
DVDegree:
PROC [degreeVec: DegreeVector, numVars:
CARDINAL]
RETURNS [degree:
CARDINAL] ~ {
IF degreeVec = NIL THEN RETURN[0];
IF degreeVec.first = numVars THEN RETURN[degreeVec.rest.first] ELSE RETURN[0];
};
DVRemoveMainVariablePower:
PROC [in: DegreeVector, numVars:
CARDINAL]
RETURNS [out: DegreeVector] ~ {
IF in = NIL THEN RETURN[NIL];
IF in.first = numVars THEN RETURN [in.rest.rest] ELSE RETURN[in];
};
DVAddMainVariablePower:
PROC [in: DegreeVector, varIndex, exponent:
CARDINAL]
RETURNS [out: DegreeVector] ~ {
IF exponent>0 THEN RETURN[ CONS[varIndex, CONS[ exponent, in] ] ] ELSE RETURN[in];
};
DVCons4:
PROC [x1, x2, x3, x4:
CARDINAL, degreeVec: DegreeVector]
RETURNS [DegreeVector] ~
INLINE {
RETURN[ CONS[x1, CONS[x2, CONS[x3, CONS[x4, degreeVec]]]] ];
};
DVNconc:
PROC [l1, l2: DegreeVector]
RETURNS [DegreeVector] ~ {
z: DegreeVector ← l1;
IF z = NIL THEN RETURN[l2];
UNTIL z.rest =
NIL DO
z ← z.rest;
ENDLOOP;
z.rest ← l2;
RETURN[l1];
};
DVReverse:
PROC [list: DegreeVector]
RETURNS[val: DegreeVector] = {
val ← NIL;
UNTIL list =
NIL DO
val ← CONS[list.first, val];
list ← list.rest;
ENDLOOP;
RETURN[val];
}; -- of Reverse
Distributed Polynomials
DPInsertTerm:
PROC [coefficient:
RN.RatNum, degreeVec: DegreeVector, inPoly: DPolynomial]
RETURNS [ok: BOOL, outPoly: DPolynomial] ~ {
The term (coefficient, degreeVec) is inserted in the distributed polynoimal inPoly. NOT ok if degreeVec already occurs (and inPoly unchanged). If degreeVec doesn't yet occur, then ok, and outPoly is inPoly with (coefficient, degreeVec) inserted.
DPInsertTerm is an insertion sort.
nextCoeff: RN.RatNum;
nextDegreeVec: DegreeVector;
poly: DPolynomial ← inPoly;
degreeVecComparison: [-1..1];
ok ← TRUE;
IF inPoly=
NIL THEN {
outPoly←CONS[ [coefficient, degreeVec], NIL ];
RETURN
};
outPoly ← inPoly;
[nextCoeff, nextDegreeVec] ← poly.first; poly ← poly.rest;
degreeVecComparison ← DVCompare[degreeVec, nextDegreeVec];
SELECT degreeVecComparison
FROM
0 => { ok ← FALSE; RETURN };
1 => {
outPoly←CONS[ [coefficient, degreeVec], inPoly ];
RETURN
};
ENDCASE;
outPoly ← CONS[ [nextCoeff, nextDegreeVec], NIL];
WHILE poly#
NIL DO
[nextCoeff, nextDegreeVec] ← poly.first; poly ← poly.rest;
degreeVecComparison ← DVCompare[degreeVec, nextDegreeVec];
SELECT degreeVecComparison
FROM
0 => { outPoly ← inPoly; ok ← FALSE; RETURN };
1 => {
outPoly ← CONS[ [nextCoeff, nextDegreeVec], CONS[ [coefficient, degreeVec], outPoly] ];
outPoly ← DPReverse[outPoly];
outPoly ← DPNconc[outPoly, poly];
RETURN
};
ENDCASE;
outPoly ← CONS[ [nextCoeff, nextDegreeVec], outPoly];
ENDLOOP;
outPoly ← CONS[ [coefficient, degreeVec], outPoly];
outPoly ← DPReverse[outPoly];
};
DPNconc:
PROC [l1, l2: DPolynomial]
RETURNS [DPolynomial] ~ {
z: DPolynomial ← l1;
IF z = NIL THEN RETURN[l2];
UNTIL z.rest =
NIL DO
z ← z.rest;
ENDLOOP;
z.rest ← l2;
RETURN[l1];
};
DPReverse:
PROC [list: DPolynomial]
RETURNS[val: DPolynomial] = {
val ← NIL;
UNTIL list =
NIL DO
val ← CONS[list.first, val];
list ← list.rest;
ENDLOOP;
RETURN[val];
}; -- of Reverse
END.