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] ~ {
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: BOOLEAN ← FALSE] 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:
BOOLEAN ←
FALSE, showDenomOne:
BOOL ←
FALSE]
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.ROPE ← NIL;
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[] ];
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:
BOOLEAN ←
FALSE]
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:
BOOL ←
TRUE] ~ {
numerator, denominator:
BC.BigCARD;
bigCARDRope: Rope.ROPE;
charsSkipped: INT;
sign: INTEGER[-1..1] ← +1;
[]← in.SkipWhitespace[];
IF in.PeekChar[ ]='-
THEN {
sign ← -1;
[ ] ← in.GetChar[ ];
}
ELSE
IF in.PeekChar[ ]='+
THEN {
sign ← +1;
[ ] ← in.GetChar[ ];
};
[bigCARDRope, charsSkipped] ← in.GetTokenRope[];
numerator ← BC.BigFromDecimalRope[bigCARDRope];
[]← in.SkipWhitespace[];
IF in.PeekChar[ ]#'/
THEN
-- Missing / in RatNum
RETURN[ MakeRatNumZero[], FALSE ];
[ ] ← in.GetChar[ ]; -- toss /;
[]← in.SkipWhitespace[];
[bigCARDRope, charsSkipped] ← in.GetTokenRope[];
denominator ← BC.BigFromDecimalRope[bigCARDRope];
IF BC.BigZero[numerator] THEN out ← MakeRatNumZero[] ELSE out ← RatNumFromBigCards[sign, 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:
BOOLEAN ←
FALSE]
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.