Re: Divide-by-multiply algorithm reference needed

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

Return to the comp.compilers page.
Search the comp.compilers archives again.