# Re: Divide-by-multiply algorithm reference needed

## glen herrmannsfeldt <gah@ugcs.caltech.edu>Tue, 14 Sep 2010 03:51:30 +0000 (UTC)

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: glen herrmannsfeldt Newsgroups: comp.compilers Date: Tue, 14 Sep 2010 03:51:30 +0000 (UTC) Organization: Aioe.org NNTP Server References: 10-09-013 Keywords: arithmetic, code Posted-Date: 13 Sep 2010 23:59:53 EDT

Joseph M. Newcomer <newcomer@flounder.com> wrote:
> Division can be approximated with multiprecision multiplication, e.g.,
> 32-bit division can be done by producing the appropriate 64-bit
> product and using the high order 32 bits.

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

It gets a little complicated to get the exact truncated answer, but...

If you multiply a 32 bit number, n, by 2**32/d then the high 32 bits
of the 64 bit product are n/d. That works if the divisor is less
than one half.

Remember the rules you learned in 3rd grade. Multiply the number, the
digits after the radix point in the product is the sum of the digits
after the radix point in the numbers being multiplied.

I believe that in some cases the rounding is different, though I
haven't tried to find out those cases. Also, you might need to round
2*32/d to get the right result. That is, though, the basic idea.

-- glen

Post a followup to this message