<> <> <<>> DIRECTORY <> <> 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] ~ { <> 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]~ { <> 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]~ { <> <> 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]~ { <> 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] ~ { <> 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] ~ { <> 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] ]; }; <> <> <<>> <> <> <> <> <> <> <> <<[in: in, out: out] _ ViewerIO.CreateViewerStreams[title:"Your favorite title"];>> <<[]_ in.SkipWhitespace[];>> <<[bigCARDRope, charsSkipped] _ in.GetTokenRope[ ];>> <> <<[]_ in.SkipWhitespace[];>> <> <> <> <<};>> <<[ ] _ in.GetChar[ ]; -- toss /;>> <<[]_ in.SkipWhitespace[];>> <<[bigCARDRope, charsSkipped] _ in.GetTokenRope[ ];>> <> <> <<};>> <<>> RatNumToRatRope: PUBLIC PROC [in: RatNum, reuse: BOOLEAN _ FALSE, showDenomOne: BOOL _ FALSE] RETURNS [Rope.ROPE] ~ { <> 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] ~ { <> 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] ]; }; }; <<>> <> <> <> <<};>> RatNumToREAL: PUBLIC PROC [in: RatNum, reuse: BOOLEAN _ FALSE] RETURNS [out: REAL] ~ { <> 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] ~ { <> RETURN [in.sign = POSITIVE] }; RatNumZero: PUBLIC PROC [in: RatNum] RETURNS [BOOLEAN] ~ { <> RETURN [in.sign = ZERO] }; RatNumNegative: PUBLIC PROC [in: RatNum] RETURNS [BOOLEAN] ~ { <> RETURN [in.sign = NEGATIVE] }; RatNumInteger: PUBLIC PROC [in: RatNum] RETURNS [BOOLEAN] ~ { <> RETURN[ BigOne[in.denominator] ]; }; <<***** Miscellaneous BigCardinal routines *****>> <<>> BigPowerOfTen: PUBLIC PROC [exponent: CARDINAL] RETURNS [power: BC.BigCARD] ~ { <> 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] ~ { <> IF in.size = 1 THEN RETURN[BC.BigToSmall[in] = 1] ELSE RETURN[FALSE] }; END.