[Solved]: How does taking modulo 1 make sense?

Problem Detail: 

I need some help understanding the problem statement in CLRS 11.3-4 pg 269. It says:

Consider a hash table of size $m = 1000$ and a corresponding hash function $ h(k) =\left \lfloor m(kA \bmod 1) \right \rfloor $ for $A = (\sqrt5 - 1)/2$. Compute the locations to which the keys 61, 62, 63, 64, and 65 are mapped.

Is $\mod 1$ a misprint in my copy? Also $A$ is a real number. Is modulus defined for non-integer numbers?

Asked By : p.j

Answered By : p.j

Thanks to for clarifying mod 1 concept , for constant $\mathcal{A}$ I got the proper explanation in CLRS itself it says : Although this method works with any value of the constant $\mathcal{A}$, it works better with some values than with others. The optimal choice depends on the characteristics of the data being hashed. Knuth suggests that $$ \mathcal{A} \approx (\sqrt(5) - 1)/div 2 = 0.6180339887 ... $$ is likely to work reasonably well. As an example, suppose we have $ \mathcal{k} = 123456, \mathcal{p} = 14, \mathcal{m} = 2^{14} = 16384,$ and $ \mathcal{w} = 32.$ Adapting Knuth's suggestion, we choose $\mathcal{A}$ to be the fraction of the form $$\mathcal{s}/2^{32}$$ that is closest to $$(\sqrt(5) - 1)/ 2,$$ so that $$ \mathcal{A} = 2654435769/2^{32}.$$ Then $$\mathcal{k} . \mathcal{s} = 327706022297664 =(76300 . 2^{32} )+ 17612864,$$ and so $\mathcal{r_{1}} = 76300$ and $\mathcal{r_{0}} = 17612864.$ The 14 most significant bits of $ \mathcal{r_{0}} $ yield the value $\mathcal{h}(k) = 67$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18130

3.2K people like this

 Download Related Notes/Documents