Re: Integer division

dz <drizzle76@gmail.com> wrote:


> I am looking for references on how to support general 32 bit
> integer division (not just invariants) on hardware without dedicated
> integer-division support and 64 bit floating point support.


Well, there is always the shift/subtract loop generating
one bit at a time. Either the restoring or non-restoring
division algorithm should be easy to find. Many processors without
hardware divide have instruction to make this easier, such as
rotate and rotate through carry.


> However
> there is 32 bit floating point support and dedicated hardware to
> support 32 bit math functions such as logarithm and exponential. Can
> someone please point me to references. I realize this question has
> been asked before but they seemed to pertain to invariant
> denominators. And invariant perhaps refers to constants...


> [I'd look in Knuth's "Seminumerical Algorithms" where he explains it all.
> -John]


That is the reference I would have given, too. The more usual problem
is, given an N bit divide instruction, and N bit multiply, and, and
subtract, do a 2N bit divide. Using the 32 bit floating point
hardware, you should be able to do a 20 or so bit divide, then use the
algorithms in Knuth to extend that to 32 bits.


For constants, you can usually find the appropriate N bit constant
such that when multiplied generating a 2N bit product, the appropriate
quotient appears in the high half of the product. Many compilers will
do this for division by constants. That doesn't help so much when the
divisor is variable.


-- glen

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