Fixed Point Arithmetic support

We’ve received multiple requests for a fixed point math library in OpenZeppelin (e.g. here). For those that are not familir with this concept, it basically boils down to scaling an integer so that a certain (fixed) number of decimals are included, e.g. a value of 100 would represent the number 1.00 if using two decimals, and multiplying 100 by 200 would yield 200 (1.00 * 2.00 = 2.00). This is particularly useful when dealing with decimals on systems that have no floating point support, but allow for large integers (e.g. on 32-bit microcontrollers, and especially on the EVM). You can read more about it here.

Given that fixed-point arithmetic is quite a low-level primitive, I don’t think we should aim for full-fledged support, since the potential for misuse is quite large due to the unfamiliarity of developers with this concept, and the difficulty of handling different number types without getting them mixed up (e.g. regular integers and custom fixed-point representations).

Because of this, and given that the usefulness of fixed-point support in the context of Ethereum usually comes from a need to calculate fractions of values (like in PaymentSplitter here), I propose implementing a simpler, easier-to-use library, where the only supported operation is calculating a percentage of a number, i.e. answering questions such as ‘how much is 75.6% of x?’.

This could be done in a number of ways, e.g. with a function that receives a regular integer and a percentage number (scaled by some factor so that decimals are included - a percentage of 5000 could stand for 50.00%, 5023 for 50.23%, etc.), and returns both the requested fraction and the remainder, which may be useful to avoid leftovers (e.g. if a value is split into three fractions of 33.33%, 0.01% will be left unclaimed) - thanks @frangio for this suggestion!

I’d love to hear everyone’s thoughts about this!

4 Likes

Hey nventuro!

I agree, a general fixed point math library may have it’s risks, although I’d definitely support some sort of library to support fractions! Like you said there are quite a few ways to go about it but I think that’s something the community would really appreciate :slight_smile:

Hey @nventuro,

thanks so much for bringing it up. We see a lot of rounding-related issues. Therefore, it is a timely issue to discuss.

About your proposal:

  1. I am generally in favor of a limited implementation.
  2. Do you know what the status of this is on the solidity level? Described here. A solidity-level solution might be more desirable.
  3. Your implementation seems to do the following:
function percentageOf(uint x, uint basisPoints) internal returns (uint) {
    return x.mul(basisPoints).div(10000);
}

While it is generally a good approach that might be helpful for developers to know, why would you want to use such an approach in the PaymentSplitter? As you said there might easily be a 0.01% remainder which is considerably larger than the remainder that the current implementation of PaymentSplitter has.

Thanks.

1 Like

Hi @nventuro,

I work for CementDAO and we happen to have implemented a fixed point math library for solidity, with support for basic arithmetic including multiplication and division, as well as logarithms. We have implemented it with full protection for overflows, found the numerical limits for safe operation, and tested all functions extensively (probably more than 100% coverage).

We are planning to release this library as open source when we release CementDAO, but if you would be interested in having a look we would be happy to facilitate that. It would be awesome if we could have your feedback and advice on how to make the library more useful for the community.

Thanks!

4 Likes

That’s cool @albertocanada!

This sounds interesting. Would you mind sharing a few more details?

To be clear, PaymentSplitter doesn’t have a remainder that results from numerical error. The only remainder is that which cannot be split between the shareholders. There’s very simple scenarios where this happens: if you and me are splitting payments 50-50, and we receive 3 wei, there is 1 wei that we can’t split, so it will stay in the contract. It’s always very few wei that will remain. Even then, it’s possible to “top up” the contract balance so that it is fully emptied.

This is how percentages should be always done IMO, and we should try to give tools for people to replicate that in their contracts. I’m not sure how much this approach can be generalized, though.

Because of that, my main interest in this thread is collecting examples where percentages and/or fixed point were needed, to evaluate how different possible libraries would help.

1 Like

With each arithmetical operation we made sure it throws on overflow.

Additionally to that we calculated what are the bounds within which an arithmetical operation won’t overflow. For example we know that add will overflow (and throw) if the result is greater than 2**255-1 (we are using int256). From this we can assert that all add operations where both operands are smaller than (2**255-1)/2 will never throw.

