How to safely do a power operation with a factional base

I’m trying to convert the following function to solidity:
y = 1,000555^x
(Should be able to calculate from x=0 up to x=10000 without overflowing)

If I do uint256 y = (1000555**x).mul(10**18).div(10**(6*x)) I will get some accurate results but it soon starts overflowing.

If I do uint256 y = ((uint256(1000555).div(10**6))**x)*10**18 it will lose the precision for 1,000555 which will become just a 1 for all x.

I’m using Solidity 0.8.5 and SafeMath.

How should this be done accurately and safely?

Thanks in advance!

@abcoathup would appreciate a lot to have your feedback here! I have also checked this thread before but was not able to apply the same approach it here.

0.02 can be written as 2/100, and 1.000555 can be written as 1000555/1000000 and Function 1 can be rewritten as `2 * 1000555 ** x / 1000000 ** x / 100 + x/35555.

A similar reorganization can be applied to Function 2.

I have tried some permutations of that but I keep getting inaccurate results or overflows - in this case, using the exact function you mentioned I get 0 for all X which is not right.

The solidity function that will give some accurate results for function 1 is:

uint256 result = ((((1000555**_id).mul(2*10**18)).div(10**(6*_id))).div(100)).add((_id.mul(10**18)).div(35555));

But on _id=10 it is already overflowing - does anyone know what changes we need to make so that we can prevent overflowing even if the _id = 10000?

You can try using exponentiation by squaring, dividing by 1000000 on every iteration.

But I don’t know if you can get accurate results like this.

Suppose you have to do 1.000555 ** x.

You represent the number to the left as 1000555.

When you square this number you’re going to get 1001110308025, which is now scaled up by too much so you bring it back down to only 6 decimals dividing by 1000000. You get 1001110 as an approximation of the square.

By squaring repeatedly (see the Wikipedia article above) you get the final result.

I manually tested this in JavaScript for x = 10 and got 1005561, where the real answer seems to be ~1.005564. So it could be a reasonable approximation.

Thanks @frangio , I have tried this before as well, I think you mean I need to bring it down by 6*X and not only 6 right?
The problem with this is that it will overflow using only x = 100, and this should be able to calculate up to x = 10000.
I have also tried (uint256(1000555).div(10**6))**x but this will cause a precision loss on 1,00055 which will become just 1.
Perhaps I’m missing something, if you know the correct way to do it do you mind sharing the solidity function for it please?

This doesn’t overflow but it has bad precision:

function raiseWith6Decimals(uint base, uint16 exp) public pure returns (uint) {
    uint res = 1e6;
    while (exp > 1) {
        if (exp % 2 == 1) {
            res = (res * base) / 1e6;
        }
        base = base ** 2 / 1e6;
        exp /= 2;
    }
    if (exp == 1) {
        res = (res * base) / 1e6;
    }
    return res;
}

I used uint16 for exp to be safe on the number of iterations it will do.

There are probably better approximations that you could write.

Thanks, so I’ve tried this with Solidity 0.8.5 with and SafeMath but I get an error when using uint256 result = (raiseWith6Decimals((uint256(1000555)),_id).mul(raiseWith6Decimals(10,18))).div(raiseWith6Decimals(10,6*_id));
Error:
VM Exception while processing transaction: reverted with panic code 0x12 (Division or modulo division by zero)
Strangely this seems to happen for all values of x besides 0.

I have also tried to use this Bancor formula to calculate the power with fractional base or exp, it is available on the OpenZeppelin repo, but when I try to do
uint256 result = power(2, 1, 2, 1);
result = 680564733841876926926749214863536422875 when it should be 4
Anyone knows why this happens and if this is the proper use of this library?

I have tried so many alternatives and I can’t seem to find a good way to do this - I’d be really grateful if someone could share a working example that accurately represents 1.000555^x without overflowing, from x=0up to 10000.
cc @frangio @abcoathup @maxaero

If I were you, I would spend more time thinking if this can be done off-chain. It sounds like you have a finite number to be calculated, why not calculate them off-chain and store them on-chain in a mapping?

The purpose of this is to use on a bigger function with more power of fractionals, we want to avoid having to table the values as it would end up being expensive to deploy.

Alternatively, we got this power function to work without overflowing:

function power(uint256 base, uint256 exponent, uint256 precision) public pure returns (uint256) {
      if (exponent == 0) {
        return 10**precision;
      } else if (exponent == 1) {
        return base;
      } else {
        uint256 answer = base;
        for (uint256 i = 0; i < exponent; i++) {
          answer = answer * base / (10**precision);
        }
        return answer;
      }
    }

Using Solidity 0.8.4 and Hardhat console.log I can confirm uint256 result = pow(1000555,exponent,6)is able to calculate all the values up to exponent = 10000 with a good level of accuracy, but it throws this error:
Error: Timeout of 20000ms exceeded. For async tests and hooks, ensure "done()" is called; if returning a Promise, ensure it resolves.

If I try to deploy it to Rinkeby I can call the function to get some of the first results, but starting around exponent>2000 it will start returning errored: [object Object]

I tried to look for ways to prevent this timeout from happening but I only find info about changes for tests or deployment config which don’t seem to prevent the issue above.

What changes need to be made to the code so that the timeout is prevented and all the values can be read?
cc @frangio

Doing a for loop on chain is never a good idea. I can see a middle groud by storing a grid of points on chain and doing for loops starting from the closest point. For example, for every 100, you calculate the desired value and get it stored on chain, i.e., f(0), f(100), f(200),… etc. For every other number x, find the closest number and do a for loop to get to x. Let’s say if x is 125, read f(100) first and do a for loop with 25 iterations, if x is 178, then read f(200) and do a for loop with 22 iterations. This can significantly reduce both run-time and storage gas costs.

Thanks, I get what you are saying in this case we really wanted to try to avoid tabling as we would probably need saving a lot of values.

Came across this solution from MakerDAO which works without overflowing or timeouts :slight_smile:
Shoutout to @banteg for pointing it out :tada:
Thanks for your help @maxaero @frangio !

I took a look and still do not think it is a good idea to do 10000 loops to get a value for f(10000), even if it is doen by MakerDao or in Assembly, no matter what, it is not a good idea.

Thanks, I guess it’s not the best way to do it, but perhaps you can elaborate on what is the risk we’re taking on going with this approach so we can compare that with the costs of deploying a tabled approach?
Before calling this function we’ll require that the exponent be between 0 and 10000 which we have confirmed can be safely computed by this function.

The code I shared is not going to do 10000 iterations to calculate f(10000). Exponentiation by squaring is O(log n). The exponent is divided by 2 on every iteration so it results in log2(n) total.

@Ape’s function is indeed doing 10000 iterations, that is very bad and is the reason why it times out.

The error is pretty clear, it says “division by zero”. You’re dividing by raiseWith6Decimals(10,6*_id). The number 10 here is representing 0.000010 and squaring it is already small enough that it doesn’t fit in 6 decimals and is rounded to zero.