# Bit representation of the hashing multiplication method

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

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.

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

• 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.
– Josh
Apr 9 '20 at 16:43
• 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$$
– Josh
Apr 9 '20 at 19:37
• Do you $(kA see that \bmod 1) \in [0,1)$? Therefore $\left\lfloor 2^p (kA \bmod 1) \right\rfloor < 2^p$. Apr 10 '20 at 7:41
• 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$ ?
– Josh
Apr 11 '20 at 1:44
• Yes, that's it. Apr 11 '20 at 1:49