How many bits to represent a quantity $\omega$ bounded in a particular way?

Question

I'm working out some details to implement a division algorithm, I'm following the explanation given in this book (chapter 5) for who is interested.

Anyway I need to work out how many bits are necessary to represent a value $\omega$ bounded by

$$ | \omega | \leq \rho r^{k+1} y $$

where

$$ \begin{array}{l} \frac{1}{2} < \rho \leq 1 \\ r = 2^l, \text{where $l\geq 1$ is some integer} \\ 0 \leq y \leq 2^{k} - 1, \text{ $k$ positive integer} \end{array} $$

My approach is finding the number of bits to represent $| \omega |$ and then adding one bit to represent the sign of $\omega$, in two complement.

There fore

$$ \left\lceil \log_2(|\omega|) \right\rceil \leq \left\lceil \log_2(\rho r^{k+1} y) \right\rceil = \left\lceil \log_2(\rho) + (k+1)\log_2 r + \log_2(y) \right\rceil \leq \left\lceil (k+1)l + \log_2(2^k-1))\right\rceil \leq \left\lceil (k+1)l + k \right\rceil = \left\lceil (k+1)(l+1) - 1 \right\rceil = (k+1)(l+1) - 1 $$

Therefore in two complement I would need a total of $(k+1)(l+1)$ bits to represent my value $\omega$.

Is this correct?

Answer 1

Yes it's correct, but I would not introduce the rounding until the end. Let $w = |\omega|$, then in the worst case:

$$w \leq \rho r^{k+1}y$$

$$w \leq 1\cdot r^{k+1}y$$ $$w \leq (2^l)^{k+1}y$$ $$w \leq (2^l)^{k+1}(2^k-1)$$ $$\log_2(w) \leq \log_2((2^l)^{k+1}) + \log_2(2^k-1)$$ $$\log_2(w) \leq \log_2(2^{l(k+1)}) + \log_2(2^k)$$ $$\log_2(w) \leq {l(k+1)} + k$$ $$\log_2(w) \leq {(l+1)(k+1)} -1$$ $$\lceil\log_2(w)\rceil \leq {(l+1)(k+1)} -1$$ $$\lceil\log_2(w)\rceil < {(l+1)(k+1)}$$