Re: integer mod with constant modulus.

"R. Bernstein" <rocky@panix.com> wrote:


> The first part of the idea is really simple and used to be taught in
> school; it is known as casting out nines. Changing to a binary radix,
> the rule would be: for powers of two minus 1,
> you sum up blocks of bits (size = log (number+1)) in a word.


Or put slightly more formally:
            an n a
  m * 2 == m * b mod p if 2 == b mod p




For the case where b = -1, 0, or 1, this leads to optimizations where
you sum the chunks of bits, with alternating sign (b=-1), all positive
(b=1), or forget all but the least significant chunk (b=0).


If b isn't -1,0 or 1, it is still possible to use this method, but it
becomes uglier: for example the nearest prime to 2^12 is 4093, making
b = +3. For a 32 bit value you can use the relation
            12 12
  m * 2 + l == 3m+l mod 2 - 3


and simply apply it a few times before the final test (this avoids
having to deal with higher powers of b, which might be more expensive
to multiply by) Clearly using this method to reduce modulo 23 will
not be very optimal (b = -7 (8 chunks) or +9 (7 chunks)).


In practice there are not many moduli that are amenable to this
method, unless the compiler gets to chose the modulus itself and can
make it close to a power of 2 (!!).


> Blocks of bits in a word can be summed in parallel in a register using
> the usual add and subtract operations provided you make sure that
> there is no possibility for a carry to occur between blocks. This is
> done by by copying, masking and shifting.


These precautions include taking care if your dividend is negative,
since 2^32 mod p is unlikely to be zero!




| Mark Tillotson | Harlequin Ltd. | markt@harlequin.co.uk |
| http://www.harlequin.co.uk/ | +44 1223 873829 |
--

Return to the comp.compilers page.
Search the comp.compilers archives again.