1

I am currently trying to figure out a concrete way to perform fixed point division on two 128.128 uint256 numbers. This seems like a fairly straightforward thing, but haven't been able to code a solution up.

For two 64.64 fixed point numbers the following works just fine.

function div64x64 (uint128 x, uint128 y) internal pure returns (uint128) {
    unchecked {
        require (y != 0);
    
        uint256 answer = (uint256 (x) << 64) / y;

        require (answer <= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF);
        return uint128 (answer);
    }
}

But the same logic does not hold for uint256 128.128 fixed point numbers since you cannot cast x into a larger uint type to left shift x. This is my sad attempt at solving this for 128.128 which doesn't include the correct decimals in the output, but my attempt does include the correct values left of the decimal.

    function div128x128 (uint256 x, uint256 y) internal pure returns (uint256) {
    unchecked {
        require (y != 0);

        uint256 xInt = x>>128;
        uint256 xDecimal = x<<128;
        uint256 yInt = y>>128;
        uint256 yDecimal = y<<128;

        uint256 hi = ((uint256(xInt) << 64)/yInt)<<64;
        uint256 lo = ((uint256(xDecimal)<<64)/yDecimal);
        
        require (hi+lo <= MAX_128x128);
        return hi+lo;
    }
}

Does anyone know the best way to accomplish this, or even just a conceptual explanation would be super appreciated. Thanks in advance!

4
  • Hi! I can't test but I get the formulas hi = (xInt << 128) / yInt and lo = xDecimal / y, but they won't work for yInt = 0.
    – Ismael
    Commented May 21, 2022 at 19:33
  • @Ismael are you keeping xDecimal in the form it is above in my code. I tested this solution, looks like not getting quite correct out but seems suspiciously close. 12.525/9.25 yields 473023146089196455034305347672812970287*2**-128=1.39009009009 expected: 1.354054054054054. Not exactly sure what the issue is here, but it does seem like the methodology is close to correct. Also for our purposes yInt can be assumed to never be 0.
    – 0xOsiris
    Commented May 21, 2022 at 23:02
  • In the above example we have lo=0.0567567567567568 & hi=1.3333333333333333
    – 0xOsiris
    Commented May 21, 2022 at 23:25
  • I'm using the same names. The exact formula would be hi = (xInt << 256) / y, but it obviously won't work. Another approximation could be hi = xInt * (one / y), where one = MAX_UINT256. To get the best approximation I'd simulate with the approximate ranges for x and y the one that give the lowest relative error.
    – Ismael
    Commented May 21, 2022 at 23:55

1 Answer 1

1

Okay, so I'll post the solution here for the next guy. Shoutout to the comments for the helpful hints. The key here is one of the more obvious facts that you can break up a fraction with a common denominator into two additive parts. For example 12.525/9.5= (12/9.5)+(.525/9.5) with this in mind we have a way to break up our numbers into 2 uint256 numbers and just concatenate them with some fancy shifting.

    function div128x128 (uint256 x, uint256 y) internal pure returns (uint256) {
        unchecked {
            //Require denominator != 0
            require (y != 0);
            // xDec = x & 2**128-1 i.e 128 precision 128 bits of padding on the left
            uint256 xDec = x & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF;
             //xInt x *2**-128 i.e. 128 precision 128 bits of padding on the right
            uint256 xInt = x >> 128;
            //hi = xInt*2**256-1 /y ==> leave a full uint256 of bits to store the integer representation of the fractional decimal with 128.128 precision
            uint256 hi = xInt*(MAX_128x128/y);
            //xDec*2**256-1 /y ==> leave full uint256 of bits to store the integer representation of fractional decimal with 128.128 precision, right shift 128 bits since output should be the right 128 bits of precision on the output
            uint256 lo = (xDec*(MAX_128x128/y))>>128;
            /*Example: 12.525/9.5 := 12/9.5 + .525/9.5<-- legal to break up a fraction into additive pieces with common deniminator in the example above just padding to fit 128.128 output in a uint256
*/
            require (hi+lo <= MAX_128x128);
            return hi+lo;
        }
    }

This is one solution, that seems to be working so long as the require criterion are met. There are almost undoubtedly optimization improvements to be made. But I have tested this on some real data, and it seems to be accurate to 128.128 precision.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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