<> <> <<>> DIRECTORY Rope, Ieee, PrincOpsUtils, Process, RuntimeError, IO, Basics, Atom, Real, BigCardinals, AlgebraClasses, Points, BigCardExtras, BigRats; BigRatsImpl: CEDAR PROGRAM IMPORTS Rope, Basics, Ieee, IO, PrincOpsUtils, Process, RuntimeError, BigCardinals, BigCardExtras EXPORTS BigRats = BEGIN OPEN BigRats, BC: BigCardinals, AC: AlgebraClasses, PTS: Points, BCE: BigCardExtras; <> BigRatsError: PUBLIC SIGNAL [reason: ATOM _ $Unspecified] = CODE; bitsPerWord: CARDINAL = Basics.bitsPerWord; CARD: TYPE = LONG CARDINAL; ROPE: TYPE = Rope.ROPE; STREAM: TYPE = IO.STREAM; <> BigCardZero: BigCard = BigCardinals.BigFromSmall[0]; BigCardOne: BigCard = BigCardinals.BigFromSmall[1]; BigCardTwo: BigCard = BigCardinals.BigFromSmall[2]; BigCardTen: BigCard = BigCardinals.BigFromSmall[10]; RatZero: BigRat = NEW[BigRatRep _ [sign: equal, num: BigCardZero, den: BigCardOne]]; RatOne: BigRat = NEW[BigRatRep _ [sign: greater, num: BigCardOne, den: BigCardOne]]; -- call to FromBC would be circular RatTwo: BigRat = FromBC[BigCardTwo]; RatHalf: BigRat = Breed[BigCardOne, BigCardTwo, FALSE]; <> ClassPrintName: AC.PrintNameProc = { RETURN["BigRats"]; }; ClassLegalFirstChar: AC.LegalFirstCharOp = { SELECT char FROM IN ['0..'9] => RETURN[TRUE]; ENDCASE; RETURN[FALSE]; }; ClassRead: AC.ReadOp = { RETURN[Read[in]]; }; ClassFromRope: AC.FromRopeOp = { stream: IO.STREAM _ IO.RIS[in]; RETURN[ ClassRead[stream] ]; }; ClassToRope: AC.ToRopeOp = { RETURN[ ToRope[NARROW[in, BigRat] ] ] }; ClassWrite: AC.WriteOp = { Write[stream, NARROW[in, BigRat] ] }; ClassZero: AC.NullaryOp = { RETURN[ RatZero ] }; ClassOne: AC.NullaryOp = { RETURN[ RatOne ] }; ClassCharacteristic: AC.StructureRankOp = { RETURN[ 0 ] }; ClassAdd: AC.BinaryOp = { RETURN[ Add[NARROW[firstArg, BigRat], NARROW[secondArg, BigRat] ] ] }; ClassNegate: AC.UnaryOp = { RETURN[ Negate[ NARROW[arg, BigRat] ] ]; }; ClassSubtract: AC.BinaryOp = { RETURN[ Subtract[NARROW[firstArg, BigRat], NARROW[secondArg, BigRat] ] ] }; ClassMultiply: AC.BinaryOp = { RETURN[ Multiply[NARROW[firstArg, BigRat], NARROW[secondArg, BigRat] ] ] }; ClassEqual: AC.EqualityOp = { RETURN[ Compare[NARROW[firstArg, BigRat], NARROW[secondArg, BigRat] ] = equal] }; ClassSign: AC.CompareToZeroOp = { RETURN[ Sign[NARROW[arg, BigRat] ] ] }; ClassAbs: AC.UnaryOp = { RETURN[ Abs[NARROW[arg, BigRat] ] ] }; ClassCompare: AC.BinaryCompareOp = { RETURN[ Compare[NARROW[firstArg, BigRat], NARROW[secondArg, BigRat] ] ] }; ClassInvert: AC.UnaryOp = { RETURN[ Invert[NARROW[arg, BigRat] ] ] }; ClassDivide: AC.BinaryOp = { RETURN[ Divide[NARROW[firstArg, BigRat], NARROW[secondArg, BigRat] ] ] }; RationalClass: AC.StructureClass _ NEW[AC.StructureClassRec _ [ flavor: field, printName: ClassPrintName, characteristic: ClassCharacteristic, legalFirstChar: ClassLegalFirstChar, read: ClassRead, fromRope: ClassFromRope, toRope: ClassToRope, write: ClassWrite, add: ClassAdd, negate: ClassNegate, subtract: ClassSubtract, zero: ClassZero, multiply: ClassMultiply, commutative: TRUE, invert: ClassInvert, divide: ClassDivide, one: ClassOne, equal: ClassEqual, ordered: TRUE, sign: ClassSign, abs: ClassAbs, compare: ClassCompare, integralDomain: TRUE, completeField: FALSE, realField: TRUE, realClosedField: FALSE, algebraicallyClosedField: FALSE, propList: NIL ] ]; BigRats: PUBLIC AC.Structure _ NEW[AC.StructureRec _ [ class: RationalClass, instanceData: NIL ] ]; <> <> <> <> <> <> <> <> <<}>> <> <> <> <<[out.num, dummy] _ BC.BigDivMod[ num, gcd];>> <<[out.den, dummy] _ BC.BigDivMod[ den, gcd]>> <<}>> <<};>> <<>> <> <> <> <> <> <> <> <<}>> <> <> <> <> <> <<[out.num, dummy] _ BC.BigDivMod[ bignum, gcd];>> <<[out.den, dummy] _ BC.BigDivMod[ bigden, gcd]>> <<}>> <<};>> FromPairBC: PUBLIC PROC [num, den: BigCard, less: BOOL _ FALSE] RETURNS [BigRat] = { RETURN [Simplify[Breed[num, den, less]]]; }; FromPairLC: PUBLIC PROC [num, den: CARD, less: BOOL _ FALSE] RETURNS [BigRat] = { RETURN [Simplify[Breed[BCE.LCToBC[num], BCE.LCToBC[den], less]]]; }; FromBC: PUBLIC PROC [bc: BigCard, less: BOOL _ FALSE] RETURNS [BigRat] = { RETURN [Breed[bc, BigCardOne, less]]; }; FromLC: PUBLIC PROC [lc: CARD, less: BOOL _ FALSE] RETURNS [BigRat] = { IF Basics.HighHalf[lc] = 0 AND NOT less THEN SELECT Basics.LowHalf[lc] FROM 0 => RETURN [RatZero]; 1 => RETURN [RatOne]; ENDCASE; RETURN [Breed[BCE.LCToBC[lc], BigCardOne, less]]; }; <> Read: PUBLIC PROC [in: IO.STREAM] RETURNS [out: BigRat] ~ { <> num, den: BC.BigCARD; bigCARDRope: Rope.ROPE; charsSkipped: INT; -- dummy output parm for GetTokenRope sign: Basics.Comparison _ greater; []_ in.SkipWhitespace[]; IF in.PeekChar[ ]='- THEN { sign _ less; [ ] _ in.GetChar[ ]; } ELSE IF in.PeekChar[ ]='+ THEN { sign _ greater; [ ] _ in.GetChar[ ]; }; [bigCARDRope, charsSkipped] _ in.GetTokenRope[]; num _ BC.BigFromDecimalRope[bigCARDRope]; []_ in.SkipWhitespace[]; IF in.EndOf[] OR in.PeekChar[ ]#'/ THEN -- No / in BigRat IF BC.BigZero[num] THEN out _ RatZero ELSE out _ FromPairBC[num, BigCardOne, IF sign = less THEN TRUE ELSE FALSE ] ELSE { [ ] _ in.GetChar[ ]; -- toss /; []_ in.SkipWhitespace[]; [bigCARDRope, charsSkipped] _ in.GetTokenRope[]; den _ BC.BigFromDecimalRope[bigCARDRope]; IF BC.BigZero[num] THEN out _ RatZero ELSE out _ FromPairBC[ num, den, IF sign = less THEN TRUE ELSE FALSE ]; }; RETURN[out]; }; <> <> <> <> <<};>> <<>> FromRope: PUBLIC PROC [rope: ROPE] RETURNS [BigRat] = { less: BOOL _ Rope.Match["-*", rope]; pos: INT _ 0; len: INT _ 0; IF less THEN rope _ Rope.Substr[rope, 1]; len _ Rope.Length[rope]; pos _ Rope.SkipTo[rope, 0, "/"]; IF pos # len THEN { <> num: ROPE _ Rope.Substr[rope, 0, pos]; den: ROPE _ Rope.Substr[rope, pos+1]; RETURN [FromPairBC[ BigCardinals.BigFromDecimalRope[num], BigCardinals.BigFromDecimalRope[den], less]]; }; pos _ Rope.SkipTo[rope, 0, "."]; IF pos < len THEN { <> whole: ROPE _ Rope.Substr[rope, 0, pos]; fract: ROPE _ Rope.Substr[rope, pos+1]; fractPlaces: INT _ Rope.Length[fract]; number: BigCard _ BigCardinals.BigFromDecimalRope[Rope.Concat[whole, fract]]; tens: BigCard _ InternalBCPower[BigCardOne, BigCardTen, fractPlaces]; RETURN [FromPairBC[number, tens, less]]; }; <> RETURN [FromBC[BigCardinals.BigFromDecimalRope[rope]]]; }; <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <<};>> <<>> ToRope: PUBLIC PROC [rat: BigRat] RETURNS [out: ROPE] = { IF rat.sign = equal THEN RETURN ["0"]; IF rat.den.size = 1 AND rat.den.contents[0] = 1 THEN { RETURN [Rope.Cat[ IF rat.sign = less THEN "-" ELSE NIL, BigCardinals.BigToDecimalRope[rat.num] ]]; }; RETURN [Rope.Cat[ IF rat.sign = less THEN "-" ELSE NIL, BigCardinals.BigToDecimalRope[rat.num], "/", BigCardinals.BigToDecimalRope[rat.den] ]]; }; ToRopeApprox: PUBLIC PROC [rat: BigRat, places: NAT _ 3] RETURNS [ROPE] = { ros: STREAM = IO.ROS[]; left, right: BigCard; rat1000: BigRat _ FromLC[1000]; placesRat: BigRat _ BCToTheX[BigCardTen, places]; IF rat.sign = less THEN IO.PutChar[ros, '-]; [left, rat] _ Truncate[rat]; [right, rat] _ Truncate[Multiply[rat, placesRat]]; IF Compare[rat, RatHalf] # less THEN { right _ BigCardinals.BigAdd[right, BigCardinals.BigFromSmall[1]]; IF BigCardinals.BigCompare[right, placesRat.num] = bigEqual THEN { left _ BigCardinals.BigAdd[right, BigCardinals.BigFromSmall[1]]; right _ BigCardinals.BigFromSmall[0]; }; }; IO.PutRope[ros, BigCardinals.BigToDecimalRope[left]]; IF right.size # 0 THEN { rope: ROPE _ BigCardinals.BigToDecimalRope[right]; IO.PutChar[ros, '.]; THROUGH [Rope.Length[rope]..places) DO IO.PutChar[ros, '0]; ENDLOOP; IO.PutRope[ros, rope]; }; RETURN [IO.RopeFromROS[ros]]; }; BigRatToRatRope: PUBLIC PROC [in: BigRat, showDenomOne: BOOL _ FALSE, reuse: BOOLEAN _ FALSE] RETURNS [Rope.ROPE] ~ { <> out: Rope.ROPE _ NIL; IF in.sign = equal THEN {IF NOT showDenomOne THEN RETURN["0"] ELSE RETURN["0 / 1"]} ELSE { IF in.sign = less THEN out _ out.Cat["-"]; out _ out.Cat[ BC.BigToDecimalRope[ in.num ] ]; IF NOT Integer[in] OR showDenomOne THEN { out _ out.Cat[ " / " ]; out _ out.Cat[ BC.BigToDecimalRope[ in.den ] ]; }; RETURN[ out ]; } }; Write: PUBLIC PROC [stream: IO.STREAM, in: BigRat] = { IO.PutRope[ stream, BigRatToRatRope[in, FALSE, FALSE] ] }; <> <> <> <> <> <> <> <> <> <> <<[type: ty, fr: z, exp10: exp] _ Real.RealToPair[in, precision];>> <> < ERROR BigRatsError[$BigRatFromREALnan];>> < ERROR BigRatsError[$BigRatFromREALinfinity];>> < RETURN[ RatZero ];>> < {>> <> <> <> <<}>> <> <> <> <> <> <> <> <> <> <> <> <> <> <> <<};>> <> <<};>> <<};>> <<>> <> <> <> <> <> <> <<};>> <<>> FromReal: PUBLIC PROC [real: REAL] RETURNS [BigRat] = { ext: Ieee.Ext = Ieee.Unpack[real]; SELECT ext.det.type FROM normal => { expRat: BigRat _ TwoToTheX[ext.exp-31, real < 0.0]; mantRat: BigRat _ FromLC[ext.frac.lc]; RETURN [Multiply[expRat, mantRat]]; }; zero => RETURN [RatZero]; ENDCASE => ERROR; }; ToReal: PUBLIC PROC [rat: BigRat] RETURNS [REAL] = { SELECT TRUE FROM rat.sign = equal => RETURN [0.0]; rat = RatOne => RETURN [1.0]; ENDCASE => { numFirst: INT _ BCE.FirstOneBit[rat.num]; denFirst: INT _ BCE.FirstOneBit[rat.den]; exp: INTEGER _ numFirst-denFirst; scale: BigRat _ TwoToTheX[31 - exp]; adjusted: BigRat _ Multiply[rat, scale]; quo, rem: BigCard; [quo, rem] _ BigCardinals.BigDivMod[adjusted.num, adjusted.den, FALSE]; SELECT BigCardinals.BigCompare[BigCardinals.BigAdd[rem, rem], adjusted.den] FROM bigEqual, bigGreater => { quo _ BigCardinals.BigAdd[quo, BigCardOne]; IF quo.size = 3 THEN { <> quo _ BigCardinals.BigDivMod[quo, BigCardinals.BigFromSmall[2]].quo; exp _ exp + 1; }; }; ENDCASE; SELECT quo.size FROM 2 => TRUSTED { <> ln: Basics.LongNumber _ [pair[lo: quo.contents[0], hi: quo.contents[1] ]]; ext: Ieee.Ext _ [det: [sign: rat.sign = less, sticky: FALSE, blank: 0, type: normal], exp: exp, frac: ln]; WHILE ext.frac.li > 0 DO ext.frac _ Basics.DoubleShiftLeft[ext.frac, 1]; ext.exp _ ext.exp - 1; ENDLOOP; IF ext.exp < Ieee.DenormalizedExponent THEN { WHILE ext.exp < Ieee.DenormalizedExponent+1 DO ext.frac _ Basics.DoubleShiftRight[ext.frac, 1]; ext.exp _ ext.exp + 1; ENDLOOP; ext.exp _ ext.exp - 1; }; RETURN [Ieee.Pack[@ext]]; }; ENDCASE => ERROR; }; }; Truncate: PUBLIC PROC [rat: BigRat] RETURNS [fix: BigCard, rem: BigRat] = { SELECT BigCardinals.BigCompare[rat.num, rat.den] FROM bigLess => RETURN [BigCardZero, rat]; bigEqual => RETURN [BigCardOne, RatZero]; bigGreater => { mod: BigCard; [fix, mod] _ BigCardinals.BigDivMod[rat.num, rat.den]; rem _ FromPairBC[mod, rat.den]; }; ENDCASE => ERROR; }; <> Template: PROC [] RETURNS [BigRat] ~ { RETURN [NEW[BigRatRep _ [sign: equal, num: BC.Zero, den: BC.Zero]]]; }; Add: PUBLIC PROC [firstArg, secondArg: BigRat] RETURNS [result: BigRat] ~ { <> ratResult: BigRat _ Template[]; prod1, prod2, denomGCD, cofactor1, cofactor2, dummy, sum, nextGCD, quot: BC.BigCARD; IF firstArg.sign = equal THEN RETURN[secondArg]; -- firstArg equal IF secondArg.sign = equal THEN RETURN[firstArg]; -- secondArg equal IF Integer[firstArg] AND Integer[secondArg] THEN { -- both args integers IF firstArg.sign # secondArg.sign THEN { relation: BC.BigRelation _ BC.BigCompare[firstArg.num, secondArg.num]; IF relation = bigGreater THEN { ratResult.num _ BC.BigSubtract[ firstArg.num, secondArg.num]; ratResult.sign _ firstArg.sign } ELSE { ratResult.num _ BC.BigSubtract[ secondArg.num, firstArg.num]; ratResult.sign _ secondArg.sign } } ELSE { ratResult.num _ BC.BigAdd[ firstArg.num, secondArg.num ]; ratResult.sign _ firstArg.sign }; ratResult.den _ BC.BigFromSmall[1]; IF BC.BigZero[ ratResult.num] THEN ratResult.sign _ equal; RETURN[ratResult]; }; IF Integer[firstArg] THEN { prod1 _ BC.BigMultiply[ firstArg.num, secondArg.den ]; IF firstArg.sign # secondArg.sign THEN { relation: BC.BigRelation _ BC.BigCompare[prod1, secondArg.num]; IF relation = bigGreater THEN { ratResult.num _ BC.BigSubtract[ prod1, secondArg.num]; ratResult.sign _ firstArg.sign } ELSE { ratResult.num _ BC.BigSubtract[ secondArg.num, prod1]; ratResult.sign _ secondArg.sign } } ELSE { ratResult.num _ BC.BigAdd[prod1, secondArg.num]; ratResult.sign _ firstArg.sign }; ratResult.den _ secondArg.den; RETURN[ratResult]; }; IF Integer[secondArg] THEN { prod2 _ BC.BigMultiply[ secondArg.num, firstArg.den ]; IF secondArg.sign # firstArg.sign THEN { relation: BC.BigRelation _ BC.BigCompare[prod2, firstArg.num]; IF relation = bigGreater THEN { ratResult.num _ BC.BigSubtract[ prod2, firstArg.num]; ratResult.sign _ secondArg.sign } ELSE { ratResult.num _ BC.BigSubtract[ firstArg.num, prod2]; ratResult.sign _ firstArg.sign } } ELSE { ratResult.num _ BC.BigAdd[ prod2, firstArg.num ]; ratResult.sign _ secondArg.sign }; ratResult.den _ firstArg.den; RETURN[ratResult]; }; denomGCD _ BC.BigGCD[ firstArg.den, secondArg.den ]; -- general case [cofactor1, dummy] _ BC.BigDivMod[ firstArg.den, denomGCD]; [cofactor2, dummy] _ BC.BigDivMod[ secondArg.den, denomGCD]; prod1 _ BC.BigMultiply[ firstArg.num, cofactor2 ]; prod2 _ BC.BigMultiply[ secondArg.num, cofactor1 ]; IF firstArg.sign # secondArg.sign THEN { relation: BC.BigRelation _ BC.BigCompare[prod1, prod2]; IF relation = bigGreater THEN { sum _ BC.BigSubtract[ prod1, prod2]; ratResult.sign _ firstArg.sign } ELSE { sum _ BC.BigSubtract[ prod2, prod1]; ratResult.sign _ secondArg.sign } } ELSE { sum _ BC.BigAdd[ prod1, prod2 ]; ratResult.sign _ firstArg.sign }; IF BC.BigZero[sum] THEN { ratResult.sign _ equal; ratResult.num _ sum; ratResult.den _ BC.BigFromSmall[1]; }; quot _ firstArg.den; -- need quot to avoid changing firstArg.den IF NOT BCE.BigOne[denomGCD] THEN { nextGCD _ BC.BigGCD[ sum, denomGCD ]; IF NOT BCE.BigOne[nextGCD] THEN { [sum, dummy] _ BC.BigDivMod[ sum, nextGCD]; [quot, dummy] _ BC.BigDivMod[ quot, nextGCD] } }; ratResult.num _ sum; ratResult.den _ BC.BigMultiply[ quot, cofactor2 ]; RETURN[ratResult]; }; Negate: PUBLIC PROC [arg: BigRat] RETURNS [result: BigRat] ~ { ratResult: BigRat _ Template[]; IF arg.sign = less THEN ratResult.sign _ greater ELSE IF arg.sign = greater THEN ratResult.sign _ less ELSE ratResult.sign _ equal; ratResult.num _ BC.BigCopy[arg.num]; ratResult.den _ BC.BigCopy[arg.den]; RETURN[ratResult]; }; Subtract: PUBLIC PROC [firstArg, secondArg: BigRat] RETURNS [result: BigRat] ~ { RETURN[ Add[ firstArg, Negate[ secondArg ] ] ]; }; Multiply: PUBLIC PROC [firstArg, secondArg: BigRat, simplify: BOOL _ TRUE] RETURNS [result: BigRat]~ { <> ratResult: BigRat _ Template[]; firstGCD, cofactor1, cofactor2, dummy, secondGCD, cofactor3, cofactor4: BC.BigCARD; IF firstArg.sign = equal OR secondArg.sign = equal THEN RETURN[ RatZero ]; IF Integer[firstArg] AND Integer[secondArg] THEN { -- both args integers ratResult.num _ BC.BigMultiply[ firstArg.num, secondArg.num ]; ratResult.den _ BC.BigFromSmall[1]; IF firstArg.sign # secondArg.sign THEN ratResult.sign _ less ELSE ratResult.sign _ greater; RETURN[ratResult]; }; IF Integer[firstArg] THEN { firstGCD _ BC.BigGCD[ firstArg.num, secondArg.den ]; [cofactor1, dummy] _ BC.BigDivMod[ firstArg.num, firstGCD]; [cofactor2, dummy] _ BC.BigDivMod[ secondArg.den, firstGCD]; ratResult.num _ BC.BigMultiply[ cofactor1, secondArg.num ]; ratResult.den _ cofactor2; IF firstArg.sign # secondArg.sign THEN ratResult.sign _ less ELSE ratResult.sign _ greater; RETURN[ratResult]; }; IF Integer[secondArg] THEN { firstGCD _ BC.BigGCD[ secondArg.num, firstArg.den ]; [cofactor1, dummy] _ BC.BigDivMod[ secondArg.num, firstGCD]; [cofactor2, dummy] _ BC.BigDivMod[ firstArg.den, firstGCD]; ratResult.num _ BC.BigMultiply[ cofactor1, firstArg.num ]; ratResult.den _ cofactor2; IF firstArg.sign # secondArg.sign THEN ratResult.sign _ less ELSE ratResult.sign _ greater; RETURN[ratResult]; }; firstGCD _ BC.BigGCD[ firstArg.num, secondArg.den ]; -- general case [cofactor1, dummy] _ BC.BigDivMod[ firstArg.num, firstGCD]; [cofactor2, dummy] _ BC.BigDivMod[ secondArg.den, firstGCD]; secondGCD _ BC.BigGCD[ secondArg.num, firstArg.den ]; [cofactor3, dummy] _ BC.BigDivMod[ secondArg.num, secondGCD]; [cofactor4, dummy] _ BC.BigDivMod[ firstArg.den, secondGCD]; ratResult.num _ BC.BigMultiply[ cofactor1, cofactor3 ]; ratResult.den _ BC.BigMultiply[ cofactor2, cofactor4 ]; IF firstArg.sign # secondArg.sign THEN ratResult.sign _ less ELSE ratResult.sign _ greater; RETURN[ratResult]; }; Invert: PUBLIC PROC [arg: BigRat] RETURNS [result: BigRat]~ { <> <> ratResult: BigRat _ Template[]; IF arg.sign = equal THEN ERROR BigRatsError[$DivideByZero]; ratResult.sign _ arg.sign; ratResult.num _ BC.BigCopy[ arg.den ]; ratResult.den _ BC.BigCopy[ arg.num ]; RETURN[ratResult]; }; Divide: PUBLIC PROC [firstArg, secondArg: BigRat, simplify: BOOL _ TRUE] RETURNS [result: BigRat]~ { <> IF firstArg.sign = equal THEN RETURN[ firstArg ] ELSE RETURN[ Multiply[ firstArg, Invert[secondArg] ] ]; }; <> <> <<};>> <<>> <> <> < less, equal => equal, less => greater, ENDCASE => ERROR;>> <> <<};>> <<>> <> <> <<};>> <<>> <> <> <<};>> <<>> <> <> < RETURN [RatZero];>> < RETURN [x];>> < RETURN [y];>> < {>> <> <> <> <> <> <> <> <<}>> <> <> <<[xn, yd] _ SimplifyPair[xn, yd];>> <<[yn, xd] _ SimplifyPair[yn, xd];>> <<};>> <> <> <> <> <<]];>> <<};>> <<};>> <<>> <> <> <<};>> <<>> <> <> < ERROR RuntimeError.ZeroDivisor;>> < RETURN [RatZero];>> < RETURN [x];>> < RETURN [Invert[y]];>> < {>> <> <> <> <> <> <> <> <<}>> <> <> <<[xn, yd] _ SimplifyPair[xn, yd];>> <<[yn, xd] _ SimplifyPair[yn, xd];>> <<};>> <> <> <> <> <<]];>> <<};>> <<};>> <> Sign: PUBLIC PROC [arg: BigRat] RETURNS [Basics.Comparison] = { RETURN [arg.sign] }; <<>> Abs: PUBLIC PROC [arg: BigRat] RETURNS [result: BigRat] ~ { ratResult: BigRat _ Template[]; ratResult.sign _ arg.sign; IF arg.sign = less THEN ratResult.sign _ greater; ratResult.num _ BC.BigCopy[arg.num]; ratResult.den _ BC.BigCopy[arg.den]; RETURN[ratResult]; }; <> <> <<};>> <<>> Compare: PUBLIC PROC [firstArg, secondArg: BigRat] RETURNS [Basics.Comparison] ~ { diff: BigRat _ Subtract[firstArg, secondArg]; SELECT diff.sign FROM less => RETURN[less]; equal => RETURN[equal]; ENDCASE; RETURN[greater]; }; <> <> <> <> < RETURN [SELECT y.sign FROM>> < greater, equal => equal, greater => less, ENDCASE => ERROR];>> < SELECT y.sign FROM>> < {>> <> <> < RETURN [less];>> < SELECT y.sign FROM>> < {};>> < RETURN [greater];>> < ERROR;>> <> <> < >> <> < {};>> < RETURN [posLess];>> <>> <> < RETURN [posGreater];>> < RETURN [equal];>> < RETURN [posLess];>> < ERROR;>> <>> <> < {};>> < RETURN [posGreater];>> < ERROR;>> <> <> <<< -2 => RETURN [posLess];>> <<> 2 => RETURN [posGreater];>> <> <> <> < RETURN [posLess];>> < RETURN [equal];>> < RETURN [posGreater];>> < ERROR;>> <<};>> <<>> <> <> <> <> < SELECT BigCardinals.BigCompare[x.num, y.num] FROM>> < RETURN [TRUE];>> <> <> <> <<};>> <<>> Integer: PUBLIC PROC [in: BigRat] RETURNS [BOOLEAN] ~ { <> RETURN[ BCE.BigOne[in.den] ]; }; <> ToTheX: PUBLIC PROC [rat: BigRat, x: INT] RETURNS [BigRat] = { less: BOOL _ rat.sign = less; abs: CARD = ABS[x]; num: BigCard _ InternalBCPower[BigCardOne, rat.num, abs]; den: BigCard _ InternalBCPower[BigCardOne, rat.den, abs]; IF less AND Basics.LowHalf[abs] MOD 2 = 0 THEN less _ FALSE; RETURN [IF x < 0 THEN Breed[den, num, less] ELSE Breed[num, den, less]]; }; TwoToTheX: PUBLIC PROC [x: INT, less: BOOL _ FALSE] RETURNS [BigRat] = { abs: CARD _ ABS[x]; IF abs = 0 AND NOT less THEN RETURN [RatOne] ELSE { absDiv: CARDINAL _ abs / bitsPerWord; absMod: CARDINAL _ abs MOD bitsPerWord; size: CARDINAL _ absDiv + 1; accum: BigCard _ [size, NEW[BigCardinals.BigCARDRec[size]]]; FOR i: CARDINAL IN [0..absDiv) DO accum.contents[i] _ 0; ENDLOOP; accum.contents[absDiv] _ Basics.BITSHIFT[1, absMod]; IF x < 0 THEN RETURN [Breed[BigCardOne, accum, less]] ELSE RETURN [Breed[accum, BigCardOne, less]]; }; }; BCToTheX: PUBLIC PROC [bc: BigCard, x: INT, less: BOOL _ FALSE] RETURNS [BigRat] = { abs: CARD _ ABS[x]; prod: BigCard _ bc; accum: BigCard _ InternalBCPower[BigCardOne, bc, ABS[x]]; RETURN [IF x < 0 THEN Breed[BigCardOne, accum, less] ELSE Breed[accum, BigCardOne, less]]; }; <> AddSub: PROC [x, y: BigRat, xs, ys: Basics.Comparison] RETURNS [BigRat] = { num1: BigCard _ x.num; num2: BigCard _ y.num; negate: BOOL _ xs = less; xDen: BigCard _ x.den; yDen: BigCard _ y.den; den: BigCard _ xDen; IF xs = equal THEN RETURN [y]; IF ys = equal THEN RETURN [x]; IF BigCardinals.BigCompare[xDen, yDen] # bigEqual THEN { [xDen, yDen] _ SimplifyPair[xDen, yDen]; <> den _ LocalBCMultiply[den, yDen]; <> num1 _ LocalBCMultiply[num1, yDen]; num2 _ LocalBCMultiply[num2, xDen]; }; IF xs = ys THEN RETURN [Simplify[Breed[BigCardinals.BigAdd[num1, num2], den, negate]]]; SELECT BigCardinals.BigCompare[num1, num2] FROM bigLess => {t: BigCard _ num1; num1 _ num2; num2 _ t; negate _ NOT negate}; bigGreater => {}; bigEqual => RETURN [RatZero]; ENDCASE; RETURN [Simplify[Breed[BigCardinals.BigSubtract[num1, num2], den, negate]]]; }; <> < 1 OR y.size > 1 DO>> <> <> <> <> <> <> <<};>> <<>> <> <> <> <> <> <> <> <<};>> <<>> Simplify: PROC [rat: BigRat] RETURNS [BigRat] = { x: BigCard; y: BigCard; [x, y] _ SimplifyPair[rat.num, rat.den]; IF rat.num = x THEN RETURN [rat]; RETURN [Breed[x, y, rat.sign = less]]; }; tryShift: BOOL _ TRUE; tryShift2: BOOL _ TRUE; SimplifyPair: PROC [num, den: BigCard] RETURNS [BigCard, BigCard] = { x: BigCard _ num; y: BigCard _ den; wc: NAT _ 0; bits: NAT _ 0; IF x.size = 0 THEN RETURN [x, y]; IF x.size = 1 AND x.contents[0] = 1 THEN RETURN [x, y]; IF y.size = 1 AND y.contents[0] = 1 THEN RETURN [x, y]; IF tryShift THEN { <> FOR i: NAT IN [0..MIN[x.size, y.size]) DO xi: CARDINAL _ x.contents[i]; yi: CARDINAL _ y.contents[i]; bits _ 0; IF xi = 0 AND yi = 0 THEN wc _ wc + 1 ELSE { DO IF xi MOD 2 = 1 OR yi MOD 2 = 1 THEN EXIT; xi _ xi / 2; yi _ yi / 2; bits _ bits + 1; ENDLOOP; EXIT; }; ENDLOOP; IF wc # 0 OR bits # 0 THEN { x _ num _ ShiftRight[x, wc, bits]; y _ den _ ShiftRight[y, wc, bits]; }; }; DO IF tryShift2 THEN { <> x _ RightJustify[x]; y _ RightJustify[y]; }; IF x.size = 1 AND y.size = 1 THEN { <> xc: CARDINAL _ x.contents[0]; yc: CARDINAL _ y.contents[0]; DO r: CARDINAL _ xc MOD yc; IF r = 0 THEN { IF yc # 1 THEN { gcd: BigCard _ BigCardinals.BigFromSmall[yc]; x _ BigCardinals.BigDivMod[num, gcd, FALSE].quo; y _ BigCardinals.BigDivMod[den, gcd, FALSE].quo; } ELSE { x _ num; y _ den; }; RETURN [x, y]; }; xc _ yc; yc _ r; ENDLOOP; } ELSE { r: BigCard; Process.CheckForAbort[]; r _ BigCardinals.BigDivMod[x, y].rem; IF r.size = 0 THEN { <> RETURN [ BigCardinals.BigDivMod[num, y, FALSE].quo, BigCardinals.BigDivMod[den, y, FALSE].quo ]; }; x _ y; y _ r; }; ENDLOOP; }; Breed: PROC [num, den: BigCard, negate: BOOL _ FALSE] RETURNS [BigRat] = { IF den.size = 0 THEN ERROR RuntimeError.ZeroDivisor; IF num.size = 0 THEN RETURN [RatZero]; Process.CheckForAbort[]; IF den.size = 1 AND den.contents[0] = 1 THEN IF num.size = 1 AND num.contents[0] = 1 AND NOT negate THEN RETURN [RatOne]; RETURN [NEW[BigRatRep _ [sign: IF negate THEN less ELSE greater, num: num, den: den]]]; }; InternalBCPower: PUBLIC PROC [bc: BigCard, base: BigCard, x: CARD] RETURNS [BigCard] = { prod: BigCard _ base; SELECT TRUE FROM bc.size = 0 => RETURN [BigCardZero]; x = 0 => RETURN [bc]; base.size = 0 => RETURN [BigCardZero]; ENDCASE => DO IF Basics.LowHalf[x] MOD 2 = 1 THEN bc _ LocalBCMultiply[bc, prod]; x _ Basics.DoubleShiftRight[[lc[x]], 1].lc; IF x = 0 THEN EXIT; prod _ LocalBCMultiply[prod, prod]; ENDLOOP; RETURN [bc]; }; RightJustify: PROC [bc: BigCard] RETURNS [BigCard] = { wc: NAT _ 0; bits: NAT _ 0; FOR i: NAT IN [0..bc.size) DO xi: CARDINAL _ bc.contents[i]; bits _ 0; IF xi = 0 THEN wc _ wc + 1 ELSE { DO IF xi MOD 2 = 1 THEN EXIT; xi _ xi / 2; bits _ bits + 1; ENDLOOP; EXIT; }; ENDLOOP; IF wc # 0 OR bits # 0 THEN { RETURN[ShiftRight[bc, wc, bits]]; }; RETURN [bc]; }; ShiftRight: PROC [bc: BigCard, words: NAT, bits: INTEGER] RETURNS [BigCard] = { size: NAT _ bc.size-words; IF size # 0 THEN TRUSTED { new: BigCard _ [size, NEW[BigCardinals.BigCARDRec[size]]]; PrincOpsUtils.LongCopy[from: @bc.contents[words], nwords: size, to: @new.contents[0] ]; IF bits # 0 THEN { FOR i: NAT IN [1..size) DO c0: CARDINAL _ new.contents[i-1]; c1: CARDINAL _ new.contents[i]; new.contents[i-1] _ Basics.BITOR[Basics.BITSHIFT[c0, -bits], Basics.BITSHIFT[c1, bitsPerWord-bits]]; ENDLOOP; IF (new.contents[size-1] _ Basics.BITSHIFT[new.contents[size-1], -bits]) = 0 THEN new.size _ size - 1; }; RETURN [new]; }; RETURN [BigCardZero]; }; LocalBCMultiply: PROC [x, y: BigCard] RETURNS [BigCard] = { xs: CARDINAL = x.size; ys: CARDINAL = y.size; xc: CARDINAL; yc: CARDINAL; SELECT TRUE FROM xs = 0, ys = 0 => RETURN [BigCardZero]; xs = 1 AND (xc _ x.contents[0]) = 1 => RETURN [y]; ys = 1 AND (yc _ y.contents[0]) = 1 => RETURN [x]; xs = 1 AND ys = 1 => RETURN [BCE.LCToBC[Basics.LongMult[xc, yc]]]; ENDCASE => RETURN [BigCardinals.BigMultiply[x, y]]; }; END.