<> <> <> <> <<>> DIRECTORY Convert USING [AtomFromRope, Error, IntFromRope, RealFromRope, RopeFromAtom, RopeFromInt, RopeFromReal], IO USING [BreakProc, CharClass, EndOfStream, GetTokenRope, NUL, RIS, SP, STREAM], MultiPolynomial, Polynomial USING [Constant, Degree, Linear, Product, Ref, Sum], Rope USING [Compare, Concat, Fetch, Length, ROPE]; MultiPolynomialImpl: CEDAR PROGRAM IMPORTS Convert, IO, Polynomial, Rope EXPORTS MultiPolynomial ~ BEGIN <<>> <> <<>> <> <<>> <> <<>> <<>> <> <<>> Ref: TYPE ~ MultiPolynomial.Ref; MultiPolRec: TYPE ~ MultiPolynomial.MultiPolRec; Monomial: TYPE ~ MultiPolynomial.Monomial; PoweredVariable: TYPE ~ MultiPolynomial.PoweredVariable; PoweredVariableSequence: TYPE ~ MultiPolynomial.PoweredVariableSequence; EvaluationBinding: TYPE ~ MultiPolynomial.EvaluationBinding; EvaluationBindings: TYPE ~ MultiPolynomial.EvaluationBindings; SubstitutionBinding: TYPE ~ MultiPolynomial.SubstitutionBinding; SubstitutionBindings: TYPE ~ MultiPolynomial.SubstitutionBindings; TSUBinding: TYPE ~ MultiPolynomial.TSUBinding; TSUBindings: TYPE ~ MultiPolynomial.TSUBindings; Error: PUBLIC ERROR[reason: ErrorCode] = CODE; ErrorCode: TYPE ~ MultiPolynomial.ErrorCode; <<>> <> <<>> UnivariateFromRef: PUBLIC PROC [a: Ref, var: ATOM] RETURNS [result: Polynomial.Ref] ~ BEGIN <> x: Polynomial.Ref Ź Polynomial.Linear[[0, 1]]; intermediate: Polynomial.Ref; degree: NAT Ź Degree[a]; <> CoeffSeq: TYPE ~ RECORD[coeffs: SEQUENCE length: NAT OF REAL]; coefficients: REF CoeffSeq Ź NEW[CoeffSeq[degree + 1]]; FOR i: NAT IN [0..coefficients.length) DO coefficients[i] Ź 0; ENDLOOP; <> FOR i: NAT IN [0..a.length) DO SELECT a[i].vars.numVars FROM =0 => coefficients[0] Ź coefficients[0] + a[i].coefficient; =1 => IF a[i].vars[0].variable= var THEN coefficients[a[i].vars[0].degree] Ź coefficients[a[i].vars[0].degree] + a[i].coefficient ELSE ERROR Error[NotUnivariate]; >1 => ERROR Error[NotUnivariate]; ENDCASE; ENDLOOP; <> intermediate Ź Polynomial.Constant[[0]]; FOR i: NAT IN [0..degree] DO newConstantTerm: Polynomial.Ref Ź Polynomial.Constant[[coefficients[degree - i]]]; intermediate Ź Polynomial.Product[intermediate, x]; intermediate Ź Polynomial.Sum[intermediate, newConstantTerm]; ENDLOOP; result Ź intermediate; END; RefFromUnivariate: PUBLIC PROC [pol: Polynomial.Ref, var: ATOM] RETURNS [result: Ref] ~ BEGIN degree: NAT Ź Polynomial.Degree[pol]; intermediate: Ref Ź NEW[MultiPolRec[degree + 1]]; IF ~LegalVariableName[var] THEN ERROR Error[BadVariableName]; FOR i: NAT IN [0..degree] DO vars: REF PoweredVariableSequence Ź NEW[PoweredVariableSequence[1]]; vars[0] Ź [variable: var, degree: i]; intermediate[i] Ź [coefficient: PolynomialCoefficient[pol, i], vars: vars]; ENDLOOP; result Ź Compact[intermediate]; END; RealFromRef: PUBLIC PROC [a: Ref] RETURNS [constantTerm: REAL] ~ BEGIN SELECT a.length FROM 0 => RETURN[0]; 1 => IF a[0].vars.numVars = 0 THEN RETURN[a[0].coefficient]; ENDCASE; ERROR Error[NotConstant]; END; RopeFromRef: PUBLIC PROC [a: Ref] RETURNS [r: Rope.ROPE] ~ BEGIN result: Rope.ROPE Ź ""; FOR i: NAT IN [0..a.length) DO thisMonomial: Monomial Ź a[i]; <> IF i = 0 THEN {IF a[i].coefficient < 0 THEN result Ź Rope.Concat[result, "-"]} ELSE {IF a[i].coefficient < 0 THEN result Ź Rope.Concat[result, " - "] ELSE result Ź Rope.Concat[result, " + "]}; result Ź Rope.Concat[result, Convert.RopeFromReal[ABS[thisMonomial.coefficient]]]; FOR j: NAT IN [0..thisMonomial.vars.numVars) DO thisVar: PoweredVariable Ź thisMonomial.vars[j]; SELECT thisVar.degree FROM =0 => {}; =1 => result Ź Rope.Concat[result, Convert.RopeFromAtom[thisVar.variable, FALSE]]; >1 => {result Ź Rope.Concat[result, Convert.RopeFromAtom[thisVar.variable, FALSE]]; result Ź Rope.Concat[result, "^"]; result Ź Rope.Concat[result, Convert.RopeFromInt[thisVar.degree]];}; ENDCASE; ENDLOOP; ENDLOOP; IF a.length = 0 THEN result Ź "0.0"; r Ź result; END; RefFromRope: PUBLIC PROC [rope: Rope.ROPE] RETURNS [result: Ref] ~ BEGIN <> intermRef: Ref; <> inStream: IO.STREAM Ź IO.RIS[rope]; <> BreakProc: IO.BreakProc ~ BEGIN charClass: IO.CharClass; SELECT char FROM IN [IO.NUL .. IO.SP] => charClass Ź sepr; '+, '-, '^ => charClass Ź break; IN ['a..'z], IN ['A..'Z] => charClass Ź break; IN ['0..'9], '. => charClass Ź other; ENDCASE => ERROR Error[BadFormat]; RETURN [charClass]; END; <> NextToken: PROC [stream: IO.STREAM Ź inStream] RETURNS [Rope.ROPE] ~ BEGIN token: Rope.ROPE; [token: token] Ź IO.GetTokenRope[stream, BreakProc]; RETURN[token]; END; <> TemporaryMultiPolRec: TYPE ~ RECORD [ numberOfMonomials: NAT, monomials: LIST OF TemporaryMonomial]; TemporaryMonomial: TYPE ~ RECORD [ sign: Rope.ROPE, coefficient: REAL, numberOfVariables: NAT, poweredVariables: LIST OF PoweredVariable]; temporaryMultiPol: TemporaryMultiPolRec; currentMonomial: TemporaryMonomial; FlushTemporaryMultiPol: PROC[] ~ BEGIN temporaryMultiPol Ź [0, NIL]; END; ClearCurrentMonomial: PROC[] ~ BEGIN currentMonomial Ź ["+", 1.0, 0, NIL]; END; StoreCurrentMonomial: PROC[] ~ BEGIN temporaryMultiPol.monomials Ź CONS[currentMonomial, temporaryMultiPol.monomials]; END; AddNewTerm: PROC[sign: Rope.ROPE] ~ BEGIN IF temporaryMultiPol.numberOfMonomials > 0 THEN StoreCurrentMonomial[]; temporaryMultiPol.numberOfMonomials Ź temporaryMultiPol.numberOfMonomials + 1; ClearCurrentMonomial[]; currentMonomial.sign Ź sign; END; ChangeCoefficient: PROC[coeff: Rope.ROPE] ~ BEGIN currentMonomial.coefficient Ź Convert.RealFromRope[coeff ! Convert.Error => {ERROR Error[BadFormat]}]; END; AddNewVariable: PROC[var: Rope.ROPE] ~ BEGIN currentMonomial.numberOfVariables Ź currentMonomial.numberOfVariables + 1; currentMonomial.poweredVariables Ź CONS [ [variable: Convert.AtomFromRope[var], degree: 1], currentMonomial.poweredVariables]; END; ChangePower: PROC[power: Rope.ROPE] ~ BEGIN currentMonomial.poweredVariables.first.degree Ź Convert.IntFromRope[power ! Convert.Error => {ERROR Error[BadFormat]}]; END; <> MonomialFromTemporary: PROC[temp: TemporaryMonomial] RETURNS[Monomial] ~ BEGIN vars: REF PoweredVariableSequence Ź NEW[PoweredVariableSequence[temp.numberOfVariables]]; coefficient: REAL Ź temp.coefficient; poweredVariableList: LIST OF PoweredVariable Ź temp.poweredVariables; index: NAT Ź temp.numberOfVariables; UNTIL poweredVariableList = NIL DO index Ź index - 1; vars[index] Ź poweredVariableList.first; poweredVariableList Ź poweredVariableList.rest; ENDLOOP; IF Rope.Compare[temp.sign, "-"] = equal THEN coefficient Ź - coefficient; RETURN[FixUpMonomial[[coefficient, vars]]]; END; RefFromTemporary: PROC RETURNS[Ref] ~ BEGIN temp: TemporaryMultiPolRec Ź temporaryMultiPol; result: Ref Ź NEW[MultiPolRec[temp.numberOfMonomials]]; monomialList: LIST OF TemporaryMonomial Ź temp.monomials; index: NAT Ź temp.numberOfMonomials; UNTIL monomialList = NIL DO index Ź index - 1; result[index] Ź MonomialFromTemporary[monomialList.first]; monomialList Ź monomialList.rest; ENDLOOP; RETURN[result]; END; <> TokenType: TYPE ~ {sign, coefficient, variable, caret, exponent, begin, end, error}; <> previousTokenType: TokenType Ź begin; FlushTemporaryMultiPol[]; ClearCurrentMonomial[]; UNTIL previousTokenType = end DO <> nextToken: Rope.ROPE; firstCharOfNextToken: CHAR; nextTokenType: TokenType; <> nextToken Ź NextToken[! IO.EndOfStream => {nextToken Ź "&EOS"; CONTINUE}]; firstCharOfNextToken Ź Rope.Fetch[nextToken, 0]; nextTokenType Ź SELECT firstCharOfNextToken FROM IN ['a..'z], IN ['A..'Z] => variable, IN ['0..'9], '. => IF previousTokenType = caret THEN exponent ELSE coefficient, '+, '- => sign, '^ => caret, '& => end, ENDCASE => error; <> SELECT previousTokenType FROM begin => SELECT nextTokenType FROM sign => AddNewTerm[sign: nextToken]; coefficient => {AddNewTerm[sign: "+"]; ChangeCoefficient[nextToken]}; variable => {AddNewTerm[sign: "+"]; AddNewVariable[nextToken]}; ENDCASE => ERROR Error[BadFormat]; sign => SELECT nextTokenType FROM coefficient => ChangeCoefficient[nextToken]; variable => AddNewVariable[nextToken]; ENDCASE => ERROR Error[BadFormat]; coefficient => SELECT nextTokenType FROM sign => AddNewTerm[sign: nextToken]; variable => AddNewVariable[nextToken]; end => {}; ENDCASE => ERROR Error[BadFormat]; variable => SELECT nextTokenType FROM sign => AddNewTerm[sign: nextToken]; variable => AddNewVariable[nextToken]; caret => {}; end => {}; ENDCASE => ERROR Error[BadFormat]; caret => SELECT nextTokenType FROM exponent => ChangePower[nextToken]; ENDCASE => ERROR Error[BadFormat]; exponent => SELECT nextTokenType FROM sign => AddNewTerm[sign: nextToken]; variable => AddNewVariable[nextToken]; end => {}; ENDCASE => ERROR Error[BadFormat]; ENDCASE => ERROR Error[InternalError]; <> previousTokenType Ź nextTokenType; ENDLOOP; <> StoreCurrentMonomial[]; intermRef Ź RefFromTemporary[]; result Ź Compact[RefFromTemporary[]]; END; <<>> <> <<>> Sum: PUBLIC PROC [a, b: Ref] RETURNS [r: Ref] ~ BEGIN r Ź Compact[AddRefsWithoutCompaction[a, b]]; END; Difference: PUBLIC PROC [a, b: Ref] RETURNS [r: Ref] ~ BEGIN r Ź Sum[a, Scale[b, -1]]; END; Product: PUBLIC PROC [a, b: Ref] RETURNS [r: Ref] ~ BEGIN r Ź Compact[MultiplyRefsWithoutCompaction[a, b]]; END; Power: PUBLIC PROC [a: Ref, n: NAT] RETURNS [r: Ref] ~ BEGIN intermediate: Ref Ź RefFromRope["1"]; FOR i: NAT IN [1..n] DO intermediate Ź Product[intermediate, a]; ENDLOOP; r Ź intermediate; END; Scale: PUBLIC PROC [p: Ref, c: REAL] RETURNS [r: Ref] ~ BEGIN intermediate: Ref Ź NEW[MultiPolRec[p.length]]; FOR i: NAT IN [0..p.length) DO intermediate[i] Ź [coefficient: p[i].coefficient * c, vars: p[i].vars]; ENDLOOP; r Ź Compact[intermediate]; END; Differentiate: PUBLIC PROC [a: Ref, var: ATOM] RETURNS [r: Ref] ~ BEGIN intermediate: Ref Ź NEW[MultiPolRec[a.length]]; FOR i: NAT IN [0..a.length) DO intermediate[i] Ź DifferentiateMonomial[a[i], var]; ENDLOOP; r Ź Compact[intermediate]; END; Degree: PUBLIC PROC [a: Ref] RETURNS [d: NAT] ~ BEGIN degree: NAT Ź 0; FOR i: NAT IN [0..a.length) DO degree Ź MAX[degree, MonomialDegree[a[i]]]; ENDLOOP; d Ź degree; END; <<>> <<>> <> <<>> Evaluate: PUBLIC PROC [a: Ref, variable: ATOM, value: REAL] RETURNS [result: Ref] ~ BEGIN break: SIGNAL = CODE; intermediate: Ref Ź NEW[MultiPolRec[a.length]]; <> FOR i: NAT IN [0..a.length) DO thisMonomial: Monomial Ź a[i]; newCoefficient: REAL; newVars: REF PoweredVariableSequence; <> variablePresent: BOOLEAN; variablePosition: NAT; [variablePresent, variablePosition] Ź VariablePositionInMonomial[thisMonomial, variable]; <> IF variablePresent THEN BEGIN degree: NAT Ź thisMonomial.vars[variablePosition].degree; newCoefficient Ź thisMonomial.coefficient * IntegerPower[value, degree]; newVars Ź NEW[PoweredVariableSequence[thisMonomial.vars.numVars - 1]]; FOR j: NAT IN [0..variablePosition) DO newVars[j] Ź thisMonomial.vars[j]; ENDLOOP; FOR j: NAT IN (variablePosition..thisMonomial.vars.numVars) DO newVars[j-1] Ź thisMonomial.vars[j]; ENDLOOP; END <> ELSE BEGIN newCoefficient Ź thisMonomial.coefficient; newVars Ź NEW[PoweredVariableSequence[thisMonomial.vars.numVars]]; FOR j: NAT IN [0..thisMonomial.vars.numVars) DO newVars[j] Ź thisMonomial.vars[j]; ENDLOOP; END; <> intermediate[i] Ź [coefficient: newCoefficient, vars: newVars]; ENDLOOP; <> result Ź Compact[intermediate]; END; EvaluateList: PUBLIC PROC [a: Ref, bindings: EvaluationBindings] RETURNS [result: Ref] ~ BEGIN bindingList: EvaluationBindings Ź bindings; intermediate: Ref Ź a; UNTIL bindingList = NIL DO intermediate Ź Evaluate[intermediate, bindingList.first.variable, bindingList.first.value]; bindingList Ź bindingList.rest; ENDLOOP; result Ź intermediate; END; TotallyEvaluate: PUBLIC PROC [a: Ref, bindings: EvaluationBindings] RETURNS [result: REAL] ~ BEGIN intermediate: Ref Ź EvaluateList[a, bindings]; value: REAL; value Ź RealFromRef[intermediate ! Error => IF reason=NotConstant THEN GOTO UVError]; result Ź value; EXITS UVError => ERROR Error[UnsubstitutedVariables]; END; Substitute: PUBLIC PROC [a: Ref, variable: ATOM, replacement: Ref] RETURNS [result: Ref] ~ BEGIN intermediate: Ref Ź NEW[MultiPolRec[0]]; <> FOR i: NAT IN [0..a.length) DO thisMonomial: Monomial Ź a[i]; newMonomial: Monomial; newPolynomial: Ref; <> variablePresent: BOOL Ź FALSE; variablePosition: NAT; FOR j: NAT IN [0..thisMonomial.vars.numVars) DO IF thisMonomial.vars[j].variable = variable THEN { variablePresent Ź TRUE; variablePosition Ź j} ENDLOOP; <> IF variablePresent THEN BEGIN degree: NAT Ź thisMonomial.vars[variablePosition].degree; thisMonomialConvertedToPoly: Ref Ź NEW[MultiPolRec[1]]; thisMonomialConvertedToPoly[0] Ź thisMonomial; newMonomial Ź Evaluate[thisMonomialConvertedToPoly, variable, 1][0]; newPolynomial Ź MultiplyMonomialByRef[newMonomial, Power[replacement, degree]]; END <<>> <> ELSE BEGIN newPolynomial Ź NEW[MultiPolRec[1]]; newPolynomial[0] Ź thisMonomial; END; <> intermediate Ź AddRefsWithoutCompaction[intermediate, newPolynomial]; ENDLOOP; <> result Ź Compact[intermediate]; END; SubstituteList: PUBLIC PROC [a: Ref, bindings: SubstitutionBindings] RETURNS [result: Ref] ~ BEGIN bindingList: SubstitutionBindings Ź bindings; intermediate: Ref Ź a; UNTIL bindingList = NIL DO intermediate Ź Substitute[ intermediate, bindingList.first.variable, bindingList.first.replacement]; bindingList Ź bindingList.rest; ENDLOOP; result Ź intermediate; END; TotallySubstituteUnivariates: PUBLIC PROC [a: Ref, bindings: TSUBindings] RETURNS [result: Polynomial.Ref] ~ BEGIN bindingList: TSUBindings Ź bindings; intermediate: Ref Ź a; UNTIL bindingList = NIL DO intermediate Ź Substitute[ intermediate, bindingList.first.variable, RefFromUnivariate[bindingList.first.replacement, $t] ]; bindingList Ź bindingList.rest; ENDLOOP; result Ź UnivariateFromRef[intermediate, $t ! Error => IF reason=NotUnivariate THEN GOTO UVError]; EXITS UVError => ERROR Error[UnsubstitutedVariables]; END; <<>> <> AddRefsWithoutCompaction: PROC [a, b: Ref] RETURNS [result: Ref] ~ BEGIN result Ź NEW[MultiPolRec[a.length + b.length]]; FOR i: NAT IN [0..a.length) DO result[i] Ź a[i]; ENDLOOP; FOR i: NAT IN [0..b.length) DO result[i+a.length] Ź b[i]; ENDLOOP; END; Compact: PROC [a: Ref] RETURNS [result: Ref] ~ BEGIN <> <<>> intermediate: Ref Ź NEW[MultiPolRec[a.length]]; monomialsCopied: NAT Ź 0; finalIndex: NAT; <> FOR i: NAT IN [0..a.length) DO thisMonomial: Monomial Ź a[i]; copied: BOOLEAN Ź FALSE; <> FOR j: NAT IN [0..monomialsCopied) DO IF Equivalent[thisMonomial.vars, intermediate[j].vars] THEN BEGIN intermediate[j].coefficient Ź intermediate[j].coefficient + thisMonomial.coefficient; copied Ź TRUE; END; ENDLOOP; <> IF copied = FALSE AND thisMonomial.coefficient # 0 THEN BEGIN intermediate[monomialsCopied] Ź thisMonomial; monomialsCopied Ź monomialsCopied + 1; END; ENDLOOP; <> finalIndex Ź 0; FOR i: NAT IN [0..monomialsCopied) DO IF intermediate[i].coefficient # 0 THEN BEGIN intermediate[finalIndex] Ź intermediate[i]; finalIndex Ź finalIndex + 1; END; ENDLOOP; <> result Ź NEW[MultiPolRec[finalIndex]]; FOR i: NAT IN [0..finalIndex) DO result[i] Ź intermediate[i] ENDLOOP; END; CopyMonomial: PROC [m: Monomial] RETURNS [result: Monomial] ~ BEGIN newVars: REF PoweredVariableSequence Ź NEW[PoweredVariableSequence[m.vars.numVars]]; FOR i: NAT IN [0..m.vars.numVars) DO newVars[i] Ź [variable: m.vars[i].variable, degree: m.vars[i].degree]; ENDLOOP; result Ź [coefficient: m.coefficient, vars: newVars]; END; DifferentiateMonomial: PROC [m: Monomial, variable: ATOM] RETURNS [result: Monomial] ~ BEGIN newCoefficient: REAL; newVars: REF PoweredVariableSequence; <> variablePresent: BOOL Ź FALSE; variablePosition: NAT; FOR j: NAT IN [0..m.vars.numVars) DO IF m.vars[j].variable = variable THEN BEGIN variablePresent Ź TRUE; variablePosition Ź j; END; ENDLOOP; <> IF variablePresent THEN BEGIN degree: NAT Ź m.vars[variablePosition].degree; newCoefficient Ź m.coefficient * degree; newVars Ź NEW[PoweredVariableSequence[m.vars.numVars]]; FOR j: NAT IN [0..m.vars.numVars) DO newVars[j] Ź m.vars[j]; ENDLOOP; newVars[variablePosition].degree Ź degree - 1; -- if this is zero, it should be eliminated. END <> ELSE BEGIN newCoefficient Ź 0; newVars Ź NEW[PoweredVariableSequence[0]]; END; <> result Ź [coefficient: newCoefficient, vars: newVars]; END; Equivalent: PROC [p, q: REF PoweredVariableSequence] RETURNS [result: BOOLEAN] ~ BEGIN <> <<>> IF p.numVars # q.numVars THEN {result Ź FALSE; RETURN}; FOR i: NAT IN [0..p.numVars) DO IF (p[i].variable # q[i].variable) OR (p[i].degree # q[i].degree) THEN BEGIN result Ź FALSE; RETURN; END; ENDLOOP; result Ź TRUE; END; FixUpMonomial: PROC [m: Monomial] RETURNS [result: Monomial] ~ BEGIN <> <<>> <> <<>> <> intermediate: REF PoweredVariableSequence Ź NEW[PoweredVariableSequence[m.vars.numVars]]; lastVariableCopied: Rope.ROPE Ź ""; lastVariableToCopy: Rope.ROPE Ź ""; iIndex: NAT Ź 0; <

