Re: Divide-by-multiply algorithm reference needed

> 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

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