# Re: integer mod with constant modulus.

## markt@harlequin.co.uk (Mark Tillotson)Tue, 4 Jul 1995 15:42:01 GMT

From comp.compilers

Related articles
integer mod with constant modulus. rocky@panix.com (R. Bernstein) (1995-06-24)
Re: integer mod with constant modulus. mernst@theory.lcs.mit.edu (1995-06-29)
Re: integer mod with constant modulus. markt@harlequin.co.uk (1995-07-04)
| List of all articles for this month |

 Newsgroups: comp.compilers From: markt@harlequin.co.uk (Mark Tillotson) Keywords: arithmetic Organization: Harlequin Limited, Cambridge, England References: 95-06-047 Date: Tue, 4 Jul 1995 15:42:01 GMT

"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 |
--

Post a followup to this message