🚀 go-pugleaf

In article <44t2n7$oe1@bug.rahul.net>, Samuel P. Kho <samkho@rahul.net> wrote:
>In article <44sjp4$c71@news.jf.intel.com>,
>Mike Haertel <haertel@ichips.intel.com> wrote:
>>People who do hashing usually like primes.  There are some primes of the
>>form 2^n +- 1; remainders modulo such primes still do not require the full
>>force of a fully general remainder routine.  Most compilers I've seen do not
>>optimize this case, but they could--it's only a couple extra shifts and
>>adds over mod 2^n.
>
>could you describe how to take modulo-prime-number-1-less-than-2^n by
>few shifts and adds over mod 2^n?

It's based on the idea that:

    1
  ----- = 1 + z + z**2 + z**3 + ...
  1 - z

when |z| < 1.  (Aside: This is probably the single most useful arithmetic
trick I've ever seen.  It comes up all over the place...)

To compute x % (2**n - 1) = x - (2**n-1) * floor(x /(2**n-1)) do the following:

  x / 2**n-1 = (x / 2**n) + (x / 2**(2*n)) + (x / (2**3*n)) + ... (infinite series)

Note that in binary these are really right shifts: (x >> n) + (x >> 2*n) + ...
except that you need to keep the fractional places around.  You need to
truncate this series.  The point a which you truncate it depends on N
and the word size of your computer.  Furthermore, you have to be
careful since the fractional places can affect rounding.  Anyway, let:

	s = floor( (x >> n) + (x >> 2*n) + ... )

You have to be careful, but this is just a few shifts and adds.
Then the desired modulus is:

	m = (2 ** n - 1) * s.

This is just a shift and a subtract.