Multiplication method Assume that all keys are integers, m=2 and our computer has w-bit words. Define h(k)=(Ak mod 2 )rsh(w-r), where rsh is the " bit-wise right-shift operator and A is an odd integer in the range 2w-1<A<2W Dont pick a too close to 2w Multiplication modulo 2w is fast The rsh operator is fast o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 L7.11© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.11 Multiplication method Assume that all keys are integers, m = 2r, and our computer has w-bit words. Define h(k) = (A·k mod 2w) rsh (w – r), where rsh is the “bit-wise right-shift” operator and A is an odd integer in the range 2w–1 < A < 2w. • Don’t pick A too close to 2w. • Multiplication modulo 2w is fast. • The rsh operator is fast