0

Need to calculate (at least approximately):

customerBalance * numerator * collateralBalance / denominator / INITIAL_CUSTOMER_BALANCE / numberOfCustomers

without possibility of overflow. How?

Here:

uint constant INITIAL_CUSTOMER_BALANCE = 1000 * 10**18; // an arbitrarily choosen value

customerBalance is uint256 but it can't be greater than INITIAL_CUSTOMER_BALANCE multiplied by the number of customers (which is limited as one Ethereum transaction (or internal transaction) can register at most one customer).

numerator and numberOfCustomers type is determined by me. It could be for example uint256, uint128, or uint64.

collateralBalance is uint256.

denominator type is determined by me. It could be for example uint256, uint128, or uint64.

The best idea I came to is to somehow use ABDKMath for approximate calculations.

2
  • Can assume numerator <= denominator.
    – porton
    Dec 7 '20 at 6:30
  • Moreover can assume, customerBalance <= INITIAL_CUSTOMER_BALANCE * numberOfCustomers == totalCustomersBalance.
    – porton
    Dec 7 '20 at 6:35
0

With ABDKMath can be done so:

using ABDKMath64x64 for int128;
...
int128 marketShare = ABDKMath64x64.divu(customerBalance, marketTotalBalances[market]);
int128 userShare = ABDKMath64x64.divu(numerator, denominator);
return marketShare.mul(userShare).mulu(collateralBalance);

marketShare and userShare represent reals 0..1.

2
  • Just so you know, your answer includes information not present in the question, such as ABDKMath64x64 and marketTotalBalances. Dec 14 '20 at 10:33
  • In addition to that, the entire solution is subjected to a significant loss of precision, for example, when numerator is much smaller than denominator, or when customerBalance is much smaller than marketTotalBalances[market], etc. Dec 14 '20 at 10:33
0

It sounds like you can easily determine the types of some of the variables in your system, such that the following two expressions can be computed with no risk of overflow:

  • uint256 n = customerBalance * numerator;
  • uint256 d = INITIAL_CUSTOMER_BALANCE * numberOfCustomers * denominator;

And the fact that n <= d (according to your description), guarantees that the value of collateralBalance * n / d is within range (i.e., 256 bits).

Thus, the only risk of overflow is in collateralBalance * n.

We can obtain a good approximation of collateralBalance * n / d by reducing n and d by the same proportion.

And if we reduce them such that n <= MAX_UINT256 / collateralBalance, then we can compute collateralBalance * n with no risk of overflow.

Here is how we can do all of that:

uint256 internal constant INITIAL_CUSTOMER_BALANCE = 1000 * 10**18;
uint256 internal constant MAX_UINT256 = uint256(-1);

function func(
    uint256 collateralBalance,
    uint256 customerBalance,
    uint128 numerator,
    uint128 denominator,
    uint32 numberOfCustomers
) external pure returns (uint256) {
    uint256 n = customerBalance * numerator; // <= (1000 * 10**18) * (2**128 - 1)
    uint256 d = INITIAL_CUSTOMER_BALANCE * numberOfCustomers * denominator; // <= (1000 * 10**18) * (2**32 - 1) * (2**128 - 1)
    (n, d) = reducedRatio(n, d, MAX_UINT256 / collateralBalance);
    return collateralBalance * n / d;
}

function reducedRatio(uint256 n, uint256 d, uint256 max) internal pure returns (uint256, uint256) {
    if (n > max || d > max)
        (n, d) = normalizedRatio(n, d, max);
    if (n != d)
        return (n, d);
    return (1, 1);
}

function normalizedRatio(uint256 a, uint256 b, uint256 scale) internal pure returns (uint256, uint256) {
    if (a <= b)
        return accurateRatio(a, b, scale);
    (uint256 y, uint256 x) = accurateRatio(b, a, scale);
    return (x, y);
}

function accurateRatio(uint256 a, uint256 b, uint256 scale) internal pure returns (uint256, uint256) {
    uint256 maxVal = uint256(-1) / scale;
    if (a > maxVal) {
        uint256 c = a / (maxVal + 1) + 1;
        a /= c; // we can now safely compute `a * scale`
        b /= c;
    }
    if (a != b) {
        uint256 n = a * scale;
        uint256 d = a + b; // can overflow
        if (d >= a) { // no overflow in `a + b`
            uint256 x = roundDiv(n, d); // we can now safely compute `scale - x`
            uint256 y = scale - x;
            return (x, y);
        }
        if (n < b - (b - a) / 2) {
            return (0, scale); // `a * scale < (a + b) / 2 < MAX_UINT256 < a + b`
        }
        return (1, scale - 1); // `(a + b) / 2 < a * scale < MAX_UINT256 < a + b`
    }
    return (scale / 2, scale / 2); // allow reduction to `(1, 1)` in the calling function
}

function roundDiv(uint256 n, uint256 d) internal pure returns (uint256) {
    return n / d + (n % d) / (d - d / 2);
}

Note that function reducedRatio(uint256 n, uint256 d, uint256 max) returns a pair of values, let's denote them n' and d', both <= max.

However, the value of n' / d' can be larger than n / d in some cases, and smaller than n / d in other cases.

Subsequently, the final approximation (i.e., collateralBalance * n' / d') can be on both sides of the true value.

Therefore, depending on your usage of this solution, you may want to apply some assertions on the result.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.