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 $$


$$ \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?


1 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)}$$

  • $\begingroup$ Hi, thanks for your reply. Why wouldn't you introduce the rounding until the end? $\endgroup$ Jun 1, 2017 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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