# Multiply/divide without an overflow

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.

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

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`.

• 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

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.