Consider the problem of representing in memory numbers in the range $\{1,\ldots,n\}$.

Obviously, exact representation of such number requires $\lceil\log_2(n)\rceil$ bits.

In contrast, assume we are allowed to have compressed representations such that when reading the number we get a 2-approximation for the original number. Now we can encode each number using $O(\log\log n)$ bits. For example, given an integer $x\in\{1,\ldots,n\}$, we can store $z = \text{Round}(\log_2 x)$. When asked to reconstruct an approximation for $x$, we compute $\widetilde{x} = 2^z$. Obviously, $z$ is in the range $\{0,1,\ldots,\log_2 n\}$ and only requires $O(\log\log n)$ bits to represent.

In general, given a parameter $\epsilon>0$, what is the minimal number of bits required for saving an approximate representation of an integer in the above set, so that we can reconstruct its value up to a multiplicative error of $(1+\epsilon)$?

The above example shows that for $\epsilon=1$, approximately $\log\log n$ bits are enough. This probably holds asymptotically for every constant $\epsilon$. But how does epsilon affect the memory (e.g., does it require $\Theta(\frac{1}{\epsilon^2}\log\log n)$ bits?).


Storing $x$ to within a $1+\epsilon$ approximation can be done with $\lg \lg n - \lg(\epsilon) + O(1)$ bits.

Given an integer $x$, you can store $z = \text{Round}(\log_{1+\epsilon} x)$. $z$ is in the range $\{0,1,\dots,\log_{1+\epsilon} n\}$, so requires about $b = \lg \log_{1+\epsilon} n$ bits. Doing a bit of math, we find

$$b = \lg \frac{\lg n}{\lg(1+\epsilon)} = \lg \lg n - \lg \lg (1+\epsilon).$$

Now $\lg(1+\epsilon) = \log(1+\epsilon)/\log(2) \approx \epsilon/\log(2)$, by a Taylor series approximation. Plugging in, we get

$$b = \lg \lg n - \lg(\epsilon) + \lg(\log(2)),$$

which yields the claimed answer.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.