diff options
author | Amir Bandeali <abandeali1@gmail.com> | 2018-08-25 08:29:09 +0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2018-08-25 08:29:09 +0800 |
commit | 74ce893f520db6ae4617432975b5c9321ff5b89b (patch) | |
tree | 45853fe1c16066290834ee5827b3c269a9fb7734 /packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol | |
parent | 94e01be9ed5bfe2d0ace4cd0562fced889b34108 (diff) | |
parent | cc1fac9bbee2656bdb327490de42922abfc5125a (diff) | |
download | dexon-sol-tools-74ce893f520db6ae4617432975b5c9321ff5b89b.tar dexon-sol-tools-74ce893f520db6ae4617432975b5c9321ff5b89b.tar.gz dexon-sol-tools-74ce893f520db6ae4617432975b5c9321ff5b89b.tar.bz2 dexon-sol-tools-74ce893f520db6ae4617432975b5c9321ff5b89b.tar.lz dexon-sol-tools-74ce893f520db6ae4617432975b5c9321ff5b89b.tar.xz dexon-sol-tools-74ce893f520db6ae4617432975b5c9321ff5b89b.tar.zst dexon-sol-tools-74ce893f520db6ae4617432975b5c9321ff5b89b.zip |
Merge pull request #1003 from 0xProject/feature/contracts/roundup
[contracts] Add getPartialAmountCeil and isRoundingErrorCeil
Diffstat (limited to 'packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol')
-rw-r--r-- | packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol | 122 |
1 files changed, 108 insertions, 14 deletions
diff --git a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol index fa09da6ac..0e0fba5d2 100644 --- a/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol +++ b/packages/contracts/src/2.0.0/protocol/Exchange/libs/LibMath.sol @@ -25,12 +25,12 @@ contract LibMath is SafeMath { - /// @dev Calculates partial value given a numerator and denominator. + /// @dev Calculates partial value given a numerator and denominator rounded down. /// @param numerator Numerator. /// @param denominator Denominator. /// @param target Value to calculate partial of. - /// @return Partial value of target. - function getPartialAmount( + /// @return Partial value of target rounded down. + function getPartialAmountFloor( uint256 numerator, uint256 denominator, uint256 target @@ -39,19 +39,56 @@ contract LibMath is pure returns (uint256 partialAmount) { + require( + denominator > 0, + "DIVISION_BY_ZERO" + ); + partialAmount = safeDiv( safeMul(numerator, target), denominator ); return partialAmount; } - - /// @dev Checks if rounding error > 0.1%. + + /// @dev Calculates partial value given a numerator and denominator rounded down. + /// @param numerator Numerator. + /// @param denominator Denominator. + /// @param target Value to calculate partial of. + /// @return Partial value of target rounded up. + function getPartialAmountCeil( + uint256 numerator, + uint256 denominator, + uint256 target + ) + internal + pure + returns (uint256 partialAmount) + { + require( + denominator > 0, + "DIVISION_BY_ZERO" + ); + + // safeDiv computes `floor(a / b)`. We use the identity (a, b integer): + // ceil(a / b) = floor((a + b - 1) / b) + // To implement `ceil(a / b)` using safeDiv. + partialAmount = safeDiv( + safeAdd( + safeMul(numerator, target), + safeSub(denominator, 1) + ), + denominator + ); + return partialAmount; + } + + /// @dev Checks if rounding error >= 0.1% when rounding down. /// @param numerator Numerator. /// @param denominator Denominator. /// @param target Value to multiply with numerator/denominator. /// @return Rounding error is present. - function isRoundingError( + function isRoundingErrorFloor( uint256 numerator, uint256 denominator, uint256 target @@ -60,16 +97,73 @@ contract LibMath is pure returns (bool isError) { - uint256 remainder = mulmod(target, numerator, denominator); - if (remainder == 0) { - return false; // No rounding error. + require( + denominator > 0, + "DIVISION_BY_ZERO" + ); + + // The absolute rounding error is the difference between the rounded + // value and the ideal value. The relative rounding error is the + // absolute rounding error divided by the absolute value of the + // ideal value. This is undefined when the ideal value is zero. + // + // The ideal value is `numerator * target / denominator`. + // Let's call `numerator * target % denominator` the remainder. + // The absolute error is `remainder / denominator`. + // + // When the ideal value is zero, we require the absolute error to + // be zero. Fortunately, this is always the case. The ideal value is + // zero iff `numerator == 0` and/or `target == 0`. In this case the + // remainder and absolute error are also zero. + if (target == 0 || numerator == 0) { + return false; } - - uint256 errPercentageTimes1000000 = safeDiv( - safeMul(remainder, 1000000), - safeMul(numerator, target) + + // Otherwise, we want the relative rounding error to be strictly + // less than 0.1%. + // The relative error is `remainder / (numerator * target)`. + // We want the relative error less than 1 / 1000: + // remainder / (numerator * denominator) < 1 / 1000 + // or equivalently: + // 1000 * remainder < numerator * target + // so we have a rounding error iff: + // 1000 * remainder >= numerator * target + uint256 remainder = mulmod(target, numerator, denominator); + isError = safeMul(1000, remainder) >= safeMul(numerator, target); + return isError; + } + + /// @dev Checks if rounding error >= 0.1% when rounding up. + /// @param numerator Numerator. + /// @param denominator Denominator. + /// @param target Value to multiply with numerator/denominator. + /// @return Rounding error is present. + function isRoundingErrorCeil( + uint256 numerator, + uint256 denominator, + uint256 target + ) + internal + pure + returns (bool isError) + { + require( + denominator > 0, + "DIVISION_BY_ZERO" ); - isError = errPercentageTimes1000000 > 1000; + + // See the comments in `isRoundingError`. + if (target == 0 || numerator == 0) { + // When either is zero, the ideal value and rounded value are zero + // and there is no rounding error. (Although the relative error + // is undefined.) + return false; + } + // Compute remainder as before + uint256 remainder = mulmod(target, numerator, denominator); + // TODO: safeMod + remainder = safeSub(denominator, remainder) % denominator; + isError = safeMul(1000, remainder) >= safeMul(numerator, target); return isError; } } |