Support for ceil division

[grod220]

Given the nature of integer math, all division is rounded down. For certain applications, division that rounds up is needed. For example, in a lending market, if a user borrows they are given shares of a debt pool. Give the default rounding down of integer math, it's possible they could borrow say 1_000_000 and only owe 999_999 (rounding down favors individual vs pool).

In the case for Mars, this is being mitigated by writing a trait for Uint128 that looks like this:

use cosmwasm_std::{CheckedMultiplyRatioError, Uint128, Uint256};

pub trait CeilRatio {
    fn multiply_ratio_with_ceil(
        &self,
        numerator: Uint128,
        denominator: Uint128,
    ) -> Result<Uint128, CheckedMultiplyRatioError>;
}

impl CeilRatio for Uint128 {
    /// Using `checked_multiply_ratio()` results in a rounding down due to the nature of integer math.
    /// This function performs the same math, but rounds up. The is particularly useful in ensuring
    /// safety in certain situations (e.g. calculating what an account owes)
    fn multiply_ratio_with_ceil(
        &self,
        numerator: Uint128,
        denominator: Uint128,
    ) -> Result<Uint128, CheckedMultiplyRatioError> {
        // Perform the normal multiply ratio.
        // Converts to Uint256 to reduce likeliness of overflow errors
        let new_numerator = self.full_mul(numerator);
        let denom_256 = Uint256::from(denominator);
        let mut result = new_numerator
            .checked_div(denom_256)
            .map_err(|_| CheckedMultiplyRatioError::DivideByZero)?;

        // Check if there's a remainder with that same division.
        // If so, round up (by adding one).
        if !new_numerator
            .checked_rem(denom_256)
            .map_err(|_| CheckedMultiplyRatioError::DivideByZero)?
            .is_zero()
        {
            result += Uint256::one();
        }

        match result.try_into() {
            Ok(ratio) => Ok(ratio),
            Err(_) => Err(CheckedMultiplyRatioError::Overflow),
        }
    }
}

Is there appetite to include this kind of functionality in the standard library?

[webmaster128]

Thank you @grod220 for the detailed request. This came up multiple times recently and is tracked in #1485. Reading though that issue might be interesting if you are working on this.

A great contribution would be trying to implement

fn mul_ceiled<F: Fraction<Uint128>>(self, rhs: F) -> Self;
fn mul_floored<F: Fraction<Uint128>>(self, rhs: F) -> Self;
fn checked_mul_ceiled<F: Fraction<Uint128>>(self, rhs: F) -> Result<Self, EnumSinceWeHaveTwoDifferentErrorCases>;
fn checked_mul_floored<F: Fraction<Uint128>>(self, rhs: F) -> Result<Self, EnumSinceWeHaveTwoDifferentErrorCases>;

for Uint64, Uint128 and Uint256. Using the Fraction<IntType> here allows the usage of Decimal/Decimal256 but also your own fraction types without having to split them in two arguments. Let's not get blocked by over-generalyzing things as suggested in the other ticket.

[grod220]

Ah! Cool to see folks are thinking about this already. Things are a bit hectic during the holidays, but happy to put some thought here and offer a contribution when I get a chance.