Statement. For every FeeFrac f (a pair of integers (fee(f),size(f))) and every integer t (the "at size"), assuming
size(f)>0andt≥0,
we have
evaluateFeeUp(f,t)=⌈size(f)fee(f)⋅t⌉,
where the product fee(f)⋅t is formed in Z, then divided exactly in Q by size(f), and the ceiling is taken.
Binders and edge cases.fee(f) is an arbitrary integer (negative, zero, or ≥233 all allowed), so all three branches of evaluateFee are in scope (here with ρ false: the ceilDiv branch for 0≤fee(f)<233 and the div branch otherwise). The hypothesis t≥0 carries a name beginning with an underscore, which only signals that the name is not referred to; it is nevertheless a hypothesis of the theorem, so the statement says nothing about negative t. t=0 is allowed. No word-size bounds are imposed on fee, size or t.
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.
mul.mul(a,b)=a⋅b, the exact product of two integers.
div. For integers n,d and a boolean ρ ("round down"), with q=tdiv(n,d) and r=tmod(n,d) (truncated division):
div(n,d,ρ)=q+[r>0]−[r=0 and ρ].
Case by case: if r=0 the result is q; if r>0 it is q when ρ is true and q+1 when ρ is false; if r<0 it is q−1 when ρ is true and q when ρ is false. The definition places no condition on d: for d=0 it gives q=0, r=n, hence [n>0]−[n=0 and ρ]; for d<0 the remainder still carries the sign of n.
ceilDiv. For integers n,d, with default (Euclidean) integer division:
ceilDiv(n,d)=n/d+[nmodd=0].
The definition is stated for all integers (not only nonnegative ones); for d=0 it gives [n=0].
evaluateFee, evaluateFeeDown, evaluateFeeUp. For a FeeFrac X, an integer t ("at size") and a boolean ρ:
evaluateFee(X,t,ρ)=⎩⎨⎧(fee(X)⋅t)/size(X)ceilDiv(fee(X)⋅t,size(X))div(mul(fee(X),t),size(X),ρ)if 0≤fee(X)<233 and ρ is true,if 0≤fee(X)<233 and ρ is false,otherwise (fee(X)<0 or fee(X)≥233),
where 233=8589934592, the "/" in the first line is the default (Euclidean) integer division, and mul(a,b)=ab. Then evaluateFeeDown(X,t)=evaluateFee(X,t,true) and evaluateFeeUp(X,t)=evaluateFee(X,t,false). The definition itself imposes no condition on size(X) or t.
Confirmed by the moderator at approval.