Logarithm Approximation Precision

This cosument formally proves maximum absolute errors of approximated logarithm calculation to be used in Uniswap v2 protocol.

Base-2 Logarithm Approximation

We approximate base-2 logarithm iteratively. Initial approximation for

${\log }_{2}x$ is defined like this:

$$l_0(x)=\lfloor {\log }_{2}x\rfloor$$

So the initial approximation is just the logarithm rounded down, i.e. towards

$-\mathrm{\infty }$. The absolute error of the initial approximation is bounded like this:

$${\epsilon }_0(x)=l_0(x)-{\log }_{2}x\in (-1;+0]$$

Every next approximation is defined like this:

$$l_{i+1}(x)=\lfloor {\log }_{2}x\rfloor +\frac{1}{2}{l}_i\left({\lfloor {\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2\rfloor }_{2^{-127}}\right)$$

Here

${\lfloor a\rfloor }_b$ means

$a$ rounded down to the closest factor of

$b$.

The absolute error of this approximation is:

$$\begin{gathered} {\epsilon }_{i+1}(x)=l_{i+1}-{\log }_{2}x= \\ =\lfloor {\log }_{2}x\rfloor +\frac{1}{2}{l}_i\left({\lfloor {\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2\rfloor }_{2^{-127}}\right)-{\log }_2\left(2^{\lfloor {\log }_{2}x\rfloor }\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\right)= \\ =\lfloor {\log }_{2}x\rfloor +\frac{1}{2}{l}_i\left({\lfloor {\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2\rfloor }_{2^{-127}}\right)-\lfloor {\log }_{2}x\rfloor -{\log }_2\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}= \\ =\frac{1}{2}{l}_i\left({\lfloor {\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2\rfloor }_{2^{-127}}\right)-{\log }_2\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}= \\ =\frac{1}{2}{l}_i\left({\lfloor {\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2\rfloor }_{2^{-127}}\right)-\frac{1}{2}{\log }_2{\left(\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\right)}^2= \\ =\frac{1}{2}(l_i\left({\lfloor {\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2\rfloor }_{2^{-127}}\right)-{\log }_2{\left(\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\right)}^2) \end{gathered}$$

Let's note, that

$${\log }_{2}x-1<\lfloor {\log }_{2}x\rfloor ⩽{\log }_{2}x$$

thus

$$2^{{\log }_{2}x-1}<2^{\lfloor {\log }_{2}x\rfloor }⩽2^{{\log }_{2}x}$$

then

$$\frac{x}{2}<2^{\lfloor {\log }_{2}x\rfloor }⩽x$$

and finally:

$$\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\in [1;2)$$

Let's pick

$\alpha$ such that

$${\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}=\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\cdot (1-\alpha )$$

$$\alpha =\frac{\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}-{\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}}{\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}}\in [0;2^{-127})$$

Let's pick

$\beta$ such that

$${\lfloor {\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2\rfloor }_{2^{-127}}={\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2\cdot (1-\beta )$$

$$\beta =\frac{{\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2-{\lfloor {\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2\rfloor }_{2^{-127}}}{{\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2}\in [0;2^{-127})$$

Now we have:

$$\begin{gathered} {\epsilon }_{i+1}(x)=\cdots = \\ =\frac{1}{2}(l_i({(\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\cdot (1-\alpha ))}^2\cdot (1-\beta ))-{\log }_2{\left(\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\right)}^2)= \\ =\frac{1}{2}(l_i({\left(\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\right)}^2\cdot (1-\alpha {)}^2\cdot (1-\beta ))- \\ -{\log }_2({\left(\frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\right)}^2\cdot (1-\alpha {)}^2\cdot (1-\beta ))+ \\ +{\log }_2((1-\alpha {)}^2\cdot (1-\beta )))= \\ =\frac{1}{2}({\epsilon }_i\left({\lfloor {\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2\rfloor }_{2^{-127}}\right)+{\log }_2((1-\alpha {)}^2\cdot (1-\beta )))= \\ =\frac{1}{2}({\epsilon }_i\left({\lfloor {\left({\lfloor \frac{x}{2^{\lfloor {\log }_{2}x\rfloor }}\rfloor }_{2^{-127}}\right)}^2\rfloor }_{2^{-127}}\right)+2{\log }_2(1-\alpha )+{\log }_2(1-\beta ))\in \\ \in (\frac{1}{2}min{\epsilon }_i+\frac{3}{2}{\log }_2(1-2^{-127});+0]= \\ =(-2^{-(i+1)}+3(1-2^{-(i+1)}){\log }_2(1-2^{-127});0] \end{gathered}$$

Base-1.01 Logarithm Approximation

We approximate base-1.01 logarithm

${\log }_{1.01}x$ like this:

$${\log }_{1.01}x\approx \xi \cdot l_i(x)$$

Where

$\xi =\frac{1285013416526911433821}{2^{64}}>\frac{1}{{\log }_{2}1.01}$. The error of such approximation is:

$$\begin{gathered} \xi \cdot l_i(x)-{\log }_{1.01}x= \\ =\xi \cdot ({\log }_{2}x+{\epsilon }_i(x))-\frac{{\log }_{2}x}{{\log }_{2}1.01}= \\ ={\log }_{2}x(\xi -\frac{1}{{\log }_{2}1.01})+\xi \cdot {\epsilon }_i(x) \end{gathered}$$

For

$x\in [2^{-112};2^{112})$ the approximation error is within the following range:

$$\begin{gathered} (-112(\xi -\frac{1}{{\log }_{2}1.01})+\xi \cdot (-2^{-i}+3(1-2^{-i}){\log }_2(1-2^{-127})); \\ 112(\xi -\frac{1}{{\log }_{2}1.01})) \end{gathered}$$

Base-

$\sqrt{1.0001}$ Logarithm Approximation

We approximate base-

$\sqrt{1.0001}$ logarithm

${\log }_{\sqrt{1.0001}}x$ like this:

$${\log }_{\sqrt{1.0001}}x\approx \psi \cdot l_i(x)$$

Where

$\psi =\frac{255738958999603826347141}{2^{64}}>\frac{1}{{\log }_2\sqrt{1.0001}}$. The error of such approximation is:

$$\begin{gathered} \psi \cdot l_i(x)-{\log }_{\sqrt{1.0001}}x= \\ =\psi \cdot ({\log }_{2}x+{\epsilon }_i(x))-\frac{{\log }_{2}x}{{\log }_2\sqrt{1.0001}}= \\ ={\log }_{2}x(\psi -\frac{1}{{\log }_2\sqrt{1.0001}})+\psi \cdot {\epsilon }_i(x) \end{gathered}$$

For

$x\in [2^{-64};2^{64})$ the approximation error is within the following range:

$$\begin{gathered} (-64(\psi -\frac{1}{{\log }_2\sqrt{1.0001}})+\psi \cdot (-2^{-i}+3(1-2^{-i}){\log }_2(1-2^{-127})); \\ 64(\psi -\frac{1}{{\log }_2\sqrt{1.0001}})) \end{gathered}$$

Approximation of

${\mathtt{getRatioAtTick}}^{-1}$ (normal ticks)

Function

$\mathtt{getRatioAtTick}(x)$ approximates

${1.01}^x$ with relative pricision not worse than

$0.01\mathrm{\%}$. Thus:

$$\mathtt{getRatioAtTick}(x)=\gamma (x)\cdot {1.01}^x$$

where

$\gamma (x)\in [0.9999;1.0001]$. By inverting this function we have:

$${\mathtt{getRatioAtTick}}^{-1}(x)={\log }_{1.01}\frac{x}{\gamma (y)}={\log }_{1.01}x-{\log }_{1.01}\gamma (y)$$

Here

$y$ is some number. Note, that while actual

$\mathtt{getRatioAtTick}(x)$ function may be calculated only for integer arguments, we assume that it is consinuously and strictly-monotonically defined for all real numbers. This assumtion allows us to consider inverse function

${\mathtt{getRatioAtTick}}^{-1}(x)$ to be defined for all positive arguments.

We approximate the inverse function

${\mathtt{getRatioAtTick}}^{-1}(x)$ like this:

$${\log }_{1.01}x-{\log }_{1.01}\gamma (y)\approx \xi \cdot l_i(x)$$

The absoulte error of such approximation is:

$$\xi \cdot l_i(x)-{\log }_{1.01}x+{\log }_{1.01}\gamma (y)$$

For

$x\in [2^{-112};2^{112})$ the error is within the following range:

$$\begin{gathered} (-112(\xi -\frac{1}{{\log }_{2}1.01})+ \\ +\xi \cdot (-2^{-i}+3(1-2^{-i}){\log }_2(1-2^{-127}))+ \\ +{\log }_{1.01}0.9999; \\ 112(\xi -\frac{1}{{\log }_{2}1.01})+{\log }_{1.01}1.0001) \end{gathered}$$

Here

$-112(\xi -\frac{1}{{\log }_{2}1.01})$ and

$112(\xi -\frac{1}{{\log }_{2}1.01})$ are contributed by the imperfection of

$\xi$ value;

$\xi \cdot (-2^{-i})$ is contributed by the finity of

$i$;

$\xi \cdot 3(1-2^{-i}){\log }_2(1-2^{-127})$ is contributed by the rounding errors inside the approximation algorithm implementation (the implementation uses 129.127-bit binary fixed point numbers, thus

$2^{-127}$ thing); finally

${\log }_{1.01}0.9999$ and

${\log }_{1.01}1.0001$ are contributed by the imperfection of

$\mathtt{getRatioAtTick}$ implementation.

Approximation of

${\mathtt{getRatioAtTick}}^{-1}$ (fine ticks)

Function

$\mathtt{getRatioAtTick}(x)$ approximates

${\sqrt{1.0001}}^x$ with relative pricision not worse than

$0.00005\mathrm{\%}$. Thus:

$$\mathtt{getRatioAtTick}(x)=\gamma (x)\cdot {\sqrt{1.0001}}^x$$

where

$\gamma (x)\in [0.9999995;1.0000005]$. By inverting this function we have:

$${\mathtt{getRatioAtTick}}^{-1}(x)={\log }_{\sqrt{1.0001}}\frac{x}{\gamma (y)}={\log }_{\sqrt{1.0001}}x-{\log }_{\sqrt{1.0001}}\gamma (y)$$

Here

$y$ is some number. Note, that while actual

$\mathtt{getRatioAtTick}(x)$ function may be calculated only for integer arguments, we assume that it is consinuously and strictly-monotonically defined for all real numbers. This assumtion allows us to consider inverse function

${\mathtt{getRatioAtTick}}^{-1}(x)$ to be defined for all positive arguments.

We approximate the inverse function

${\mathtt{getRatioAtTick}}^{-1}(x)$ like this:

$${\log }_{\sqrt{1.0001}}x-{\log }_{\sqrt{1.0001}}\gamma (y)\approx \psi \cdot l_i(x)$$

The absoulte error of such approximation is:

$$\psi \cdot l_i(x)-{\log }_{\sqrt{1.0001}}x+{\log }_{\sqrt{1.0001}}\gamma (y)$$

For

$x\in [2^{-64};2^{64})$ the error is within the following range:

$$\begin{gathered} (-64(\psi -\frac{1}{{\log }_2\sqrt{1.0001}})+ \\ +\psi \cdot (-2^{-i}+3(1-2^{-i}){\log }_2(1-2^{-127}))+ \\ +{\log }_{\sqrt{1.0001}}0.9999995; \\ 64(\psi -\frac{1}{{\log }_2\sqrt{1.0001}})+{\log }_{\sqrt{1.0001}}1.0000005) \end{gathered}$$

Here

$-64(\psi -\frac{1}{{\log }_2\sqrt{1.0001}})$ and

$64(\psi -\frac{1}{{\log }_2\sqrt{1.0001}})$ are contributed by the imperfection of

$\psi$ value;

$\psi \cdot (-2^{-i})$ is contributed by the finity of

$i$;

$\psi \cdot 3(1-2^{-i}){\log }_2(1-2^{-127})$ is contributed by the rounding errors inside the approximation algorithm implementation (the implementation uses 129.127-bit binary fixed point numbers, thus

$2^{-127}$ thing); finally

${\log }_{\sqrt{1.0001}}0.9999995$ and

${\log }_{\sqrt{1.0001}}1.0000005$ are contributed by the imperfection of

$\mathtt{getRatioAtTick}$ implementation.

Choosing The Right

$i$ (normal ticks)

What we need is to calculate for given positive value

$y$ the maximum integer

$x$ such that

$\mathtt{getRatioAtTick}(x)⩽y$. Basically we need to solve the following inequation in integer numbers:

$$\mathtt{getRatioAtTick}(x)⩽y<\mathtt{getRatioAtTick}(x+1)$$

or

$$x⩽{\mathtt{getRatioAtTick}}^{-1}(y)<x+1$$

Thus:

$$x=\lfloor {\mathtt{getRatioAtTick}}^{-1}(y)\rfloor$$

Once we know, that

${\mathtt{getRatioAtTick}}^{-1}(y)\in [x_{min};x_{max}]$, then

$x\in [\lfloor x_{min}\rfloor ;\lfloor x_{max}\rfloor ]$. When

$x_{max}-x_{min}<1$ there are at most two integer values fitting into range

$[\lfloor x_{min}\rfloor ;\lfloor x_{max}\rfloor ]$, thus the right value could be chosen by calling

$\mathtt{getRatioAtTick}$ function at most once.

The following table gives possible ranges of absolute approximation error

$\epsilon$ of

${\mathtt{getRatioAtTick}}^{-1}(y)$ for

$i\in \{0,\dots ,10\}$:

$i$	$min\epsilon$	$max\epsilon$	$P$
$0$	$-69.68$	$0.01005$
$1$	$-34.85$	$0.01005$
$2$	$-17.43$	$0.01005$
$3$	$-8.718$	$0.01005$
$4$	$-4.364$	$0.01005$
$5$	$-2.187$	$0.01005$
$6$	$-1.099$	$0.01005$
$7$	$-0.5543$	$0.01005$	$57\mathrm{\%}$
$8$	$-0.2822$	$0.01005$	$30\mathrm{\%}$
$9$	$-0.1462$	$0.01005$	$16\mathrm{\%}$
$10$	$-0.07808$	$0.01005$	$9\mathrm{\%}$

For

$i⩾7$ at most one call to

$\mathrm{getRatioAtTick}$ is needed to return bit-perfect

${\mathrm{getRatioAtTick}}^{-1}x$ value. The probability

$P$ of

$\mathrm{getRatioAtTick}$ call is shown in the last column.

Choosing The Right

$i$ (fine ticks)

What we need is to calculate for given positive value

$y$ the maximum integer

$x$ such that

$\mathtt{getRatioAtTick}(x)⩽y$. Basically we need to solve the following inequation in integer numbers:

$$\mathtt{getRatioAtTick}(x)⩽y<\mathtt{getRatioAtTick}(x+1)$$

or

$$x⩽{\mathtt{getRatioAtTick}}^{-1}(y)<x+1$$

Thus:

$$x=\lfloor {\mathtt{getRatioAtTick}}^{-1}(y)\rfloor$$

Once we know, that

${\mathtt{getRatioAtTick}}^{-1}(y)\in [x_{min};x_{max}]$, then

$x\in [\lfloor x_{min}\rfloor ;\lfloor x_{max}\rfloor ]$. When

$x_{max}-x_{min}<1$ there are at most two integer values fitting into range

$[\lfloor x_{min}\rfloor ;\lfloor x_{max}\rfloor ]$, thus the right value could be chosen by calling

$\mathtt{getRatioAtTick}$ function at most once.

The following table gives possible ranges of absolute approximation error

$\epsilon$ of

${\mathtt{getRatioAtTick}}^{-1}(y)$ for

$i\in \{0,\dots ,20\}$:

$i$	$min\epsilon$	$max\epsilon$	$P$
$0$	$-13863.6$	$0.0100005$
$1$	$-6931.83$	$0.0100005$
$2$	$-3465.92$	$0.0100005$
$3$	$-1732.96$	$0.0100005$
$4$	$-866.487$	$0.0100005$
$5$	$-433.249$	$0.0100005$
$6$	$-216.629$	$0.0100005$
$7$	$-108.32$	$0.0100005$
$8$	$-54.1648$	$0.0100005$
$9$	$-27.0874$	$0.0100005$
$10$	$-13.5487$	$0.0100005$
$11$	$-6.77935$	$0.0100005$
$12$	$-3.39468$	$0.0100005$
$13$	$-1.70234$	$0.0100005$
$14$	$-0.85617$	$0.0100005$	86%
$15$	$-0.433085$	$0.0100005$	44%
$16$	$-0.221543$	$0.0100005$	23%
$17$	$-0.115772$	$0.0100005$	12%
$18$	$-0.0628861$	$0.0100005$	7%
$19$	$-0.0364433$	$0.0100005$	4%
$20$	$-0.0232219$	$0.0100005$	3%

For

$i⩾14$ at most one call to

$\mathrm{getRatioAtTick}$ is needed to return bit-perfect

${\mathrm{getRatioAtTick}}^{-1}x$ value. The probability

$P$ of

$\mathrm{getRatioAtTick}$ call is shown in the last column.