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.