Efficient, safe pow using EXP opcode

Question

I recently stumbled across ds-math's rpow() being a O(lg n) safe implementation of exponentiation.

Such a function is ultimately created because the EVM EXP opcode is unsafe wrt. overflows. The strategy is that since we're multiplying, we'll detect any overflows incrementally using a safe rmul(). (The "r" part supposedly refers to how it rounds.)

But I wonder why it isn't the case with EXP that you can create some invariant that asserts no overflows.

I thought that one might simply check that either the exponent is 0, or the result is greater-than-or-equal to the base. But what if the exponent is so great that it wraps around the word size and lands above the base, or wraps around the word size twice and lands above the base?

In another vein, I don't think you can easily do any modulo checks, since overflows conform to modular semantics.

So my question is: Has anyone tried to perform a safe exponentiation using EXP or ruled out the possibility?

The opcode is only 10 gas, after all.

Answer 1

You can get a good estimation as to whether or not it is going to overflow, by:

1. Counting the number of bits in the base
2. Multiplying it by the exponent
3. Checking whether or not the result is larger than 256

For example:

function floorLog2(uint256 _n) internal pure returns (uint8) {
    uint8 res = 0;

    if (_n < 256) {
        // At most 8 iterations
        while (_n > 1) {
            _n >>= 1;
            res += 1;
        }
    }
    else {
        // Exactly 8 iterations
        for (uint8 s = 128; s > 0; s >>= 1) {
            if (_n >= (uint256(1) << s)) {
                _n >>= s;
                res |= s;
            }
        }
    }

    return res;
}

function numOfBits(uint256 _n) internal pure returns (uint256) {
    return uint256(floorLog2(_n)) + 1;
}

function isPowSafe(uint256 _base, uint256 _exp) internal pure returns (bool) {
    return _base < 2 || numOfBits(_base) * _exp <= 256;
}

Of course, you'll have to verify that there is no overflow in the multiplication by the exponent.

Note that if isPowSafe(x, y) returns true, then x ** y will not overflow.

However, if isPowSafe(x, y) returns false, then x ** y will not necessarily overflow.