Tue, 14 Sep 2010 22:27:16 -0400

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: | Paul Khuong <pvk@pvk.ca> |

Newsgroups: | comp.compilers |

Date: | Tue, 14 Sep 2010 22:27:16 -0400 |

Organization: | A noiseless patient Spider |

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

Keywords: | arithmetic, code |

Posted-Date: | 15 Sep 2010 00:04:57 EDT |

"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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.