1
$\begingroup$

Let $x,N$ be positive integers.

I'd like to store a counter which could reach value of $\left\lfloor \frac{N}{x}\right\rfloor$ (i.e. could take any value in $0,1,\ldots,\frac{N}{x}$) using $$\lceil\log_2(N+1)\rceil - \lfloor\log_2 x\rfloor$$

bits.

Equivalently, does the following hold: $$\log\left\lfloor \frac{N}{x} + 1\right\rfloor \leq \lceil\log_2(N+1)\rceil - \lfloor\log_2 x\rfloor$$

Obviously, this holds for $x=1$, what about general $x$?

$\endgroup$
1
  • 1
    $\begingroup$ You could ask the inequality on math.se. However they are bound to ask you if you have at least tried it out for a number of different values of $x$. $\endgroup$ – Anush Jan 29 '15 at 14:08
2
$\begingroup$

This is indeed possible.

First, notice that for storing $\left\lfloor\frac{N}{x}+1\right\rfloor$ values ($0,1,2,\ldots,\left\lfloor\frac{N}{x}\right\rfloor$), you need $\left\lceil\log\left\lfloor\frac{N}{x}+1\right\rfloor\right\rceil$ bits (which might be larger than $\log\left\lfloor\frac{N}{x}+1\right\rfloor$). This won't stop us though :).


We first notice that for every $$\forall 1<x,N\in\mathbb N:\left\lfloor\frac{N}{x}+1\right\rfloor\leq\left\lceil\frac{N+1}{x}\right\rceil$$ To see this, consider the case where $\frac{N}{x}\in \mathbb N$, and thus $$\left\lfloor\frac{N}{x}+1\right\rfloor = \frac{N}{x}+1=\frac{N}{x}+\left\lceil\frac{1}{x}\right\rceil=\left\lceil\frac{N+1}{x}\right\rceil$$ Otherwise, when $\frac{N}{x}\not \in \mathbb N$:$$\left\lfloor\frac{N}{x}+1\right\rfloor =\left\lceil\frac{N}{x}\right\rceil\leq\left\lceil\frac{N+1}{x}\right\rceil$$

Another useful inequality is $\forall r\geq 1:\log\left\lceil r\right\rceil\leq\left\lceil\log r\right\rceil$.

To see this, let $k\in \mathbb N$ such that $2^{k-1}<r\leq2^{k}$.

Now $k-1<\log r\leq k$, and therefore $\left\lceil\log r\right\rceil =k$. Now $\log\left\lceil r\right\rceil\leq k=\left\lceil\log r\right\rceil$.

Finally, we conclude that: $$\left\lceil\log\left\lfloor\frac{N}{x}+1\right\rfloor\right\rceil\leq\left\lceil\log\left\lceil\frac{N+1}{x}\right\rceil\right\rceil\leq\left\lceil\left\lceil\log\frac{N+1}{x}\right\rceil\right\rceil$$ $$=\left\lceil\log(N+1)-\log(x)\right\rceil$$ $$\leq\left\lceil\log(N+1)\right\rceil-\left\lfloor\log(x)\right\rfloor$$

$\endgroup$

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.