# 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) = \left\lfloor \log_2 x \right\rfloor
$$

So the initial approximation is just the logarithm rounded down, i.e. towards $-\infty$. The absolute error of the initial approximation is bounded like this:

$$
\varepsilon_0(x) = l_0 (x) - \log_2 x \in (-1;+0]
$$

Every next approximation is defined like this:

$$
l_{i+1}(x) = \left\lfloor \log_2 x \right\rfloor + \frac{1}{2} l_i \left(\left\lfloor\left(\left\lfloor\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right\rfloor_{2^{-127}}\right)^2\right\rfloor_{2^{-127}}\right)
$$

Here $\left\lfloor a \right\rfloor_b$ means $a$ rounded down to the closest factor of $b$.

The absolute error of this approximation is:

$$
\varepsilon_{i+1}(x) = l_{i+1} - \log_2 x =\\=
\left\lfloor \log_2 x \right\rfloor + \frac{1}{2} l_i \left(\left\lfloor\left(\left\lfloor\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right\rfloor_{2^{-127}}\right)^2\right\rfloor_{2^{-127}}\right) - \log_2 \left(2^{\left\lfloor \log_2 x \right\rfloor}\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right) =\\=
\left\lfloor \log_2 x \right\rfloor + \frac{1}{2} l_i \left(\left\lfloor\left(\left\lfloor\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right\rfloor_{2^{-127}}\right)^2\right\rfloor_{2^{-127}}\right) - \left\lfloor \log_2 x \right\rfloor - \log_2 \frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}} =\\=
\frac{1}{2} l_i \left(\left\lfloor\left(\left\lfloor\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right\rfloor_{2^{-127}}\right)^2\right\rfloor_{2^{-127}}\right) - \log_2 \frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}} =\\=
\frac{1}{2} l_i \left(\left\lfloor\left(\left\lfloor\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right\rfloor_{2^{-127}}\right)^2\right\rfloor_{2^{-127}}\right) - \frac{1}{2}\log_2\left(\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right)^2 =\\=
\frac{1}{2} \left(l_i \left(\left\lfloor\left(\left\lfloor\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right\rfloor_{2^{-127}}\right)^2\right\rfloor_{2^{-127}}\right) - \log_2\left(\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right)^2\right)
$$

Let's note, that

$$
\log_2 x - 1 < \left\lfloor \log_2 x \right\rfloor \leqslant \log_2 x
$$

thus

$$
2^{\log_2 x - 1} < 2^{\left\lfloor \log_2 x \right\rfloor} \leqslant 2^{\log_2 x}
$$

then

$$
\frac{x}{2} < 2^{\left\lfloor \log_2 x \right\rfloor} \leqslant x
$$

and finally:

$$
\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}} \in [1;2)
$$

Let's pick $\alpha$ such that

$$
\left\lfloor\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right\rfloor_{2^{-127}} = \frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}} \cdot (1 - \alpha)
$$

$$
\alpha = \frac{\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}} - \left\lfloor\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right\rfloor_{2^{-127}}}{\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}} \in \left[0; 2^{-127}\right)
$$

Let's pick $\beta$ such that

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

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

Now we have:

$$
\varepsilon_{i+1}(x) = \dots =\\=
\frac{1}{2} \left(l_i \left(\left(\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\cdot (1 - \alpha)\right)^2 \cdot (1 - \beta)\right) - \log_2\left(\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right)^2\right) =\\=
\frac{1}{2} \left(l_i \left(\left(\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right)^2 \cdot (1 - \alpha)^2 \cdot (1 - \beta)\right) -\\- \log_2\left(\left(\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right)^2 \cdot (1 - \alpha)^2 \cdot (1 - \beta)\right) +\\+
\log_2 \left((1 - \alpha)^2 \cdot (1 - \beta)\right)\right)=\\=
\frac{1}{2}\left(\varepsilon_i\left(\left\lfloor\left(\left\lfloor\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right\rfloor_{2^{-127}}\right)^2\right\rfloor_{2^{-127}}\right) + \log_2 \left((1 - \alpha)^2 \cdot (1 - \beta)\right)\right) =\\=
\frac{1}{2}\left(\varepsilon_i\left(\left\lfloor\left(\left\lfloor\frac{x}{2^{\left\lfloor \log_2 x \right\rfloor}}\right\rfloor_{2^{-127}}\right)^2\right\rfloor_{2^{-127}}\right) + 2 \log_2 \left(1 - \alpha\right) + \log_2 \left(1 - \beta\right)\right) \in\\\in
\left(\frac{1}{2} \min \varepsilon_i + \frac{3}{2} \log_2\left(1 - 2^{-127}\right);+0\right] =\\=
\left(-\,2^{-(i + 1)} + 3\left(1-2^{-(i + 1)}\right)\log_2\left(1 - 2^{-127}\right);0\right]
$$

## 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:

$$
\xi \cdot l_i (x) - \log_{1.01} x =\\=
\xi \cdot \left(\log_2 x + \varepsilon_i (x)\right) - \frac{\log_2 x}{\log_2 1.01} =\\=
\log_2 x\left(\xi - \frac{1}{\log_2 1.01}\right) + \xi \cdot \varepsilon_i (x)
$$

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

