How does Uniswap v3-core derive the look up table used in TickMath?

Question

Background

In TickMath.sol of v3-core codebase, getSqrtRatioAtTick(int24 tick) implements \sqrt{1.0001}^n with binary fixed point arithmetics in Q128 and down casts to Q96.

With a lookup table of Q128 entries \sqrt{1.0001^-1}^{0b1}, \sqrt{1.0001^-1}^{0b10}, ..., the input tick is split into several terms multiplied together. The negative exponent is chosen to avoid overflow and the reciprocal is taken in the end for positive inputs.

My Question

I have trouble reproducing the exact constants of \sqrt{1/1.0001}^n defined in the contract. What I've tried is to precompute in IEEE-754 doubles and convert them back to Q128 in python, as in:

>>> int(1/math.sqrt(1.0001) * 2**128)
340265354078545014477014422800776036352
>>> 0xfffcb933bd6fad37aa2d162d1a594001
340265354078544963557816517032075149313

As you can see the result deviates the hexadecimal value 0xfffcb933bd6fad37aa2d162d1a594001 provided in TickMath.sol for n=1. My guess is it's due to precision loss and there must be some numerical methods to derive those exact values.

Hope to get some guidances here. Thank you.

Answer 1

In TickMath.sol you can see that positive ticks are later used to divide type(uint256).max:

if (tick > 0) ratio = type(uint256).max / ratio;

So to get this value 0xfffcb933bd6fad37aa2d162d1a594001, the math is

round((2^256-1)/(sqrt(1.0001)       *2^128)) = 0xfffcb933bd6fad37aa2d162d1a594001

For subsequent constants all the way up to the second last:

round((2^256-1)/(sqrt(1.0001)^2     *2^128)) = 0xfff97272373d413259a46990580e213a
round((2^256-1)/(sqrt(1.0001)^4     *2^128)) = 0xfff2e50f5f656932ef12357cf3c7fdcc
round((2^256-1)/(sqrt(1.0001)^8     *2^128)) = 0xffe5caca7e10e4e61c3624eaa0941cd0
...
round((2^256-1)/(sqrt(1.0001)^(2^17)*2^128)) = 0x5d6af8dedb81196699c329225ee604
round((2^256-1)/(sqrt(1.0001)^(2^18)*2^128)) = 0x2216e584f5fa1ea926041bedfe98

The last constant, however, is not quite there

round((2^256-1)/(sqrt(1.0001)^(2^19)*2^128)) = 0x48a170392fc23bde77dc94f
                                            != 0x48a170391f7dc42444e8fa2