Tue, 4 Jul 1995 15:42:01 GMT

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

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.