Re: Divide-by-multiply algorithm reference needed

>> 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.


(Example: I compute an inverse for /5 as 33333334h. But Microsoft C++
uses 66666667h, followed by a shr of the result. Is there a deep and
meaningful reason for this? I would like to know what I missed by
using 33333334, other than an issue of normalization; but at first I
thought they were normalizing so the high-order bit was 0, but then
other inverse multiplicative values are negative (well, unsigned) with
the h/o bit set, so I am left confused as to why my algorithm which I
worked out from the basic arithmetic properties produces a different
result than the compiler, or what the normalization algorithm might be
for the binary fraction)


Assume that the basis of my question is a desire to teach the compiler
technology, so I need to explain to the students why the apparently
correct algorithm produces a different result than the compiler uses.


joe
Joseph M. Newcomer [MVP]
email: newcomer@flounder.com
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm

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