[vox-tech] least number of operations to find modulo (trick question)

[Brian Lavender]

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
> vox-tech at lists.lugod.org
> 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