> FOR i: NAT IN [0..m.vars.numVars) DO thisVar: Rope.ROPE Ź Convert.RopeFromAtom[m.vars[i].variable, FALSE]; IF Rope.Compare[thisVar, lastVariableToCopy] = greater THEN lastVariableToCopy Ź thisVar; ENDLOOP; <> UNTIL Rope.Compare[lastVariableCopied, lastVariableToCopy] = equal DO <> varToCopy: ATOM; variableToCopy: Rope.ROPE Ź lastVariableToCopy; exponent: NAT Ź 0; <

> FOR i: NAT IN [0..m.vars.numVars) DO thisVar: Rope.ROPE Ź Convert.RopeFromAtom[m.vars[i].variable, FALSE]; IF Rope.Compare[lastVariableCopied, thisVar] = less AND Rope.Compare[thisVar, variableToCopy] = less THEN BEGIN variableToCopy Ź thisVar; END; ENDLOOP; varToCopy Ź Convert.AtomFromRope[variableToCopy]; <> FOR i: NAT IN [0..m.vars.numVars) DO thisVar: Rope.ROPE Ź Convert.RopeFromAtom[m.vars[i].variable, FALSE]; IF Rope.Compare[thisVar, variableToCopy] = equal THEN exponent Ź exponent + m.vars[i].degree; ENDLOOP; <> SELECT exponent FROM <0 => ERROR Error[InternalError]; =0 => NULL; >0 => { intermediate[iIndex] Ź [variable: varToCopy, degree: exponent]; iIndex Ź iIndex + 1}; ENDCASE; <> lastVariableCopied Ź variableToCopy; ENDLOOP; <> result Ź [ coefficient: m.coefficient, vars: NEW[PoweredVariableSequence[iIndex]]]; FOR i: NAT IN [0..iIndex) DO result.vars[i] Ź intermediate[i]; ENDLOOP; END; LegalVariableName: PROC [name: ATOM] RETURNS [legal: BOOLEAN] ~ BEGIN <> <<>> RETURN[Rope.Length[Convert.RopeFromAtom[name, FALSE]] = 1]; END; MonomialDegree: PROC [m: Monomial] RETURNS [degree: NAT] ~ BEGIN d: NAT Ź 0; FOR i: NAT IN [0..m.vars.numVars) DO d Ź d + m.vars[i].degree; ENDLOOP; degree Ź d; END; MultiplyMonomials: PROC [m, n: Monomial] RETURNS [result: Monomial] ~ BEGIN <> <<>> Selection: TYPE ~ {fromM, fromN, fromBoth}; intermediate: REF PoweredVariableSequence Ź NEW[PoweredVariableSequence[m.vars.numVars + n.vars.numVars]]; resultTerm: REF PoweredVariableSequence; iIndex: NAT Ź 0; mIndex: NAT Ź 0; nIndex: NAT Ź 0; IF m.coefficient = 0 OR n.coefficient = 0 THEN BEGIN resultTerm Ź NEW[PoweredVariableSequence[0]]; result Ź [coefficient: 0, vars: resultTerm]; RETURN; END; <> UNTIL (mIndex >= m.vars.numVars) AND (nIndex >= n.vars.numVars) DO selection: Selection; <> IF mIndex >= m.vars.numVars THEN selection Ź fromN ELSE IF nIndex >= n.vars.numVars THEN selection Ź fromM ELSE BEGIN nextMvariable: Rope.ROPE Ź Convert.RopeFromAtom[m.vars[mIndex].variable]; nextNvariable: Rope.ROPE Ź Convert.RopeFromAtom[n.vars[nIndex].variable]; SELECT Rope.Compare[nextMvariable, nextNvariable] FROM less => selection Ź fromM; equal => selection Ź fromBoth; greater => selection Ź fromN; ENDCASE; END; SELECT selection FROM fromM => BEGIN intermediate[iIndex] Ź m.vars[mIndex]; mIndex Ź mIndex + 1; END; fromN => BEGIN intermediate[iIndex] Ź n.vars[nIndex]; nIndex Ź nIndex + 1; END; fromBoth => BEGIN intermediate[iIndex].variable Ź m.vars[mIndex].variable; intermediate[iIndex].degree Ź m.vars[mIndex].degree + n.vars[nIndex].degree; mIndex Ź mIndex + 1; nIndex Ź nIndex + 1; END; ENDCASE; iIndex Ź iIndex + 1; ENDLOOP; <> resultTerm Ź NEW[PoweredVariableSequence[iIndex]]; FOR i: NAT IN [0..iIndex) DO resultTerm[i] Ź intermediate[i]; ENDLOOP; result Ź [coefficient: m.coefficient * n.coefficient, vars: resultTerm]; END; MultiplyMonomialByRef: PROC [m: Monomial, a: Ref] RETURNS [result: Ref] ~ BEGIN <> IF m.coefficient = 0 OR a.length = 0 THEN BEGIN result Ź NEW[MultiPolRec[0]]; RETURN; END; <> result Ź NEW[MultiPolRec[a.length]]; FOR i: NAT IN [0..a.length) DO result[i] Ź MultiplyMonomials[m, a[i]]; ENDLOOP; END; MultiplyRefsWithoutCompaction: PROC [a, b: Ref] RETURNS [result: Ref] ~ BEGIN <> intermediate: Ref Ź NEW[MultiPolRec[0]]; FOR i: NAT IN [0..a.length) DO distributedProduct: Ref Ź MultiplyMonomialByRef[a[i], b]; intermediate Ź AddRefsWithoutCompaction[intermediate, distributedProduct]; ENDLOOP; result Ź intermediate; END; PolynomialCoefficient: PROC [poly: Polynomial.Ref, degree: NAT] RETURNS [coeff: REAL] ~ BEGIN <> coeff Ź poly[degree]; END; VariablePositionInMonomial: PROC [m: Monomial, var: ATOM] RETURNS [variablePresent: BOOLEAN, variablePosition: NAT] ~ BEGIN j: NAT Ź 0; variablePresent Ź FALSE; UNTIL variablePresent OR j = m.vars.numVars DO IF m.vars[j].variable = var THEN { variablePresent Ź TRUE; variablePosition Ź j}; j Ź j + 1; ENDLOOP; END; IntegerPower: PROC [base: REAL, exponent: INTEGER] RETURNS [result: REAL] ~ BEGIN SELECT exponent FROM 0 => result Ź 1; 1 => result Ź base; 2 => result Ź base*base; 3 => result Ź base*base*base; 4 => {foo: REAL Ź base*base; result Ź foo*foo}; 5 => {foo: REAL Ź base*base; result Ź foo*foo*base}; 6 => {foo: REAL Ź base*base; result Ź foo*foo*foo}; >6 => {foo: REAL Ź base*base; result Ź foo*foo*foo*IntegerPower[base, exponent-6]}; ENDCASE; END; END.