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
] ];

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] ]
}; 

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] ]   ];
};

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];
};

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]]];
};

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.

$ZBigRatsImpl.mesa
Last Edited by: Arnon, July 19, 1985 2:54:46 pm PDT

Types
Constants
Variables
Creation
FromPairBC: PUBLIC PROC [num, den: BigCard, less: BOOL _ FALSE] RETURNS [out: BigRat] ~ {
gcd, dummy: BC.BigCARD;
out _ Template[];
IF BC.BigZero[num] THEN {
out.sign _ equal;
out.num _ num;
out.den _ den
}
ELSE {
out.sign _ IF less THEN less ELSE greater;
gcd _ BC.BigGCD[ num, den ]; -- general case
[out.num, dummy] _ BC.BigDivMod[ num, gcd];
[out.den, dummy] _ BC.BigDivMod[ den, gcd]
}
};

FromPairLC: PUBLIC PROC [num, den: CARD, less: BOOL _ FALSE] RETURNS [out: BigRat] ~ {
bignum, bigden, gcd, dummy: BC.BigCARD;
out _ Template[];
IF num = 0 THEN {
out.sign _ equal;
out.num _ BCE.LCToBC[num];
out.den _ BigCardOne;
}
ELSE {
out.sign _ IF less THEN less ELSE greater;
bignum _ BC.BigFromSmall[num];
bigden _ BC.BigFromSmall[den];
gcd _ BC.BigGCD[ bignum, bigden ]; -- general case
[out.num, dummy] _ BC.BigDivMod[ bignum, gcd];
[out.den, dummy] _ BC.BigDivMod[ bigden, gcd]
}
};
I/O and Conversion
reads a BigRat, possibly preceded by sign, with or without explicit denominator.
FromRope: PUBLIC PROC [in: Rope.ROPE] RETURNS [out: BigRat] ~ {
stream: IO.STREAM _ IO.RIS[in];
out _ Read[stream];
RETURN[out];
};

Expressed as a ratio
Expressed with a decimal point
Simply a non-less integer
BigRatFromREALRope: PUBLIC PROC [in: Rope.ROPE] RETURNS [out: BigRat] ~ {
Intended to allow decimal notation input of BigRats.
dotPos: INT = in.Find["."]; -- decimal point assumed always present
minusPos: INT = in.Find["-"];
integer, fraction: BC.BigCARD;
fractionLength: CARDINAL;
sign: INTEGER;
num, den: 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;
den _ BCE.BigPowerOfTen[ fractionLength ];
num _ BC.BigAdd[ BC.BigMultiply[ integer, den ], fraction ];
RETURN[ FromPairBC[ sign, num, den] ];
};

Used for displaying the values of BigRats. If in is greater, then the output Rope is unsigned. The default of reuse: FALSE preserves the input BigRat.If in is an integer, then if showDenomOne = FALSE the den of one is not printed, if TRUE then it is.
BigRatFromREAL: PUBLIC PROC [in: REAL] RETURNS [out:BigRat] ~ {
Convert a REAL to a BigRat.  The REAL is viewed as a decimal fraction, whose num and den become the num and den of the resulting BigRat.
separator: INT = 10000;
expsep: CARDINAL = 5;
exp, z: INT;
lowz, midz, highz: CARDINAL;
num, den: BC. BigCARD;
sign: INTEGER;
ty: Real.NumberType;
precision: CARDINAL _ 10;
[type: ty, fr: z, exp10: exp] _ Real.RealToPair[in, precision];
SELECT ty FROM
nan => ERROR BigRatsError[$BigRatFromREALnan];
infinity => ERROR BigRatsError[$BigRatFromREALinfinity];
equal => RETURN[ RatZero ];
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;
num _ BC.BigFromSmall[ highz ];
num _ BC.BigMultiply[ num, BCE.BigPowerOfTen[expsep -1 ]  ];
num _ BC.BigAdd[ num, BC.BigFromSmall[ midz ]  ]; 
num _ BC.BigMultiply[ num, BCE.BigPowerOfTen[expsep -1 ]  ];
num _ BC.BigAdd[ num, BC.BigFromSmall[ lowz ]  ]; 
IF exp < 0 THEN den _ BCE.BigPowerOfTen[ - exp]
ELSE {
den _ BC.BigFromSmall[1];
num _ BC.BigMultiply[ num, BCE.BigPowerOfTen[exp] ]
};
RETURN[ FromPairBC[sign, num, den] ];
};
};

