2 Jul 2001 00:30:20 -0400

Related articles |
---|

Any references for efficient division code sequences? shankar@webnexus.com (Shankar Unni) (2001-06-28) |

Re: Any references for efficient division code sequences? torbenm@diku.dk (2001-07-02) |

Re: Any references for efficient division code sequences? rv3s@cobra.cs.virginia.edu (Raja Venkateswaran) (2001-07-02) |

Re: Any references for efficient division code sequences? David.Chase@naturalbridge.com (David Chase) (2001-07-03) |

Re: Any references for efficient division code sequences? kadiyala@home.com (Suresh Kadiyala) (2001-07-17) |

From: | torbenm@diku.dk (Torben AEgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | 2 Jul 2001 00:30:20 -0400 |

Organization: | Department of Computer Science, U of Copenhagen |

References: | 01-06-060 |

Keywords: | arithmetic |

Posted-Date: | 02 Jul 2001 00:30:20 EDT |

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)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.