Re: Divide-by-multiply algorithm reference needed

"Joseph M. Newcomer" <newcomer@flounder.com>
Tue, 14 Sep 2010 16:47:33 -0400

          From comp.compilers

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)
| List of all articles for this month |

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.