Next Meeting: August 5: Social gathering Next Installfest: TBD Latest News: Jul. 4: July, August and September: Security, Photography and Programming for Kids Page last updated: 2010 Feb 18 20:19
Re: [vox-tech] least number of operations to find modulo (trickquestion)

# Re: [vox-tech] least number of operations to find modulo (trickquestion)

```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@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
_______________________________________________
vox-tech mailing list
vox-tech@lists.lugod.org
http://lists.lugod.org/mailman/listinfo/vox-tech

```