128.128 Unsigned fixed point Division in Solidity-CodePudding

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 of how to do it would be super appreciated. Thanks in advance!

CodePudding user response：

Okay, so I'll post the solution here for the next guy. 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.