I want to calculate logarithm of a non-standard base at low gas cost. First thought is to use change of base rule with log2()
fixed point methods mentioned in this thread.
However Uniswap v3 core has custom code for log to the base √1.0001. It has assembly level optimizations which I'm trying to understand. However implementation is opaque and not well documented.
As per my understanding:
- First find MSB: first set of assembly code probably does this. Why is
r
needed? - Use MSB to get log2: What does the second set of assembly do after
log2
is found? - Change of base rule: What is the significance of
255738958999603826347141
inlog_2 * 255738958999603826347141
? - What is the significance of subtracting
3402992956809132418596140100660247210
fortickLow
and adding291339464771989622907027621153398088495
fortickHi
?
TickMath.sol
/// @notice Calculates the greatest tick value such that getRatioAtTick(tick) <= ratio
/// @dev Throws in case sqrtPriceX96 < MIN_SQRT_RATIO, as MIN_SQRT_RATIO is the lowest value getRatioAtTick may
/// ever return.
/// @param sqrtPriceX96 The sqrt ratio for which to compute the tick as a Q64.96
/// @return tick The greatest tick for which the ratio is less than or equal to the input ratio
function getTickAtSqrtRatio(uint160 sqrtPriceX96) internal pure returns (int24 tick) {
// second inequality must be < because the price can never reach the price at the max tick
require(sqrtPriceX96 >= MIN_SQRT_RATIO && sqrtPriceX96 < MAX_SQRT_RATIO, 'R');
uint256 ratio = uint256(sqrtPriceX96) << 32;
uint256 r = ratio;
uint256 msb = 0;
assembly {
let f := shl(7, gt(r, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF))
msb := or(msb, f)
r := shr(f, r)
}
assembly {
let f := shl(6, gt(r, 0xFFFFFFFFFFFFFFFF))
msb := or(msb, f)
r := shr(f, r)
}
assembly {
let f := shl(5, gt(r, 0xFFFFFFFF))
msb := or(msb, f)
r := shr(f, r)
}
assembly {
let f := shl(4, gt(r, 0xFFFF))
msb := or(msb, f)
r := shr(f, r)
}
assembly {
let f := shl(3, gt(r, 0xFF))
msb := or(msb, f)
r := shr(f, r)
}
assembly {
let f := shl(2, gt(r, 0xF))
msb := or(msb, f)
r := shr(f, r)
}
assembly {
let f := shl(1, gt(r, 0x3))
msb := or(msb, f)
r := shr(f, r)
}
assembly {
let f := gt(r, 0x1)
msb := or(msb, f)
}
if (msb >= 128) r = ratio >> (msb - 127);
else r = ratio << (127 - msb);
int256 log_2 = (int256(msb) - 128) << 64;
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(63, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(62, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(61, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(60, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(59, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(58, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(57, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(56, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(55, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(54, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(53, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(52, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(51, f))
r := shr(f, r)
}
assembly {
r := shr(127, mul(r, r))
let f := shr(128, r)
log_2 := or(log_2, shl(50, f))
}
int256 log_sqrt10001 = log_2 * 255738958999603826347141; // 128.128 number
int24 tickLow = int24((log_sqrt10001 - 3402992956809132418596140100660247210) >> 128);
int24 tickHi = int24((log_sqrt10001 + 291339464771989622907027621153398088495) >> 128);
tick = tickLow == tickHi ? tickLow : getSqrtRatioAtTick(tickHi) <= sqrtPriceX96 ? tickHi : tickLow;
}
Best Answer
You are correct, this part of assembly is looking for the MSB that will serve as an initial integer approximation for the log 2 variable. the
r
variable is needed as a temporary variable in order to preserve theratio
variable, if you only cared about the first assembly block, you could useratio
directly and get a perfectly valid MSB.With the MSB of a
number
you get an approximate value oflog_2(number)
as an integer. For example :log_2(127) = 6.98868468677
: MSB is 6log_2(128) = 7
: MSB is 7log_2(129) = 7.01122725542
: MSB is 7Basically with MSB = x you know that
log_2(value)
is< MSB + 1
and>= MSB
but you don't know exactly where it is in between those values.When dealing with financial data, you can understand why computing the decimal part is absolutely mandatory. This is what this second block of assembly does, refining the integer
log_2
approximation to account for the decimal part up to 14 bits of precision.Those magic numbers are always just a mathematical expression that ends up being constant. In this case this is a change of base from
2
tosqrt(1.0001)
.log_(sqrt(1.0001)(number) = log_2(number) / log_2(sqrt(1.0001))
you can rewrite
log_2(sqrt(1.0001))
as :log_(sqrt(1.0001)(sqrt(1.0001) / log_(sqrt(1.0001)(2)
which translates to :1 / log_(sqrt(1.0001)(2)
so :
log_(sqrt(1.0001)(number) = log_2(number) * log_(sqrt(1.0001)(2)
Now
log_(sqrt(1.0001)(2))
is a constant : 13863.63...And a previous line transformed the MSB to a Q64 fixed point number.
We now want the approximation as a Q128 fixed point number as per the comment. So we need to left shift by 64 or multiply by
2 ** 64
, those are equivalent.it turns out that
log_(sqrt(1.0001))(2) * 2 ** 64
equals : 255738958999603826347141 (with the correct precision)(I've had trouble to come up to the exact value but I supposed it's because of precision / rounding errors, if you do the reverse path, it's fine)
so :
is equivalent to :
Where
log(sqrt(1.0001), 2)
changes the base and2 ** 64
changes the format to Q128.I must admit that I did not clearly understand that part in the code so I won't be able to explain it.. I'll edit the answer if I find out !