BigRatToREAL: PUBLIC PROC [in: BigRat, reuse: BOOLEAN _ FALSE] RETURNS [out: REAL] ~ {
Convert a BigRat to a real.  For the time being, it is assumed that the BigRat is not so large in absolute value as to cause floating point overflow.
IF in.sign = equal THEN RETURN[0.0];
out _ BCE.BigToREAL[in.num];
IF NOT BCE.BigOne[in.den] THEN out _ out / BCE.BigToREAL[in.den];
IF in.sign = less THEN out _ - out;
};

There was a carry in that last thing that disturbed the sizing
We should now have the right stuff in hand
Arithmetic
Adapted from SAC-2 RNSUM
Adapted from SAC-2 RNPROD
Inverse of a non-equal BigRat.
Adapted from SAC-2 RNINV.
Adapted from SAC-2 RNQ
Add: PUBLIC PROC [x, y: BigRat] RETURNS [BigRat] = {
RETURN [AddSub[x, y, x.sign, y.sign]];
};

Sub: PUBLIC PROC [x, y: BigRat] RETURNS [BigRat] = {
ys: Basics.Comparison _ SELECT y.sign FROM
greater => less, equal => equal, less => greater, ENDCASE => ERROR;
RETURN [AddSub[x, y, x.sign, ys]];
};

Negate: PUBLIC PROC [rat: BigRat] RETURNS [BigRat] = {
RETURN [Breed[rat.num, rat.den, rat.sign = greater]];
};

Abs: PUBLIC PROC [rat: BigRat] RETURNS [BigRat] = {
RETURN [Breed[rat.num, rat.den, FALSE]];
};

Multiply: PUBLIC PROC [x, y: BigRat, simplify: BOOL _ TRUE] RETURNS [BigRat] = {
SELECT TRUE FROM
x = RatZero, y = RatZero => RETURN [RatZero];
y = RatOne => RETURN [x];
x = RatOne => RETURN [y];
ENDCASE => {
xn: BigCard _ x.num;
yn: BigCard _ y.num;
xd: BigCard _ x.den;
yd: BigCard _ y.den;
IF xd.contents[0] = yd.contents[0] AND xd.size = yd.size AND (xd.size = 1 OR BigCardinals.BigCompare[xd, yd] = bigEqual)
THEN {
No simplification possible
}
ELSE {
Cross-simplify
[xn, yd] _ SimplifyPair[xn, yd];
[yn, xd] _ SimplifyPair[yn, xd];
};
RETURN [Breed[
num: LocalBCMultiply[xn, yn],
den: LocalBCMultiply[xd, yd],
negate: x.sign # y.sign
]];
};
};

Invert: PUBLIC PROC [rat: BigRat] RETURNS [BigRat] = {
RETURN [Breed[rat.den, rat.num, rat.sign = less]];
};

Divide: PUBLIC PROC [x, y: BigRat, simplify: BOOL _ TRUE] RETURNS [BigRat] = {
SELECT TRUE FROM
y = RatZero => ERROR RuntimeError.ZeroDivisor;
x = RatZero => RETURN [RatZero];
y = RatOne => RETURN [x];
x = RatOne => RETURN [Invert[y]];
ENDCASE => {
xn: BigCard _ x.num;
yn: BigCard _ y.den;
xd: BigCard _ x.den;
yd: BigCard _ y.num;
IF xd.contents[0] = yd.contents[0] AND xd.size = yd.size AND (xd.size = 1 OR BigCardinals.BigCompare[xd, yd] = bigEqual)
THEN {
No simplification possible
}
ELSE {
Cross-simplify
[xn, yd] _ SimplifyPair[xn, yd];
[yn, xd] _ SimplifyPair[yn, xd];
};
RETURN [Breed[
num: LocalBCMultiply[xn, yn],
den: LocalBCMultiply[xd, yd],
negate: x.sign # y.sign
]];
};
};
Comparison