We implemented those limits because sometimes you might not want to wait to see if an operation throws and instead stop the user at the frontend when it’s going towards a risky situation so that you have a more predictable experience.

Thanks. I agree. Sorry for my misunderstandable post. PaymentSharer is indeed a good example.

The medium post below might be a good example. We have seen a number of implementations based on this post:

I haven’t been following development closely, but seriously doubt this is a pressing concern for them, considering they’re working on much more generally useful features.

This would be useful for many projects yes. Rather than using basis points (4 decimal places) using 18 decimal places seems to be the standard for many protocols including Maker and dYdX

2 Likes

There are a number of approaches with regards to how many decimal places. If you are going to do arithmetic with currencies then using as many decimal points as your fractional monetary unit makes sense. That would be 2 decimals for dollars, 18 decimals for bitcoin.

If you are going to do more complex arithmetic (we had to do logarithm curves) then the more decimals you use the more precision you get for iterative methods (log, exp, sqrt). Our initial setup was for 36 decimals to get a really good approximation of the curves.

We only included limited support for operating on fixed point numbers of different decimals, because we didn’t need more, but it would be relatively easy to pack an uint8 denoting the decimals used into a Struct that represents the fixed point value. That way a fixed point library would be flexible enough for applications needing any number of decimals.

2 Likes

We just released Solidity library for signed 64.64-bit fixed point math, i.e. for binary rather than decimal fixed point: https://github.com/abdk-consulting/abdk-libraries-solidity
It has basic arithmetic, exponentiation, logarithm, square root, etc.

Hey,
My team in LimeChain had to implement sqrt/power/ln functions in order to run the Bonding Curve concept.
The problem with these functions in solidity is actually the missing double type (The big pain :frowning: ) That is why we gave a chance to Vyper.

And here are the results:

SQRT Function:

  1. Vyper already has an integrated sqrt function thanks to @Perseverance(Github name) -> returns up to 10 digits fraction
  2. If you want to have more accurate result in terms of fraction a.k.a more than 10 digits accuracy, you can check: https://github.com/LimeChain/bonding_mathematics/blob/master/contracts/Math/SQRT_HFP.py

Example:
sqrt(2) => 14142135623
sqrt_hfp(2, 18) -> 1414213562373095048

LN Function: (Natural logarithm)
You can calculate ln of a number with high precision (up to 10 digits fraction)
The code:

POWER Function:
You can power a number with high precision (up to 10 digits fraction)

The limits:
Let’s say we have x^y where x is the Number and y is the Exponent

  1. The biggest Number is 9999999999999.9999999999 with an approximation of 9999999970066.393832446 (the real result is: 9999999970066.393835878 )

  2. 9999999999999.9999999999 ^ 0.9999999999 = 9999999970066.393832446 (the real result is: 9999999970066.393835878 )

  3. Exponent should be in range: [ 0 < Exponent < 1 ]

  4. Gas cost => approximately 367806 gas = 0.30527 USD

Hint: If you want to power a number with exponent > 1 you can do:

2.13 ^ 9.82 = 2.13 ^ 9 * exp(2.13 ^ 0.82)

Keep in mind that 2.13 ^ 9 gives inaccurate result due to Vyper decimal size limit (Underflow)

The code:

And finally… :slight_smile: here is a code snippet of how to run vyper functions from solidity contract:

contract TestingVyperLN {
    
    uint256 public result;

    function calcLN(address vyperMath, uint256 number) public {
        
        address vyperContract = vyperMath;
        
        (bool success, bytes  memory data) = vyperContract.call(abi.encodeWithSignature("ln(uin256)", number));
        require(success);
        
        // Convertion from bytes to uint
        uint lnResult;
        assembly {
            lnResult := mload(add(data, add(0x20, 0)))
        }
        
        result = lnResult;
    }
}

Library I mentioned in my previous comment is able to calculate sqrt, x^y, and ln x in Solidity with 64-bit precision (about 18 decimals) and uses less gas:

sqrt: less then 2K gas
2^x: less than 2K gas
log2 x: about 10K gas
ln x: about 10K gas

x^y is calculated as 2^(y * log2 x) and thus consumes about 12K gas.