How does Uniswap v3's logarithm library (TickMath.sol) work?

Question

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:

1. First find MSB: first set of assembly code probably does this. Why is r needed?
2. Use MSB to get log2: What does the second set of assembly do after log2 is found?
3. Change of base rule: What is the significance of 255738958999603826347141 in log_2 * 255738958999603826347141?
4. What is the significance of subtracting 3402992956809132418596140100660247210 for tickLow and adding 291339464771989622907027621153398088495 for tickHi?

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 &gt;= 128) r = ratio &gt;&gt; (msb - 127);
    else r = ratio &lt;&lt; (127 - msb);

    int256 log_2 = (int256(msb) - 128) &lt;&lt; 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) &gt;&gt; 128);
    int24 tickHi = int24((log_sqrt10001 + 291339464771989622907027621153398088495) &gt;&gt; 128);

    tick = tickLow == tickHi ? tickLow : getSqrtRatioAtTick(tickHi) &lt;= sqrtPriceX96 ? tickHi : tickLow;
}

Answer 1

1. First find MSB: first set of assembly code probably does this. Why is r needed?

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 the ratio variable, if you only cared about the first assembly block, you could use ratio directly and get a perfectly valid MSB.

2. Use MSB to get log2: What does the second set of assembly do after log2 is found?

With the MSB of a number you get an approximate value of log_2(number) as an integer. For example :

log_2(127) = 6.98868468677 : MSB is 6

log_2(128) = 7 : MSB is 7

log_2(129) = 7.01122725542 : MSB is 7

Basically 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.

3. Change of base rule: What is the significance of 255738958999603826347141 in log_2 * 255738958999603826347141?

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 to sqrt(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.

int256 log_2 = (int256(msb) - 128) << 64;

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 :

int256 log_sqrt10001 = log_2 * 255738958999603826347141; // 128.128 number

is equivalent to :

// Not valid code, just for the example
// With power notation
int256 log_sqrt10001 = log_2 * log(sqrt(1.0001), 2) * 2 ** 64;
// With bit shift notation
 int256 log_sqrt10001 = log_2 * log(sqrt(1.0001), 2) << 64; 

Where log(sqrt(1.0001), 2) changes the base and 2 ** 64 changes the format to Q128.

4. What is the significance of subtracting 3402992956809132418596140100660247210 when finding tickLow?

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 !