Re: Any references for efficient division code sequences?

Shankar Unni <shankar@webnexus.com> writes:


>Specifically for dividing by small constants (< 16). We're working on a
>small MIPS-like network processor that has no MUL/DIV unit, and need to
>be able to do a *fast* mod by small numbers.


>Are there any references that discuss code sequences for dividing (or
>specifically in our case, remaindering) integers by small constants (for
>any processor that doesn't have a MUL/DIV unit)?


There are some easy special cases. Obviously, remaindering by 2^N is
easily done by ANDing with 2^N-1. Remaindering by 2^N-1 is possible by
adding up all the N-bit aligned N-bit segments (recursively, until the
result is < 2^N) and treat 2^N-1 as 0 in the result. This is exactly
equivalent to finding modulo-9 of a decimal number by adding the
digits and casting out nines.


In general, you can for any N make a finite state machine that makes
trasitions on the digits in a number such that you in the final state
can read off the modulo N. You can choose the base (so you can make
transitions e.g. on each bit or on each hexadecimal digit) and the
order you read the bits (left-to-right or right-to-left). However, the
FSM will have N states, so it is impractical for large N.


Torben Mogensen (torbenm@diku.dk)

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