7 (2^3 - 1) is a Mersenne prime. Thus, finding the modulus involves an and, a shift, an and, and an add.
10100 20 111 & 7 ----- 100 == 4 Shift 3 to the right. 010 111 & ---- 010 == 2 4 + 2 = 6 Voila, Modulus in 4 operations! Much faster than divide! In this case, we would only have 7 slots for a hash function, probably not the most effective. On Thu, Feb 18, 2010 at 12:03:47AM -0800, Bill Kendrick wrote: > Brian said: > > There is something special about the number 7 that makes this problem > > unique. > > Rea11y? What wou1d that be? ;) > > -bill! > _______________________________________________ > vox-tech mailing list > [email protected] > http://lists.lugod.org/mailman/listinfo/vox-tech -- Brian Lavender http://www.brie.com/brian/ "About 3 million computers get sold every year in China, but people don't pay for the software. Someday they will, though. As long as they are going to steal it, we want them to steal ours. They'll get sort of addicted, and then we'll somehow figure out how to collect sometime in the next decade." -- Bill Gates (Microsoft) 1998 _______________________________________________ vox-tech mailing list [email protected] http://lists.lugod.org/mailman/listinfo/vox-tech
