3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

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

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.