Mon, 13 Sep 2010 23:31:32 -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: | Russ Cox <rsc@swtch.com> |

Newsgroups: | comp.compilers |

Date: | Mon, 13 Sep 2010 23:31:32 -0400 |

Organization: | Compilers Central |

References: | 10-09-013 |

Keywords: | arithmetic, code |

Posted-Date: | 13 Sep 2010 23:59:34 EDT |

*> 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. B I am unable to find any references via google. B Any*

*> recommendations? B No, I really don't want to read the gcc source (even*

*> if it does this) unless someone knows the specific subroutine name I*

*> should be looking at.*

Alverson, Integer Division Using Reciprocals (1991)

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1710

Granlund and Montgomery, Division by Invariant Integers Using

Multiplication (1994)

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.2556

Warren, Hackers Delight, Chapter 10 (2003)

http://www.hackersdelight.org/

http://www.hackersdelight.org/magic.htm

http://www.hackersdelight.org/HDcode.htm

I don't know about gcc but here is an implementation in the

Go compiler. The routines are smagic and umagic for

signed and unsigned.

http://code.google.com/p/go/source/browse/src/cmd/gc/subr.c?r=release.2010-09

-06#3399

Russ

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.