Re: Divide-by-multiply algorithm reference needed

  "Joseph M. Newcomer" <newcomer@flounder.com> wrote:
> >> My problem is I am trying to find the algorithm by which I can
> >> generate the 32-bit multiplier and the shift amount, given a specific
> >> constant divisor. ...
>
> Yes, that's the easy part. Now the hard part. In the Microsoft C
> compiler, the values they use are sometimes twice the values I
> compute, but then they throw in an additional shr instruction to
> divide the result by 2. Why? Why are my selections different from
> theirs? However, the previous message gave some citations, so I'm
> going to go look at those now.


AFAICT, the main reason for doing something like this is to maximise the
range of inputs for which the pseudoinverse will truncate to the right
value. I'm pretty sure that
<http://www.discontinuity.info/~pkhuong/pseudoinverse.pdf> derives a
tight bound for the range for which a given fixed-point multiplication
(which is what division-by-multiplication implements) always
approximates a constant (unsigned) division exactly.


Paul Khuong

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