no, we don't either.
2003-12-14, 2:21 p.m.
An advantage of the multiplication method is the fact that the value of m is not critical. we typically choose it to be a power of 2 (m = 2^p for some integer p) since we can then easily implement the function on most computers as follows. suppose that the word size of the machine is w bits and that k fits into a single word. we restrict A to be a fraction of the form s/2^2, where s is an integer in the range 0 < s < 2^w. referring to figure 11.4, we first multiply k by the w-bit integer s = A2^2. the result is a 2w-bit value r(1)2^w + r(0), where r(1) is the high-order word of the product and r(0) is the low-order word of the product. the desired p-bit hash value consists of the p most significant bits of r(0).
* * *
as an example, suppose we have k = 123456, p = 14, m = 2^14 = 16384, and w = 32. adapting knuth's suggestion, we choose A to be the fraction of the form s/2^32 that is closest to (sqrt(5) - 1)/2, so that A = 2654435769/2^32. then ks = 327706022297664 = (76300(2^32)) + 17612864, and so r(1) = 76300 and r(0) = 17612864. the 14 most significant bits of r(0) yield the value h(k) = 67.