Fri, 3 Apr 1992 14:04:06 GMT

Related articles |
---|

Is there a way of generating code for x/const without division? jeremy@sw.oz.au (1992-04-02) |

Re: Is there a way of generating code for x/const without division? suitti@ima.isc.com (1992-04-03) |

Re: Is there a way of generating code for x/const without division? moss@cs.umass.edu (1992-04-03) |

Re: Is there a way of generating code for x/const without division? markt@harlqn.co.uk (1992-04-08) |

Re: Is there a way of generating code for x/const without division? haddad@pa.dec.com (1992-04-07) |

Newsgroups: | comp.compilers,comp.arch |

From: | moss@cs.umass.edu (Eliot Moss) |

Followup-To: | comp.compilers |

Keywords: | optimize, arithmetic |

Organization: | Dept of Comp and Info Sci, Univ of Mass (Amherst) |

References: | 92-04-018 |

Date: | Fri, 3 Apr 1992 14:04:06 GMT |

The question was: if one is dividing by a constant or taking modulus by a

constant, might one do better than using a general divid instruction,

analogous to doing some shifts and adds to replace a multiply? The answer,

of course, is "yes, but the advisability depends a lot on the

architecture". In fact, there was recent discussion in one of the news

group (I think it was comp.arch, but it might have been comp.compilers) of

the divide track. Basically, one replaces the division by multiplication

times the inverse. Suppose we have 32 bit words and a multiply that can

generate a 64 bit result. Then we can compute an inverse that has the

binary point at the high end of the word (this binary point is "in our

mind") and when we multiply, the high order word has the integer part and

the low order word the fraction. Careful calculation of the inverse value

will allow you to use the high order half as the result directly (i.e., no

rounding or adjustment required). Similarly, if we know the values are

bounded by say, 16 bits, we can carry all of this out using a multiply

that produces a 32 bit rather than 64 bit result. And finally (whew!) that

multiply could be done by shifts and adds. Whether or not this is

*profitable* depends strongly on the relative speeds of divide, multiply,

shift, add, etc., *and* on the constant value involved.

Concerning modulus, there are all kinds of tricks if the constant is

special. Most compilers will mask if the constant is a power of two, for

example. If the constant is close to a power of two (e.g., +/- 1 from a

power of two), then repeated shifting, adding/subtracting, and maybe some

masking, will do the trick (if you learned it in school, mod 2^n-1 works

like "casting out nines" does in base 10).

Perhaps other respondents can provide citations in the literature that go

beyond my blathering .....

--

J. Eliot B. Moss, Assistant Professor

Department of Computer Science

Lederle Graduate Research Center

University of Massachusetts

Amherst, MA 01003

(413) 545-4206, 545-1249 (fax); Moss@cs.umass.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.