Tue, 14 Sep 2010 16:47:33 -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: | "Joseph M. Newcomer" <newcomer@flounder.com> |

Newsgroups: | comp.compilers |

Date: | Tue, 14 Sep 2010 16:47:33 -0400 |

Organization: | NewsGuy - Unlimited Usenet $19.95 |

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

Keywords: | arithmetic, code |

Posted-Date: | 14 Sep 2010 21:37:05 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.