Modern Electronics (was Re: List charter mods & headcount... ;

Michael> Paul Koning <pkoning(a)equallogic.com> wrote: 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