$$
\left(-112\left(\xi - \frac{1}{\log_2 1.01}\right) + \xi \cdot \left(-\,2^{-i} + 3\left(1-2^{-i}\right)\log_2\left(1 - 2^{-127}\right)\right);\\
112\left(\xi - \frac{1}{\log_2 1.01}\right)\right)
$$

## 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:

$$
\psi \cdot l_i (x) - \log_{\sqrt{1.0001}} x =\\=
\psi \cdot \left(\log_2 x + \varepsilon_i (x)\right) - \frac{\log_2 x}{\log_2 \sqrt{1.0001}} =\\=
\log_2 x\left(\psi - \frac{1}{\log_2 \sqrt{1.0001}}\right) + \psi \cdot \varepsilon_i (x)
$$

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

$$
\left(-64\left(\psi - \frac{1}{\log_2 \sqrt{1.0001}}\right) + \psi \cdot \left(-\,2^{-i} + 3\left(1-2^{-i}\right)\log_2\left(1 - 2^{-127}\right)\right);\\
64\left(\psi - \frac{1}{\log_2 \sqrt{1.0001}}\right)\right)
$$

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

Function $\mathtt{getRatioAtTick}(x)$ approximates $1.01^x$ with relative pricision not worse than $0.01\%$. Thus:

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

where $\gamma(x) \in \left[0.9999; 1.0001\right]$. 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 \left[2^{-112}; 2^{112}\right)$ the error is within the following range:

$$
\left(-112\left(\xi - \frac{1}{\log_2 1.01}\right) +\\+
\,\xi \cdot \left(-\,2^{-i} + 3\left(1-2^{-i}\right)\log_2\left(1 - 2^{-127}\right)\right) +\\+
\log_{1.01} 0.9999;\\
112\left(\xi - \frac{1}{\log_2 1.01}\right) + \log_{1.01} 1.0001\right)
$$

Here $-112\left(\xi - \frac{1}{\log_2 1.01}\right)$ and $112\left(\xi - \frac{1}{\log_2 1.01}\right)$ are contributed by the imperfection of $\xi$ value; $\xi \cdot \left(-\,2^{-i}\right)$ is contributed by the finity of $i$; $\xi \cdot 3\left(1-2^{-i}\right)\log_2\left(1 - 2^{-127}\right)$ 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\%$. Thus:

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

where $\gamma(x) \in \left[0.9999995; 1.0000005\right]$. 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 \left[2^{-64}; 2^{64}\right)$ the error is within the following range:

$$
\left(-64\left(\psi - \frac{1}{\log_2 \sqrt{1.0001}}\right) +\\+
\,\psi \cdot \left(-\,2^{-i} + 3\left(1-2^{-i}\right)\log_2\left(1 - 2^{-127}\right)\right) +\\+
\log_{\sqrt{1.0001}} 0.9999995;\\
64\left(\psi - \frac{1}{\log_2 \sqrt{1.0001}}\right) + \log_{\sqrt{1.0001}} 1.0000005\right)
$$

Here $-64\left(\psi - \frac{1}{\log_2 \sqrt{1.0001}}\right)$ and $64\left(\psi - \frac{1}{\log_2 \sqrt{1.0001}}\right)$ are contributed by the imperfection of $\psi$ value; $\psi \cdot \left(-\,2^{-i}\right)$ is contributed by the finity of $i$; $\psi \cdot 3\left(1-2^{-i}\right)\log_2\left(1 - 2^{-127}\right)$ 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) \leqslant y$. Basically we need to solve the following inequation in integer numbers:

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

or

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

Thus:

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

Once we know, that $\mathtt{getRatioAtTick}^{-1}(y) \in \left[x_{min};x_{max}\right]$, then $x \in \left[\left\lfloor x_{min}\right\rfloor; \left\lfloor x_{max}\right\rfloor\right]$. When $x_{max} - x_{min} < 1$ there are at most two integer values fitting into range $\left[\left\lfloor x_{min}\right\rfloor; \left\lfloor x_{max}\right\rfloor\right]$, 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 $\varepsilon$ of $\mathtt{getRatioAtTick}^{-1}(y)$ for $i \in \{0, \dots, 10\}$:

| $i$ | $\min \varepsilon$ | $\max \varepsilon$ | $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\%$ |
| $8$ | $-0.2822$ | $0.01005$ | $30\%$ |
| $9$ | $-0.1462$ | $0.01005$ | $16\%$ |
| $10$ | $-0.07808$ | $0.01005$ | $9\%$ |

For $i \geqslant 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) \leqslant y$. Basically we need to solve the following inequation in integer numbers:

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

or

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

Thus:

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

Once we know, that $\mathtt{getRatioAtTick}^{-1}(y) \in \left[x_{min};x_{max}\right]$, then $x \in \left[\left\lfloor x_{min}\right\rfloor; \left\lfloor x_{max}\right\rfloor\right]$. When $x_{max} - x_{min} < 1$ there are at most two integer values fitting into range $\left[\left\lfloor x_{min}\right\rfloor; \left\lfloor x_{max}\right\rfloor\right]$, 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 $\varepsilon$ of $\mathtt{getRatioAtTick}^{-1}(y)$ for $i \in \{0, \dots, 20\}$:

| $i$ | $\min \varepsilon$ | $\max \varepsilon$ | $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 \geqslant 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.