>>>>> "Michael" == Michael Sokolov <msokolov_at_ivan.harhan.org> writes:
Michael> Paul Koning <pkoning_at_equallogic.com> wrote:
>> Then there are special cases: the Cray and Alpha integer units,
>> which don't offer divide at all. Instead, you're supposed to
>> multiply by the reciprocal of the divisor.
Michael> Ahmm, but the reciprocal of an integer is not an integer, so
Michael> you are stepping out of integer-land into floating point
Michael> territory. Do you really want to use floating point to
Michael> implement integer division (dividing an integer by an
Michael> integer to get quotient and remainder)? And how do you
Michael> guarantee that the final integer result will be exact? (I
Michael> guess you convert the dividend to a float, get the
Michael> reciprocal of the divisor, which will be a float, do float
Michael> multiplication, and integerise the result, right? Are there
Michael> enough bits of precision in a float to guarantee an exact
Michael> result for integer division done this way? I doubt that,
Michael> since AFAIK Alpha has usual 32-bit and 64-bit floats, which
Michael> have other things besides mantissa in those bits, but has
Michael> 64-bit integers.) And how do you get the remainder?
Michael> Floating division (whether direct or via multiplication by
Michael> the reciprocal) doesn't produce a remainder at all.
That's not how it works.
This stuff relies on the availability of an "extended multiply" -- one
that produces a result twice the size of the operands. More
specifically, you need the upper half.
For example, say you have 32 bit ints. You calculate the reciprocal
of the divisor times 2^32, converted to an integer. You multiply and
pick up the upper 32 bits of the 64 bit result.
You can demonstrate that this produces the exact result for divisors
within a certain range (I do not know the details). So this provides
a way to do exact division that's fast for most divisors, and slow for
those where the reciprocal method isn't exact (if any).
As for the remainder -- that's trivial:
x % y == x - (x /y) * y
which can be implemented with reciprocal multiply and come out faster
than the simple division approach.
paul
Received on Fri Jun 25 2004 - 11:01:34 BST