乘法/除法沒有溢出

需要計算（至少近似）：

customerBalance * numerator * collateralBalance / denominator / INITIAL_CUSTOMER_BALANCE / numberOfCustomers

沒有溢出的可能性。如何？

這裡：

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

customerBalance是uint256，但它不能大於INITIAL_CUSTOMER_BALANCE乘以客戶數量（這是有限的，因為一個乙太坊交易（或內部交易）最多可以註冊一個客戶）。

numerator類型numberOfCustomers由我決定。uint256例如，它可以是uint128、 或uint64。

collateralBalance是uint256。

denominator類型由我決定。uint256例如，它可以是uint128、 或uint64。

我想到的最好的主意是以某種方式ABDKMath用於近似計算。

可以ABDKMath這樣做：

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

marketShare並userShare代表實數0..1。

聽起來您可以輕鬆確定係統中某些變數的類型，從而可以計算以下兩個表達式而沒有溢出風險：

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

事實上n <= d（根據您的描述），保證 的值collateralBalance * n / d在範圍內（即 256 位）。

因此，溢出的唯一風險在於collateralBalance * n.

collateralBalance * n / d我們可以通過減少n和d相同的比例來獲得一個很好的近似值。

如果我們將它們減少到n <= MAX_UINT256 / collateralBalance，那麼我們可以collateralBalance * n在沒有溢出風險的情況下進行計算。

以下是我們如何做到這一切：

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);
}

請注意，它function reducedRatio(uint256 n, uint256 d, uint256 max)返回一對值，我們將它們表示為n'和d'，兩者都<= max。

但是，在某些情況下， 的值n' / d'可能會更大n / d，而在其他情況下，則可能會更小n / d。

隨後，最終的近似值（即collateralBalance * n' / d'）可以在真值的兩側。

因此，根據您對該解決方案的使用情況，您可能希望對結果應用一些斷言。

引用自：https://ethereum.stackexchange.com/questions/90876