Abs: PUBLIC PROC [rat: BigRat] RETURNS [BigRat] = {
RETURN [Breed[rat.num, rat.den, FALSE]];
};

Compare: PUBLIC PROC [x, y: BigRat] RETURNS [Basics.Comparison] = {
posLess: Basics.Comparison _ less;
posGreater: Basics.Comparison _ greater;
SELECT x.sign FROM
equal => RETURN [SELECT y.sign FROM
less => greater, equal => equal, greater => less, ENDCASE => ERROR];
less => SELECT y.sign FROM
less => {
Reverse comparison sense for double negatives
posLess _ greater; posGreater _ less};
ENDCASE => RETURN [less];
greater => SELECT y.sign FROM
greater => {};
ENDCASE => RETURN [greater];
ENDCASE => ERROR;
The first comparison is based on comparisons of the pieces.  This is quicker than trying to multiply out to do the comparison.
SELECT BigCardinals.BigCompare[x.num, y.num] FROM
bigLess => 
SELECT BigCardinals.BigCompare[x.den, y.den] FROM
bigLess => {};
ENDCASE => RETURN [posLess];
bigEqual =>
SELECT BigCardinals.BigCompare[x.den, y.den] FROM
bigLess => RETURN [posGreater];
bigEqual => RETURN [equal];
bigGreater => RETURN [posLess];
ENDCASE => ERROR;
bigGreater =>
SELECT BigCardinals.BigCompare[x.den, y.den] FROM
bigGreater => {};
ENDCASE => RETURN [posGreater];
ENDCASE => ERROR;
The next try is based on the positions of the leading ones in the various parts.  This gives us a quick and fuzzy estimate of the Log2[x] and Log2[y].  If the difference is great enough to overcome the fuzz, then we can give an unambiguous answer.
SELECT (BCE.FirstOneBit[x.num]-BCE.FirstOneBit[x.den])
- (BCE.FirstOneBit[y.num]-BCE.FirstOneBit[y.den]) FROM
< -2 => RETURN [posLess];
> 2 => RETURN [posGreater];
ENDCASE;
At this point the signs are equal and the magnitudes are close, so we actually have to multiply in order to compare the numbers.
SELECT BigCardinals.BigCompare[
LocalBCMultiply[x.num, y.den],
LocalBCMultiply[y.num, x.den]] FROM
bigLess => RETURN [posLess];
bigEqual => RETURN [equal];
bigGreater => RETURN [posGreater];
ENDCASE => ERROR;
};

Equal: PUBLIC PROC [x, y: BigRat, simplify: BOOL _ TRUE] RETURNS [BOOL] = {
IF x = y THEN RETURN [TRUE];
IF x.sign = y.sign THEN
SELECT BigCardinals.BigCompare[x.num, y.num] FROM
bigEqual => SELECT BigCardinals.BigCompare[x.num, y.num] FROM
bigEqual => RETURN [TRUE];
ENDCASE;
ENDCASE;
RETURN [FALSE];
};

Test if a BigRat is an integer
Extras
Utilities
Simplify the denominators to remove the cofactor
Now the denominator has one cofactor removed
Gcd: PROC [x, y: BigCard] RETURNS [BigCard] = {
WHILE x.size > 1 OR y.size > 1 DO
r: BigCard _ BigCardinals.BigDivMod[x, y].rem;
IF r.size = 0 THEN RETURN [y];
x _ y;
y _ r;
ENDLOOP;
RETURN [BigCardinals.BigFromSmall[GcdSmall[x.contents[0], y.contents[0]]]];
};

GcdSmall: PROC [x, y: CARDINAL] RETURNS [CARDINAL] = {
DO
r: CARDINAL _ x MOD y;
IF r = 0 THEN RETURN [y];
x _ y;
y _ r;
ENDLOOP;
};

