4
$\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 Answer 1

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$
1
  • $\begingroup$ Hi, thanks for your reply. Why wouldn't you introduce the rounding until the end? $\endgroup$ Commented Jun 1, 2017 at 8:27

Your Answer

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

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