How many bits to represent a quantity $\omega$ bounded in a particular way? 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} &lt; \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?
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 &lt; {(l+1)(k+1)}$$