We can very quickly get rid of any common factors of two, which is a substantial performance improvement.
Given that we have already clobbered all of the common factors of two we can peel off any factors of two from either x or y since they cannot contribute to the GCD.  This is a substantial speedup!
At this point the mod is small enough to be done quickly
y has gcd
Κ)Ÿ˜Jš
œ™J™3J™š
Οk	˜	Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ
˜
Icodešœ
˜K˜K˜Kš
œ˜Jš
œ
˜
Jš
œ˜J˜Jš
œ˜Jš
œ˜—J˜
head2šœ
œ
˜JšœœC˜aJšœ˜J˜—Jš
œœ
œ
œœœ
œ˜\
headš
Οn™Jš	œœ
œ
œœ
˜AKšœ
œ˜+Kšœœœ
œ
˜Kšœœœ
˜Kšœœœ
œ
˜—š
œ	™	Kš
œ4˜4Kš
œ3˜3Kš
œ3˜3Kš
œ4˜4Kšœœ?˜TKšœœAΟc#˜xKš
œ$˜$Kšœ0œ˜7—š
ž	™	šžœœ˜$Jšœ˜J˜—šžœœ˜,šœ˜Kšœ
œ
œ˜Kšœ
˜—Kšœ
œ˜J˜—šž	œœ˜Jšœ˜J˜—šž
œœ˜ Kš	œœ
œœ
œ˜Kšœ˜K˜—šžœœ
˜Jšœ	œ˜%J˜—šž
œœ˜Jšœœ˜"Jš
œ˜—šž	œœ˜Jšœ˜Jš
œ˜—šžœœ˜Jšœ
˜Jš
œ˜—šžœœ˜+Jšœ˜Jš
œ˜—šžœœ
˜Jšœœœ˜CJš
œ˜—šžœœ˜Jšœ
œ˜(Jš
œ˜—šž
œœ
˜Jšœœœ˜HJš
œ˜—šž
œœ
˜Jšœœœ˜HJš
œ˜—šž
œœ˜Jšœ
œœ˜NJš
œ˜—šž	œœ˜!Jšœœ˜$Jš
œ˜—šžœœ˜Jšœœ˜#Jš
œ˜—šžœœ˜$Jšœ
œœ˜GJš
œ˜—šžœœ˜Jšœ	œ˜&Jš
œ˜—šžœœ
˜Jšœ	œœ˜FJš
œ˜—šž
œœœ
œ˜?J˜J˜Jš
œ$˜$J˜Jš
œ$˜$Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜J˜Kš
œ˜Kš
œ˜Kš
œ˜K˜K˜Kš
œ˜Kšœ
œ
˜Kš
œ˜Kš
œ˜K˜K˜K˜K˜Kšœ	œ
˜Kš
œ˜K˜Kš
œ˜K˜Kšœœ
˜Kšœœ
˜Kšœœ
˜Kšœœ
˜Kšœœ
˜ K˜Jšœ
˜
K˜K˜—š
žœœ
œ
œ
œ˜6Jš
œ˜Jšœ˜K˜——š
œ™šž
œœ
œœœœ™YJšœœ	™Jš
œ™šœ
œœ™Jš
œ™Jš
œ™J™
J™
—šœ™Jšœœœœ	™*JšœœŸ™,Jšœœ™+Jšœœ™*J™
—J™J™—šž
œœ
œœœœœ™VJšœœ	™'Jš
œ™šœ	œ™Jš
œ™Jšœ
œ
™Jš
œ™J™
—šœ™Jšœœœœ	™*Jšœ	œ™Jšœ	œ™JšœœŸ™2Jšœœ™.Jšœœ™-J™
—J™J˜—šž
œœ
œœœœ
˜TJšœ#˜)K˜K˜—šž
œœ
œœœœœ
˜QJšœœœ˜AK˜K˜—šžœœ
œœœœ
˜JJšœ˜%K˜K˜—šžœœ
œœœœœ
˜Gšœœ
œ˜,šœ˜Kšœœ˜Kšœœ
˜Kšœ
˜——Jšœœ ˜1K˜——š
œ™šžœœ
œœ
œœ˜;Jš
œP™PJšœ
œ	˜Jšœœ
˜JšœœŸ%˜9Jš
œ"˜"Jš
œ˜šœœ˜Jš
œ˜Jš
œ˜J˜
—šœ
œœ˜ Jš
œ˜Jš
œ˜J˜—Jš
œ0˜0Jšœœ!˜)Jš
œ˜šœœœŸ˜:Kšœ
œœœ#œ
œ
œ
œ
œ˜r—šœ˜JšœŸ	œ
˜Jš
œ˜Jš
œ0˜0Jšœœ!˜)Kšœ
œœœœ
œ
œ
œ
œ˜mK˜—Kšœ˜K˜K˜—š
žœœ
œœœ™?Kš	œœ
œœ
œ™Kš
œ™Kšœ™K™K™—š
žœœ
œœœ
˜7Kšœœ˜$Kšœœ˜
Kšœœ˜
Kšœœ˜)Kš
œ˜Kš
œ ˜ šœœ˜Kš
œ™Kšœœ˜&Kšœœ˜%Kšœa˜gK˜—Kš
œ ˜ šœœ˜Kš
œ™Kšœœ˜(Kšœœ˜'Kšœ
œ˜&Kš
œM˜MKš
œE˜EKšœ"˜(K˜—Kš
œ™Kšœ1˜7K˜K˜—š
žœœ
œœœ™IJ™4JšœœŸ'™CJšœ
œ™Jšœœ	™Jšœœ
™Jšœœ
™Jšœ
œ	™Jšœœœ
™.Jšœ
œ5™AJšœ
œœ
™%Jšœœ<™IJš
œ+™+Jšœœ!™*Jšœœ	œ)™<Jšœ ™&J™J™—š
žœœ
œœœ˜9Kšœœ
œ˜&šœœœ˜6šœ˜Kšœœœ
œ
˜%Kš
œ&˜&K˜—K˜—šœ˜Kšœœœ
œ
˜%Kš
œ'˜'K˜Kš
œ&˜&K˜—K˜K˜—š
žœœœœœ˜KKšœœœ
œ˜K˜K˜Kš
œ1˜1Kšœœ
œ˜,K˜Kš
œ2˜2šœœ˜&Kš
œA˜Ašœ:œ˜BKš
œ@˜@Kš
œ%˜%K˜—K˜—Kšœ3˜5šœœ˜Kšœœ(˜2Kšœ˜Kšœœ
œœ
˜DKšœ˜K˜—Kšœœ˜K˜K˜—šžœœ
œœœ	œœœœ˜uJšœ.žœižœ_™ϊ
Jšœ
œœ
˜Jšœœœ
œœ
œœ
œ
˜Sšœ˜Jšœœ˜*Jšœœ˜/šœ
œ
œœ˜)Jš
œ˜Jšœœ˜/J˜—Jšœ˜J˜
—J˜J˜—š
žœœ
œ
œ
œ˜6Jšœ&œœ˜7Jš
œ˜J˜—š
žœœ
œœœ™?Jšœ
œœc™ˆ
Jšœœ	™Jšœœ™Jšœœ
™Jšœœ
™Jšœ
œ
™Jšœœ
™J™Jšœœ™Jš
œ?™?šœ™Jšœœ"™.Jšœœ'™8Jšœ	œ™—šœ™šœœ™Jš
œ™Jš
œ	™	Jš
œ
™
—Jšœ
™Jš
œ(™(Jš
œ™Jš
œ(™(Jš
œ™Jšœœ™Jšœœœ™<Jšœœœ™2Jšœœœ™<Jšœœœ™2Jšœ	œœ™/šœ™Jšœœ™Jšœœœ™3J™—Jšœ™%J™—J™J™—šžœœ
œœœœœ™VJš
ϥ
™•
Jšœœ
œ™$Jšœœ™Jš
œ
œ
œœ
œ™AJšœœ
™#J™J™—š
žœœ
œœœ
˜7Kš
œ"˜"šœ˜˜Kš
œ3˜3Kš
œ&˜&Kšœ˜#K˜—Kšœœ˜Kšœœ
˜—K˜K˜—šžœœœœ˜4šœ
œ
˜Kšœœ˜!Kšœœ˜šœ˜Kšœ
œœ˜)Kšœ
œœ˜)Kšœœ˜!Kš
œ$˜$Kš
œ(˜(Kš
œ˜Kšœ@œ˜GšœF˜Pš
œ˜Kš
œ+˜+šœœ˜Kš
œ>™>Kš
œD˜DKš
œ˜K˜—K˜—Kšœ
˜—šœ
˜šœœ˜Kš
œ*™*Kš
œJ˜JKšœ6œ/˜jšœ˜Kš
œ/˜/Kš
œ˜Kšœ
˜—šœ%œ˜-šœ'˜.Kš
œ0˜0Kš
œ˜Kšœ
˜—Kš
œ˜K˜—Kšœ˜K˜—Kšœœ
˜—K˜——K˜K˜—šžœœœ ˜Kšœ+˜5Kšœœ˜%Kšœœ˜)š
œ˜Kš
œ
˜
Kš
œ6˜6Kš
œ˜Kš
œ˜—Kšœœ
˜—K˜——š
ž
™
šžœœœ
˜&Kšœœ œœ	˜DK˜K˜—šžœœ
œœ˜KJš
œ™J˜JšœIœ	˜TJš
œœ
œŸœŸ
œ˜CJšœ
œœ
œ
Ÿœ	Ÿ
œ˜DšœœœŸ˜Hšœ œ˜(Jšœ
œœ)˜Fšœœ˜Jšœœ+˜=Jš
œ˜Jš
œ
˜
—šœ˜Jšœœ+˜=Jš
œ˜J˜
—J˜
—šœ˜Jšœœ'˜9Jš
œ˜J˜—Jšœœ˜#J•StartOfExpansion[]šœ
œœ˜:Jšœ˜J˜—šœœ˜Jšœœ,˜6šœ œ˜(Jšœ
œœ"˜?šœœ˜Jšœœ$˜6Jš
œ˜Jš
œ
˜
—šœ˜Jšœœ$˜6Jš
œ˜J˜
—J˜
—šœ˜Jšœœ˜0Jš
œ˜J˜—Jš
œ˜Jšœ˜J˜—šœœ˜Jšœœ,˜6šœ œ˜(Jšœ
œœ!˜>šœœ˜Jšœœ#˜5Jš
œ˜Jš
œ
˜
—šœ˜Jšœœ#˜5Jš
œ˜J˜
—J˜
—šœ˜Jšœœ˜1Jš
œ˜J˜—Jš
œ˜Jšœ˜J˜—Jšœœ(Ÿ˜DJšœœ$˜;Jšœœ%˜<Jšœœ(˜2Jšœœ)˜3šœ œ˜(Jšœ
œœ˜7šœœ˜Jšœœ˜$Jš
œ˜Jš
œ
˜
—šœ˜Jšœœ˜$Jš
œ˜J˜
—J˜
—šœ˜Jšœœ˜ Jš
œ˜J˜—šœ
œœ˜Jš
œ˜Jš
œ˜Jšœœ˜#J˜—JšœŸœŸ
œ˜@šœ
œ
œœ˜"Jšœ
œ˜%šœ
œ
œœ˜!Jšœœ˜+Jšœœ˜,J˜
—J˜—Jš
œ˜Jšœœ ˜2Jšœ˜J˜J˜—šžœœ
œœ˜>J˜šœœ˜5Jšœœœ˜M—Jšœœ˜$Jšœœ˜$Jšœ˜J˜J˜—šžœœ
œœ˜PJšœ)˜/J˜J˜—šžœœ
œ)œœœ˜fJš
œ™J˜JšœHœ	˜SJšœœœ
œ˜JšœœœŸ˜HJšœœ,˜>Jšœœ˜#Jšœ œœ˜[Jšœ˜J˜—šœœ˜Jšœœ(˜5Jšœœ$˜;Jšœœ%˜<Jšœœ)˜;Jš
œ˜Jšœ œœ˜[Jšœ˜J˜—šœœ˜Jšœœ(˜5Jšœœ%˜<Jšœœ$˜;Jšœœ(˜:Jš
œ˜Jšœ œœ˜[Jšœ˜J˜—Jšœœ)Ÿ˜EJšœœ$˜;Jšœœ%˜<Jšœœ(˜6Jšœœ&˜=Jšœœ%˜<Jšœœ%˜7Jšœœ%˜7Jšœ œœ˜[Jšœ˜J˜J˜—šžœœ
œœ˜=Jš
œ™J™J˜Jšœœ
œ˜;Jš
œ˜Jšœœ˜&Jšœœ˜&Jšœ˜J˜J˜—šžœœ
œ)œœœ˜dJš
œ™šœœ
œ
˜5Jšœ.˜4—J˜J˜—šžœœœ
™4Jšœ ™&K™K™—šžœœœ
™4šœœ™*Kšœ2œœ
™C—Jšœ™"K™K™—šžœœœ
™6Kšœ/™5K™K™—šžœœœ
™3Kšœœ™(K™K™—šžœœ
œœœœ
™Pšœ
œ
™Kšœœ™-Kšœœ™Kšœœ™šœ™Kš
œ™Kš
œ™Kš
œ™Kš
œ™šœ!œœœ,™xšœ™Kš
œ™K™
—šœ™Kš
œ™Kš
œ ™ Kš
œ ™ K™——šœ™Kš
œ™Kš
œ™Kš
œ™Kš
œ™—K™——K™K™—šžœœœ
™6Kšœ,™2K™K™—š
žœœœœœ
™Nšœ
œ
™Kšœœ™.Kšœœ™ Kšœœ™Kšœœ
™!šœ™Kš
œ™Kš
œ™Kš
œ™Kš
œ™šœ!œœœ,™xšœ™Kš
œ™K™
—šœ™Kš
œ™Kš
œ ™ Kš
œ ™ K™——šœ™Kš
œ™Kš
œ™Kš
œ™Kš
œ™—K™——K™——š
œ
™
šžœœ
œœ˜@Jšœ˜Jš
œ˜J™—šžœœ
œœ˜;J˜Jš
œ˜Jšœœ˜1Jšœœ˜$Jšœœ˜$Jšœ˜J˜J˜—šžœœœ
™3Kšœœ™(K™K™J˜—šžœœœ˜RJš
œ-˜-šœ˜Jšœœ˜Jšœ	œ˜Jšœ
˜Jšœ
˜—J˜J˜—šžœœ
œœ™CKš
œ"™"Kš
œ(™(šœ™šœ	œœ™#Kšœ2œœ™D—šœœ™š
œ	™	Kš
œ-™-Kš
œ&™&—Kšœœ™—šœœ™Kš
œ™Kšœœ™—Kšœœ
™—Kš
œ~™~šœ'™1š
œ™šœ'™1Kš
œ™Kšœœ™——š
œ™šœ'™1Kšœœ™Kšœœ	™Kšœœ™Kšœœ
™——š
œ
™
šœ'™1Kš
œ™Kšœœ™——Kšœœ
™—Kš
œχ
™χ
šœœœœœ™mKšœœ™Kšœœ™Kšœ
™—Kš
œ€
™€
šœX™bKšœœ™Kšœœ	™Kšœœ™"Kšœœ
™—K™K™—šžœœ
œœœœœ™KKšœœ
œœ™šœ™šœ'™1šœœ'™=Kšœœœ™Kšœ
™—Kšœ
™——Kšœœ™K™K™—š
žœœ
œœœ˜7Jš
œ™Jšœœ˜J˜——š
œ™š
žœœ
œœœ
˜>Kšœœ˜Kšœœœ˜Kš
œ9˜9Kš
œ9˜9Kš
œœœœœ
˜<Kšœœœœ˜HK˜K˜—šž	œœ
œœœœœ
˜HKšœœœ˜šœ	œ
œœ
œ
œ˜3Jšœœ˜%Jšœœœ
˜'Jšœœ˜Jšœœ!˜<Jš
œœ
œ
œœ
˜AJšœ œ˜4šœ˜Jšœ
œ!˜,Jšœ
œ"˜-—J˜—K˜K˜—šžœœ
œœœœœ
˜TKšœœœ˜Kš
œ˜Kšœ1œ˜9Kšœœœ œ!˜ZK˜——š
œ	™	šžœœ+œ
˜KKš
œ˜Kš
œ˜Kšœœ
˜Kš
œ˜Kš
œ˜Kš
œ˜Kšœœ
œ˜Kšœœ
œ˜šœ0œ˜8š
œ(˜(Kš
œ0™0—š
œ!˜!Kš
œ,™,—Kš
œ#˜#Kš
œ#˜#K˜—šœ	˜KšœA˜G—šœ%˜/Kšœ?œ	˜KKš
œ˜Kšœœ˜Kšœ
˜—KšœF˜LK˜K˜—šžœœœ™/šœœ™!Kš
œ.™.Kšœœ
œ™K™K™Kšœ
™—KšœE™KK™K™—š
žœœœœœ™6š
™Kšœœœ™Kšœœ
œ™K™K™Kšœ
™—K™K™—šžœœœ
˜1K˜K˜Kš
œ(˜(Kšœ
œ
œ˜!Kšœ ˜&K˜K˜—Kšœ
œœ
˜Kšœœœ
˜šžœœœ˜EKš
œ˜Kš
œ˜Kšœœ˜Kšœœ˜Kšœœ
œ˜!Kšœœœ
œ˜7Kšœœœ
œ˜7šœ
œ˜Kš
œi™iš	œœ
œœ˜)Kšœœ˜Kšœœ˜Kš
œ	˜	šœœœ
œ˜,š
˜Kšœœœœœ
œ
˜*K˜K˜Kšœ
˜—Kšœ
˜K˜—Kšœ
˜—šœœ
œ˜Kš
œ"˜"Kš
œ"˜"K˜—K˜—š
˜šœœ˜K™Δ
Kš
œ˜Kš
œ˜K˜—šœœ˜šœ˜Kš
œ8™8Kšœœ˜Kšœœ˜š
˜Kšœœœ˜šœœ˜šœ˜	šœ˜Kš
œ-˜-Kšœ%œ˜0Kšœ%œ˜0K˜
—šœ˜Kš
œ˜Kš
œ˜K˜——Kšœ˜K˜—K˜K˜Kšœ
˜—K˜
—šœ˜Kš
œ˜K˜Kš
œ%˜%šœœ˜Kš
œ	™	šœ˜Kšœœ˜*Kšœœ˜)Kš
œ˜—K˜—Kš
œ˜K˜K˜——Kšœ
˜—K˜K˜—š
žœœœœœ
˜JKšœœ
œ˜4Kšœœ
œ˜&K˜šœœ˜,Kšœœœ
œœ
œ
˜L—Kš
œœœœœ ˜WK˜K˜—š
žœœ
œ!œœ˜XKš
œ˜šœ
œ
˜Kšœœ˜$Kšœ	œ˜Kšœœ˜&šœ˜
š
˜Kšœœœ ˜CKš
œ+˜+Kšœœ
œ
˜Kš
œ#˜#Kšœ
˜———Kšœ˜K˜K˜—šžœœœ˜6Kšœœ˜Kšœœ˜šœœ
œ˜Kšœœ˜Kš
œ	˜	šœœ
œ˜!š
˜Kšœœœ
œ
˜K˜K˜Kšœ
˜—Kšœ
˜K˜—Kšœ
˜—šœœ
œ˜Kšœ˜!K˜—Kšœ˜K˜K˜—š
ž
œœœœœ˜OKšœœ˜šœ
œ
œ˜Kšœœ!˜:Kš
œW˜Wšœ
œ˜šœœ
œ˜Kšœœ˜!Kšœœ˜Kšœœœœ˜dKšœ
˜—šœ œ#˜QKš
œ˜—K˜—Kšœ˜
K˜—Kšœ˜K˜K˜—šžœœœ˜;Kšœœ
˜Kšœœ
˜Kšœœ
˜
Kšœœ
˜
šœ
œ
˜Kšœœ˜'Kšœœœ˜2Kšœœœ˜2Kšœœœœ"˜BKšœœ"˜3—K˜—M˜—˜J˜—Jšœ
˜J˜—…—Wœ₯•