Function compute_max_integer_quotient

pub fn compute_max_integer_quotient<F: FixedPointOperand + One>(
    multiplier: FixedU128,
    product: F,
) -> F

Determine the maximal integer n so that multiplier.saturating_mul_int(n) <= product

See the tests compute_max_quotient_works below for an example why simple division does not give the correct result. This level of pedantry is required because otherwise we observed actual cases where limits where calculated incorrectly and the transaction ran out of gas although it used the correct gas estimate.

FixedU128 wraps a 128 bit unsigned integer self.0 and it is interpreted to represent the real number self.0 / FixedU128::DIV, where FixedU128::DIV is 1_000_000_000_000_000_000.

Given an integer n, the operation multiplier.saturating_mul_int(n) is defined as div_round_down(multiplier.0 * n, FixedU128::DIV) where div_round_down is integer division where the result is rounded down.

To determine the maximal integer n so that multiplier.saturating_mul_int(n) <= product is therefore equivalent to determining the maximal n such that div_round_down(multiplier.0 * n, FixedU128::DIV) <= product This is equivalent to the condition multiplier.0 * n <= product * FixedU128::DIV + FixedU128::DIV - 1 This is equivalent to multiplier.0 * n < (product + 1) * FixedU128::DIV This is equivalent to n < div_round_up((product + 1) * FixedU128::DIV, multiplier.0) where div_round_up is integer division where the result is rounded up. Since we look for a maximal n with this condition, the result is n = div_round_up((product + 1) * FixedU128::DIV, multiplier.0) - 1.

We can take advantage of the function FixedU128::checked_rounding_div, which, given two fixed point numbers a and b, just computes a.0 * FixedU128::DIV / b.0. It also allows to specify the rounding mode SignedRounding::Major, which means that the result of the division is rounded up.