Re: Is there a way of generating code for x/const without division?

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


--

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