RatNumsImpl.mesa
Last Edited by: Arnon, July 19, 1985 2:54:46 pm PDT
DIRECTORY
Convert USING [CardFromRope, RopeFromCard],
Convert USING [RopeFromReal],
Rope USING [Cat, ROPE, Find, Substr, Length],
IO USING [GetTokenRope, GetChar, PeekChar, SkipWhitespace, STREAM],
Real USING [NumberType, RealToPair],
BigCardinals,
RatNums;
RatNumsImpl: CEDAR PROGRAM
IMPORTS Real, Rope, IO, BigCardinals -- need to add Convert, Rope
EXPORTS RatNums =
BEGIN OPEN RatNums, BC: BigCardinals;
RatNumFail: PUBLIC ERROR [subclass: ATOM ← $Unspecified] = CODE;
***** Basic Arithmetic *****
RatNumAdd: PUBLIC PROC [in1, in2: RatNum] RETURNS [out: RatNum] ~ {
Adapted from SAC-2 RNSUM
prod1, prod2, denomGCD, cofactor1, cofactor2, dummy, sum, nextGCD, quot: BC.BigCARD;
IF RatNumZero[in1] THEN RETURN[ in2 ]; -- in1 zero
IF RatNumZero[in2] THEN RETURN[ in1 ]; -- in2 zero
IF RatNumInteger[in1] AND RatNumInteger[in2] THEN { -- both args integers
IF in1.sign # in2.sign THEN {
relation: BC.BigRelation ← BC.BigCompare[in1.numerator, in2.numerator];
IF relation = bigGreater THEN {
out.numerator ← BC.BigSubtract[ in1.numerator, in2.numerator];
out.sign ← in1.sign
}
ELSE {
out.numerator ← BC.BigSubtract[ in2.numerator, in1.numerator];
out.sign ← in2.sign
}
}
ELSE {
out.numerator ← BC.BigAdd[ in1.numerator, in2.numerator ];
out.sign ← in1.sign
};
out.denominator ← BC.BigFromSmall[1];
IF BC.BigZero[ out.numerator] THEN out.sign ← ZERO;
RETURN
};
IF RatNumInteger[in1] THEN {
prod1 ← BC.BigMultiply[ in1.numerator, in2.denominator ];
IF in1.sign # in2.sign THEN {
relation: BC.BigRelation ← BC.BigCompare[prod1, in2.numerator];
IF relation = bigGreater THEN {
out.numerator ← BC.BigSubtract[ prod1, in2.numerator];
out.sign ← in1.sign
}
ELSE {
out.numerator ← BC.BigSubtract[ in2.numerator, prod1];
out.sign ← in2.sign
}
}
ELSE {
out.numerator ← BC.BigAdd[ prod1, in2.numerator ];
out.sign ← in1.sign
};
out.denominator ← in2.denominator;
RETURN
};
IF RatNumInteger[in2] THEN {
prod2 ← BC.BigMultiply[ in2.numerator, in1.denominator ];
IF in2.sign # in1.sign THEN {
relation: BC.BigRelation ← BC.BigCompare[prod2, in1.numerator];
IF relation = bigGreater THEN {
out.numerator ← BC.BigSubtract[ prod2, in1.numerator];
out.sign ← in2.sign
}
ELSE {
out.numerator ← BC.BigSubtract[ in1.numerator, prod2];
out.sign ← in1.sign
}
}
ELSE {
out.numerator ← BC.BigAdd[ prod2, in1.numerator ];
out.sign ← in2.sign
};
out.denominator ← in1.denominator;
RETURN
};
denomGCD ← BC.BigGCD[ in1.denominator, in2.denominator ]; -- general case
[cofactor1, dummy] ← BC.BigDivMod[ in1.denominator, denomGCD];
[cofactor2, dummy] ← BC.BigDivMod[ in2.denominator, denomGCD];
prod1 ← BC.BigMultiply[ in1.numerator, cofactor2 ];
prod2 ← BC.BigMultiply[ in2.numerator, cofactor1 ];
IF in1.sign # in2.sign THEN {
relation: BC.BigRelation ← BC.BigCompare[prod1, prod2];
IF relation = bigGreater THEN {
sum ← BC.BigSubtract[ prod1, prod2];
out.sign ← in1.sign
}
ELSE {
sum ← BC.BigSubtract[ prod2, prod1];
out.sign ← in2.sign
}
}
ELSE {
sum ← BC.BigAdd[ prod1, prod2 ];
out.sign ← in1.sign
};
IF BC.BigZero[sum] THEN {
out.sign ← ZERO;
out.numerator ← sum;
out.denominator ← BC.BigFromSmall[1];
};
quot ← in1.denominator; -- need quot to avoid changing in1.denominator
IF NOT BigOne[denomGCD] THEN {
nextGCD ← BC.BigGCD[ sum, denomGCD ];
IF NOT BigOne[nextGCD] THEN {
[sum, dummy] ← BC.BigDivMod[ sum, nextGCD];
[quot, dummy] ← BC.BigDivMod[ quot, nextGCD]
}
};
out.numerator ← sum;
out.denominator ← BC.BigMultiply[ quot, cofactor2 ];
RETURN
};
RatNumNegate: PUBLIC PROC [in: RatNum] RETURNS [out: RatNum] ~ {
IF in.sign = NEGATIVE THEN out.sign ← POSITIVE ELSE
IF in.sign = POSITIVE THEN out.sign ← NEGATIVE ELSE out.sign ← ZERO;
out.numerator ← BC.BigCopy[in.numerator];
out.denominator ← BC.BigCopy[in.denominator];
};
RatNumABS: PUBLIC PROC [in: RatNum] RETURNS [out: RatNum] ~ {
out.sign ← in.sign;
IF in.sign = NEGATIVE THEN out.sign ← POSITIVE;
out.numerator ← BC.BigCopy[in.numerator];
out.denominator ← BC.BigCopy[in.denominator];
};
RatNumSubtract: PUBLIC PROC [in1, in2: RatNum] RETURNS [RatNum] ~ {
RETURN[ RatNumAdd[ in1, RatNumNegate[ in2 ] ] ];
};
RatNumMultiply: PUBLIC PROC [in1, in2: RatNum] RETURNS [out: RatNum]~ {
Adapted from SAC-2 RNPROD
firstGCD, cofactor1, cofactor2, dummy, secondGCD, cofactor3, cofactor4: BC.BigCARD;
IF RatNumZero[in1] OR RatNumZero[in2] THEN RETURN[ MakeRatNumZero[] ];
IF RatNumInteger[in1] AND RatNumInteger[in2] THEN { -- both args integers
out.numerator ← BC.BigMultiply[ in1.numerator, in2.numerator ];
out.denominator ← BC.BigFromSmall[1];
IF in1.sign # in2.sign THEN out.sign ← NEGATIVE ELSE out.sign ← POSITIVE;
RETURN;
};
IF RatNumInteger[in1] THEN {
firstGCD ← BC.BigGCD[ in1.numerator, in2.denominator ];
[cofactor1, dummy] ← BC.BigDivMod[ in1.numerator, firstGCD];
[cofactor2, dummy] ← BC.BigDivMod[ in2.denominator, firstGCD];
out.numerator ← BC.BigMultiply[ cofactor1, in2.numerator ];
out.denominator ← cofactor2;
IF in1.sign # in2.sign THEN out.sign ← NEGATIVE ELSE out.sign ← POSITIVE;
RETURN;
};
IF RatNumInteger[in2] THEN {
firstGCD ← BC.BigGCD[ in2.numerator, in1.denominator ];
[cofactor1, dummy] ← BC.BigDivMod[ in2.numerator, firstGCD];
[cofactor2, dummy] ← BC.BigDivMod[ in1.denominator, firstGCD];
out.numerator ← BC.BigMultiply[ cofactor1, in1.numerator ];
out.denominator ← cofactor2;
IF in1.sign # in2.sign THEN out.sign ← NEGATIVE ELSE out.sign ← POSITIVE;
RETURN;
};
firstGCD ← BC.BigGCD[ in1.numerator, in2.denominator ]; -- general case
[cofactor1, dummy] ← BC.BigDivMod[ in1.numerator, firstGCD];
[cofactor2, dummy] ← BC.BigDivMod[ in2.denominator, firstGCD];
secondGCD ← BC.BigGCD[ in2.numerator, in1.denominator ];
[cofactor3, dummy] ← BC.BigDivMod[ in2.numerator, secondGCD];
[cofactor4, dummy] ← BC.BigDivMod[ in1.denominator, secondGCD];
out.numerator ← BC.BigMultiply[ cofactor1, cofactor3 ];
out.denominator ← BC.BigMultiply[ cofactor2, cofactor4 ];
IF in1.sign # in2.sign THEN out.sign ← NEGATIVE ELSE out.sign ← POSITIVE;
};
RatNumInverse: PUBLIC PROC [in: RatNum] RETURNS [out: RatNum]~ {
Inverse of a non-zero RatNum.
Adapted from SAC-2 RNINV.
IF in.sign = ZERO THEN RatNumFail[$DivideByZero];
out.sign ← in.sign;
out.numerator ← BC.BigCopy[ in.denominator ];
out.denominator ← BC.BigCopy[ in.numerator ];
};
RatNumDivide: PUBLIC PROC [dividend, divisor: RatNum] RETURNS [RatNum]~ {
Adapted from SAC-2 RNQ
IF dividend.sign = ZERO THEN RETURN[ MakeRatNumZero[] ] ELSE
RETURN[ RatNumMultiply[ dividend, RatNumInverse[divisor] ] ];
};
***** Constructor Routines *****
RatNumFromBigCards: PUBLIC PROC [sign: INTEGER[-1..1], num, den: BC.BigCARD] RETURNS [out: RatNum] ~ {
gcd, dummy: BC.BigCARD;
SELECT sign FROM
-1 => out.sign ← NEGATIVE; 
0 => out.sign ← ZERO;
1 => out.sign ← POSITIVE;
ENDCASE;
IF BC.BigZero[ num ] THEN {
IF out.sign # ZERO THEN RatNumFail[$SignInconsistency];
out.numerator ← num;
out.denominator ← den
}
ELSE {
IF out.sign = ZERO THEN RatNumFail[$SignInconsistency];
gcd ← BC.BigGCD[ num, den ]; -- general case
[out.numerator, dummy] ← BC.BigDivMod[ num, gcd];
[out.denominator, dummy] ← BC.BigDivMod[ den, gcd]
}
};
RatNumFromSmallCards: PUBLIC PROC [sign: INTEGER[-1..1], num, den: CARDINAL] RETURNS [out: RatNum] ~ {
bignum, bigden, gcd, dummy: BC.BigCARD;
SELECT sign FROM
-1 => out.sign ← NEGATIVE; 
0 => out.sign ← ZERO;
1 => out.sign ← POSITIVE;
ENDCASE;
IF num = 0 THEN {
IF out.sign # ZERO THEN RatNumFail[$SignInconsistency];
RETURN [MakeRatNumZero[] ]
}
ELSE {
IF out.sign = ZERO THEN RatNumFail[$SignInconsistency];
bignum ← BC.BigFromSmall[num];
bigden ← BC.BigFromSmall[den];
gcd ← BC.BigGCD[ bignum, bigden ]; -- general case
[out.numerator, dummy] ← BC.BigDivMod[ bignum, gcd];
[out.denominator, dummy] ← BC.BigDivMod[ bigden, gcd]
}
};
MakeRatNumZero: PUBLIC PROC RETURNS [out: RatNum] ~ {
Construct RatNum representation for zero
out.sign ← ZERO;
out.numerator ← BC.BigFromSmall[0];
out.denominator ← BC.BigFromSmall[1];
};
***** Conversion and I/O Routines *****
RatNumFromREALRope: PUBLIC PROC [in: Rope.ROPE] RETURNS [out: RatNum] ~ {
Intended to allow decimal notation input of RatNums.
dotPos: INT = in.Find["."]; -- decimal point assumed always present
minusPos: INT = in.Find["-"];
integer, fraction: BC.BigCARD;
fractionLength: CARDINAL;
sign: INTEGER;
numerator, denominator: BC.BigCARD;
IF minusPos # -1 THEN sign ← -1 ELSE sign ← 1;
integer ← BC.BigFromDecimalRope[ in.Substr[minusPos+1, dotPos] ];
IF BC.BigZero[integer] THEN sign ← 0;
fraction ← BC.BigFromDecimalRope[ in.Substr[dotPos + 1, in.Length[ ] ] ];
fractionLength ← in.Length[ ] - dotPos - 1;
denominator ← BigPowerOfTen[ fractionLength ];
numerator ← BC.BigAdd[ BC.BigMultiply[ integer, denominator ], fraction ];
RETURN[ RatNumFromBigCards[ sign, numerator, denominator] ];
};
RatNumToREALRope: PUBLIC PROC [in: RatNum, reuse: BOOLEANFALSE] RETURNS [Rope.ROPE] ~ {
Intended to provide a more accurate, and arbitrary magnitude, decimal approximation to a RatNum, than just applying RatNumToREAL and displaying the resulting REAL.
RatNumFromRatRope: PUBLIC PROC [in: Rope.ROPE] RETURNS [number: RatNum] ~ {
Intended to scan a sequence of tokens constituting a rational number, and convert them to a RatNum.
The following is an approximation (actually this should be modified to get sign, numerator and denominator as BigCARDs, then call RatNumFromBigCards to make the RatNum, in particular so that gcd(numerator and denominator) removed):
numerator, denominator: BC.BigCARD;
in, out: IO.STREAM;
bigCARDRope: ROPE;
charsSkipped: INT;
[in: in, out: out] ← ViewerIO.CreateViewerStreams[title:"Your favorite title"];
[]← in.SkipWhitespace[];
[bigCARDRope, charsSkipped] ← in.GetTokenRope[ ];
numerator ← BC.BigFromDecimalRope[bigCARDRope];
[]← in.SkipWhitespace[];
IF in.PeekChar[ ]#'/ THEN { -- Missing / in RatNum
out.PutF["\nMissing / in RatNum. Please retype the expression.\n\n"];
in.Reset[ ];
};
[ ] ← in.GetChar[ ]; -- toss /;
[]← in.SkipWhitespace[];
[bigCARDRope, charsSkipped] ← in.GetTokenRope[ ];
denominator ← BC.BigFromDecimalRope[bigCARDRope];
number← RatNumFromBigCards[+1, numerator, denominator ];
};
RatNumToRatRope: PUBLIC PROC [in: RatNum, reuse: BOOLEANFALSE, showDenomOne: BOOLFALSE] RETURNS [Rope.ROPE] ~ {
Used for displaying the values of RatNums. If in is positive, then the output Rope is unsigned. The default of reuse: FALSE preserves the input RatNum.If in is an integer, then if showDenomOne = FALSE the denominator of one is not printed, if TRUE then it is.
out: Rope.ROPENIL;
IF in.sign = ZERO THEN {IF NOT showDenomOne THEN RETURN["0"] ELSE RETURN["0 / 1"]}
ELSE {
IF in.sign = NEGATIVE THEN out ← out.Cat["-"];
out ← out.Cat[ BC.BigToDecimalRope[ in.numerator ] ];
IF NOT RatNumInteger[in] OR showDenomOne THEN {
out ← out.Cat[ " / " ];
out ← out.Cat[ BC.BigToDecimalRope[ in.denominator ] ];
};
RETURN[ out ];
}
};
RatNumFromREAL: PUBLIC PROC [in: REAL] RETURNS [out:RatNum] ~ {
Convert a REAL to a RatNum. The REAL is viewed as a decimal fraction, whose numerator and denominator become the numerator and denominator of the resulting RatNum.
separator: INT = 10000;
expsep: CARDINAL = 5;
exp, z: INT;
lowz, midz, highz: CARDINAL;
numerator, denominator: BC. BigCARD;
sign: INTEGER;
ty: Real.NumberType;
precision: CARDINAL ← 10;
[type: ty, fr: z, exp10: exp] ← Real.RealToPair[in, precision];
SELECT ty FROM
nan => RatNumFail[$RatNumFromREALnan];
infinity => RatNumFail[$RatNumFromREALinfinity];
zero => RETURN[ MakeRatNumZero[] ];
ENDCASE =>
{
IF z < 0 THEN {
z ← - z;
sign ← -1
}
ELSE sign ← 1;
lowz ← z - (z / separator) * separator;
z ← z / separator;
midz ← z - (z / separator) * separator;
highz ← z / separator;
numerator ← BC.BigFromSmall[ highz ];
numerator ← BC.BigMultiply[ numerator, BigPowerOfTen[expsep -1 ] ];
numerator ← BC.BigAdd[ numerator, BC.BigFromSmall[ midz ] ];
numerator ← BC.BigMultiply[ numerator, BigPowerOfTen[expsep -1 ] ];
numerator ← BC.BigAdd[ numerator, BC.BigFromSmall[ lowz ] ];
IF exp < 0 THEN denominator ← BigPowerOfTen[ - exp]
ELSE {
denominator ← BC.BigFromSmall[1];
numerator ← BC.BigMultiply[ numerator, BigPowerOfTen[exp] ]
};
RETURN[ RatNumFromBigCards[sign, numerator, denominator] ];
};
};
RatNumFromREAL: PUBLIC PROC [in: REAL] RETURNS [out:RatNum] ~ {
Convert a REAL to a RatNum.
RETURN[ RatNumFromREALRope[ Convert.RopeFromReal[ from: in, useE: FALSE ] ] ];
};
RatNumToREAL: PUBLIC PROC [in: RatNum, reuse: BOOLEANFALSE] RETURNS [out: REAL] ~ {
Convert a RatNum to a real. For the time being, it is assumed that the RatNum is not so large in absolute value as to cause floating point overflow.
IF RatNumZero[in] THEN RETURN[0.0];
out ← BigToREAL[in.numerator];
IF NOT BigOne[in.denominator] THEN out ← out / BigToREAL[in.denominator];
IF in.sign = NEGATIVE THEN out ← - out;
};
ReadRatNum: PUBLIC PROC [in: IO.STREAM] RETURNS [out: RatNum, ok: BOOLTRUE] ~ {
reads an UNSIGNED RatNum (somebody else presumed to read and handle sign)
numerator, denominator: BC.BigCARD;
bigCARDRope: Rope.ROPE;
charsSkipped: INT; -- dummy output parm for GetTokenRope
[]← in.SkipWhitespace[];
[bigCARDRope, charsSkipped] ← in.GetTokenRope[];
numerator ← BC.BigFromDecimalRope[bigCARDRope];
[]← in.SkipWhitespace[];
IF in.PeekChar[ ]#'/ THEN -- No / in RatNum
IF BC.BigZero[numerator] THEN out ← MakeRatNumZero[] ELSE out ← RatNumFromBigCards[+1, numerator, BC.BigFromSmall[1] ]
ELSE {
[ ] ← in.GetChar[ ]; -- toss /;
[]← in.SkipWhitespace[];
[bigCARDRope, charsSkipped] ← in.GetTokenRope[];
denominator ← BC.BigFromDecimalRope[bigCARDRope];
IF BC.BigZero[numerator] THEN out ← MakeRatNumZero[] ELSE out ← RatNumFromBigCards[+1, numerator, denominator ];
};
RETURN[ out, ok ];
};
***** Comparison *****
RatNumCompare: PUBLIC PROC [in1, in2: RatNum] RETURNS [RatNumRelation] ~ {
diff: RatNum ← RatNumSubtract[in1, in2];
SELECT diff.sign FROM
NEGATIVE => RETURN[ ratLess ]; 
ZERO => RETURN[ ratEqual ];
ENDCASE;
RETURN[ ratGreater ];
};
RatNumRelationToRope: PUBLIC PROC [inRelation: RatNumRelation] RETURNS[Rope.ROPE] ~ {
SELECT inRelation FROM
ratLess => RETURN[ "Less" ]; 
ratEqual => RETURN[ "Equal" ];
ENDCASE;
RETURN[ "Greater"];
};
RatNumGreater: PUBLIC PROC [in1, in2: RatNum] RETURNS [BOOLEAN] ~ {
IF RatNumSubtract[in1, in2].sign = POSITIVE THEN RETURN[ TRUE ] ELSE RETURN[ FALSE ]
};
RatNumEqual: PUBLIC PROC [in1, in2: RatNum] RETURNS [BOOLEAN] ~ {
IF RatNumSubtract[in1, in2].sign = ZERO THEN RETURN[ TRUE ] ELSE RETURN[ FALSE ]
};
RatNumLess: PUBLIC PROC [in1, in2: RatNum] RETURNS [BOOLEAN] ~ {
IF RatNumSubtract[in1, in2].sign = NEGATIVE THEN RETURN[ TRUE ] ELSE RETURN[ FALSE ]
};
RatNumPositive: PUBLIC PROC [in: RatNum] RETURNS [BOOLEAN] ~ {
Test if a RatNum is zero
RETURN [in.sign = POSITIVE]
};
RatNumZero: PUBLIC PROC [in: RatNum] RETURNS [BOOLEAN] ~ {
Test if a RatNum is zero
RETURN [in.sign = ZERO]
};
RatNumNegative: PUBLIC PROC [in: RatNum] RETURNS [BOOLEAN] ~ {
Test if a RatNum is zero
RETURN [in.sign = NEGATIVE]
};
RatNumInteger: PUBLIC PROC [in: RatNum] RETURNS [BOOLEAN] ~ {
Test if a RatNum is an integer
RETURN[ BigOne[in.denominator] ];
};
***** Miscellaneous BigCardinal routines *****
BigPowerOfTen: PUBLIC PROC [exponent: CARDINAL] RETURNS [power: BC.BigCARD] ~ {
exponent assumed nonnegative, else coerced to abs value.
base:BC.BigCARD ← BC.BigFromSmall[10];
power ← BC.BigFromSmall[1];
IF exponent = 0 THEN RETURN;
--Exponentiation by repeated squaring.
WHILE exponent > 1 DO
IF exponent MOD 2 = 1 THEN
power ← BC.BigMultiply[power, base];
exponent ← exponent / 2;
base ← BC.BigMultiply[base, base];
ENDLOOP;
power ← BC.BigMultiply[power, base];
};
BigToREAL: PUBLIC PROC [in: BC.BigCARD, reuse: BOOLEANFALSE] RETURNS [out: REAL] ~ {
outChunk: REAL;
out ← 0.0;
IF BC.BigZero[in] THEN RETURN;
IF NOT reuse THEN in ← BC.BigCopy[in];
FOR index: CARDINAL DECREASING IN [0..in.size) DO
outChunk ← in.contents[index]; -- convert CARDINAL to REAL
out ← out * 65536.0 + outChunk;
ENDLOOP;
};
BigOne: PUBLIC PROC [in: BC.BigCARD] RETURNS [BOOLEAN] ~ {
Test if a BigCARD is the integer one.
IF in.size = 1 THEN RETURN[BC.BigToSmall[in] = 1] ELSE RETURN[FALSE]
};
END.