Re: Divide-by-multiply algorithm reference needed

Joseph M. Newcomer <newcomer@flounder.com> wrote:
(snip)


> (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)


Rounding.


Try it with a loop over all positive integers, and compare
the result of the multiplication and integer (truncating) division.


In floating point, one normally want the appropriate rounded
result, though some systems give a truncated quotient instead.


For fixed point, many algorithms depend on the truncated result.
It isn't so easy to prove that multiplication by an appropriately
scaled reciprocal does or does not generate the appropriate quotient,
but it isn't hard to test it.


As many high-level languages now have a 64 bit datatype it isn't
hard to do the multiply in such languages and test.


As well as I remember it, for about half the possible divisors,
the obvious way works fine. Note that if the low bit of the
reciprocal is zero, then the shifted value gives the same result.


The differences should appear with larger dividends, especially
the ones near where the quotient changes value. For a divisor of 5,
the quotient changes every fifth dividend.


The largest 32 bit signed integer is 2147483647. The large ones
where the quotient changes are 2147483645 and 2147483644, where
the effect of the low bit of the multplier comes into play.


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


-- glen

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