Statement. Let a and b be arbitrary FeeFracs (pairs of integers (fee,size)) and assume
size(a)>0andsize(b)>0.
Then the integer cross-multiplication comparison equals the comparison of the rational feerates:
byRatioCmp(a,b)=compare(ratio(a),ratio(b)),
i.e. the three-way comparison (lt/eq/gt) of the integers fee(a)⋅size(b) and fee(b)⋅size(a) gives the same outcome as the three-way comparison of the rationals fee(a)/size(a) and fee(b)/size(b).
Binders and edge cases. The fees of a and b are unrestricted integers (zero or negative allowed); only the sizes are required to be strictly positive, so the rational divisions never divide by zero. No upper bounds on any of the four integers are assumed. The statement is an equality of three-valued outcomes, so it covers all three cases (<, =, >) at once.
Definitions used, unfolded
Division conventions. Three kinds of division occur.
Default integer divisionn/d with remainder nmodd (Euclidean convention). For d>0: n/d=⌊n/d⌋ and nmodd=n−d⌊n/d⌋∈[0,d), also for negative n (e.g. −7/2=−4, −7mod2=1). For d<0: n/d=−⌊n/∣d∣⌋ and nmodd∈[0,∣d∣). For d=0: n/0=0 and nmod0=n.
Truncated divisiontdiv(n,d) with remainder tmod(n,d)=n−d⋅tdiv(n,d): the quotient is rounded toward zero, so the remainder is 0 or has the sign of n, with ∣tmod(n,d)∣<∣d∣ (e.g. tdiv(−7,2)=−3, tmod(−7,2)=−1). For d=0: tdiv(n,0)=0, tmod(n,0)=n.
Rational division in Q, with the convention q/0=0. For q∈Q, ⌊q⌋ is the greatest integer ≤q and ⌈q⌉ the least integer ≥q.
Below, [P] denotes 1 if the condition P holds and 0 otherwise.
FeeFrac. A FeeFrac is a pair X=(fee(X),size(X)) of two arbitrary integers. Nothing constrains them: either component may be zero or negative, and no machine-word bounds are imposed. Addition and subtraction are componentwise,
X±Y=(fee(X)±fee(Y),size(X)±size(Y)),
and the zero FeeFrac is (0,0). A chunk list is a finite list c=[c1,…,cn] of FeeFracs; the empty list (n=0) is allowed.
byRatioCmp. For FeeFracs X,Y, byRatioCmp(X,Y) is the three-way comparison of the two integers fee(X)⋅size(Y) and fee(Y)⋅size(X):
byRatioCmp(X,Y)=⎩⎨⎧lteqgtif fee(X)size(Y)<fee(Y)size(X),if they are equal,if fee(X)size(Y)>fee(Y)size(X).
No sign condition on the sizes is part of the definition. In particular, byRatioCmp(X,(0,1)) is the comparison of fee(X) with 0, independent of size(X).
ratio.ratio(X)=fee(X)/size(X)∈Q (rational division; equals 0 when size(X)=0). For rationals p,q, compare(p,q) is lt, eq or gt according as p<q, p=q or p>q.
Confirmed by the moderator at approval.