2
$\begingroup$

In the picture below from CLRS, I fail to understand why exactly $h(k)$ = the $p$ highest-order bits of the lower w-bit half of the product.

For context, this is supposed to compute $h(k) = \lfloor m (k A \; \text{mod} 1) \rfloor $

enter image description here


For further context, CLRS mentions the following, but I still don't quite get why those $p$ highest-order bits are the ones we are looking for.

enter image description here

$\endgroup$
0
3
$\begingroup$

$(kA \bmod 1)$ is in the range $[0,1)$. So multiplying that by $2^p$ gives a number in the range $[0,2^p)$. That is:

$$\left\lfloor 2^p (kA \bmod 1) \right\rfloor = \left\lfloor 2^p (kA \bmod 1) \right \rfloor \bmod 2^p$$

Once you've worked that out, it's not too hard to see:

$$\left\lfloor 2^p (kA \bmod 1) \right \rfloor \bmod 2^p = \left\lfloor kA 2^p \right\rfloor \bmod 2^p = \left\lfloor \frac{ks}{2^{w-p}} \right\rfloor \bmod 2^p$$

So you can implement this by taking $ks$, shifting it $w-p$ bits to the right, then taking the lowest order $p$ bits. Which is exactly the same as taking the highest order $p$ bits of the low word.

$\endgroup$
8
  • 1
    $\begingroup$ In case it helps others who reads this: The result of $x \; \text{mod} \; b^p$ is the last $p$ digits of the number $x$ represented in base $b$. For example: $x \; \text{mod} \; 10$ gives you the last digit of $x$ in base 10. Similarly, $x \; \text{mod} \; 100$ gives you the last two digits of $x$ in base 10, etc. $\endgroup$
    – Josh
    Apr 9 '20 at 16:43
  • $\begingroup$ Maybe I read this too quickly, sorry. I fail to see the first equivalence: $$\left\lfloor 2^p (kA \bmod 1) \right\rfloor = \left\lfloor 2^p (kA \bmod 1) \right \rfloor \bmod 2^p$$ $\endgroup$
    – Josh
    Apr 9 '20 at 19:37
  • $\begingroup$ Do you $(kA see that \bmod 1) \in [0,1)$? Therefore $\left\lfloor 2^p (kA \bmod 1) \right\rfloor < 2^p$. $\endgroup$
    – Pseudonym
    Apr 10 '20 at 7:41
  • $\begingroup$ Thanks - the first formula that you wrote in your comment just above didn't come out well, but I think I follow you. I see that $(k A \bmod 1) \in [0,1)$, i.e. this formula takes the fractional part of the product $kA$ so the result must be $\in [0, 1)$. I also see that if $n$ is a positive integer and $x \in [0,1)$, we must have $n x \leq n$, and thus we would also have $n x \bmod n \leq n$. Is that the argument behind the first Eq. in your answer, i.e. $\left\lfloor 2^p (kA \bmod 1) \right\rfloor = \left\lfloor 2^p (kA \bmod 1) \right \rfloor \bmod 2^p$ ? $\endgroup$
    – Josh
    Apr 11 '20 at 1:44
  • $\begingroup$ Yes, that's it. $\endgroup$
    – Pseudonym
    Apr 11 '20 at 1:49

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.