Tue, 14 Sep 2010 03:51:30 +0000 (UTC)

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: | glen herrmannsfeldt <gah@ugcs.caltech.edu> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.