Wed, 15 Sep 2010 02:49:51 +0000 (UTC)

Related articles |
---|

Divide-by-multiply algorithm reference needed newcomer@flounder.com (Joseph M. Newcomer) (2010-09-13) |

Re: Divide-by-multiply algorithm reference needed rsc@swtch.com (Russ Cox) (2010-09-13) |

Re: Divide-by-multiply algorithm reference needed gah@ugcs.caltech.edu (glen herrmannsfeldt) (2010-09-14) |

Re: Divide-by-multiply algorithm reference needed newcomer@flounder.com (Joseph M. Newcomer) (2010-09-14) |

Re: Divide-by-multiply algorithm reference needed newcomer@flounder.com (Joseph M. Newcomer) (2010-09-14) |

Re: Divide-by-multiply algorithm reference needed pvk@pvk.ca (Paul Khuong) (2010-09-14) |

Re: Divide-by-multiply algorithm reference needed gah@ugcs.caltech.edu (glen herrmannsfeldt) (2010-09-15) |

From: | glen herrmannsfeldt <gah@ugcs.caltech.edu> |

Newsgroups: | comp.compilers |

Date: | Wed, 15 Sep 2010 02:49:51 +0000 (UTC) |

Organization: | Aioe.org NNTP Server |

References: | 10-09-013 10-09-015 10-09-016 |

Keywords: | arithmetic, code |

Posted-Date: | 15 Sep 2010 00:05:24 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.