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.