In the EVM, the
MUL opcode costs 5 gas and is used to perform multiplication. For example, the arithmetic behind computing 20 * 30 = 600 should cost 5 gas.
EXP opcode is used to perform exponentiation, and its gas cost is variable and determined by a formula: 10 gas plus 50 times the number of bytes in the exponent. For example, the arithmetic of computing 10^27 should cost 10 + 50 * 1 = 60 gas, while 10^400 would cost 10 + 50 * 2 = 160 gas, since it takes one byte to represent 27<256 = 2^8 and two bytes to represent 400<65536=2^16.
So we are basically pricing ~10 multiplication operations for a byte.
We can of course implement our own exponentation algorithm in Solidity/Yul. A common instance used in many DeFi projects being the "exponentiation by squaring" method which computes
If n is even, then
x^n = (x^2)^(n/2).
If n is odd, then x^n = x * x^(n-1), but then n-1 is even and applying the equation above gives:
x^n = x * (x^2)^((n-1) / 2).
This calculates x^n in O(log n) instead of O(n) multiplications for the naive repeated multiplication. For example, this is what is in DS-Math library
rpow function implements. This method would clearly be more efficient for small numbers, and numbers whose binary representation is "very sparse" but not in general.
My question is:
- Does anybody know what is the cost model the Ethereum Foundation based this on? Is there a public study in numerical analysis that ~10 multiplication is the right number?
- Is there a good heuristic for when and how to use the
EXPopcode in terms of gas cost?