25 Jun
2004
25 Jun
'04
6:47 a.m.
Paul Koning <pkoning(a)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.
Ahmm, but the reciprocal of an integer is not an integer, so you are
stepping out of integer-land into floating point territory. Do you
really want to use floating point to implement integer division
(dividing an integer by an integer to get quotient and remainder)?
And how do you guarantee that the final integer result will be exact?
(I guess you convert the dividend to a float, get the reciprocal of
the divisor, which will be a float, do float multiplication, and integerise
the result, right? Are there enough bits of precision in a float to
guarantee an exact result for integer division done this way? I
doubt that, since AFAIK Alpha has usual 32-bit and 64-bit floats,
which have other things besides mantissa in those bits, but has
64-bit integers.) And how do you get the remainder? Floating division
(whether direct or via multiplication by the reciprocal) doesn't produce
a remainder at all.
MS
25 Jun
25 Jun
7:01 a.m.
>>>> "Michael" == Michael Sokolov
<msokolov(a)ivan.harhan.org> writes:
Michael> Paul Koning <pkoning(a)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
7:13 a.m.
On Friday 25 June 2004 10:47, Michael Sokolov wrote:
Ahmm, but the reciprocal of an integer is not an
integer, so you are
stepping out of integer-land into floating point territory. Do you
really want to use floating point to implement integer division
(dividing an integer by an integer to get quotient and remainder)?
And how do you guarantee that the final integer result will be exact?
(I guess you convert the dividend to a float, get the reciprocal of
the divisor, which will be a float, do float multiplication, and
integerise the result, right? Are there enough bits of precision in
a float to guarantee an exact result for integer division done this
way? I doubt that, since AFAIK Alpha has usual 32-bit and 64-bit
floats, which have other things besides mantissa in those bits, but
has 64-bit integers.) And how do you get the remainder? Floating
division (whether direct or via multiplication by the reciprocal)
doesn't produce a remainder at all.
Well, if it's really an integer, you could use a fixed-point number for
the division (assume that the highest bit is the 2^(-1)bit or 2^0 if
you can get an extra bit). For this to work, you need to have access
to double the number of input bits to the multiplier for its output. I
remember seeing this before...either in my Sr. level architecture class
or the description of how my SBC-16/40 does division, neither of which
sounds right. I need to go back and figure out where I learned this
from.
Remainder is simply quotient - divisor*result, or drop the higher half
of the result and re-do the multiplication (and the resulting higher
half is the remainder).
Pat
--
Purdue University ITAP/RCS --- http://www.itap.purdue.edu/rcs/
The Computer Refuge --- http://computer-refuge.org
11:05 a.m.
> 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.
On Fri, 25 Jun 2004, Michael Sokolov wrote:
Ahmm, but the reciprocal of an integer is not an
integer, so you are
stepping out of integer-land into floating point territory. Do you
"Most important thing to know about doing floating point arithmetic:
DON'T."
really want to use floating point to implement integer
division
(dividing an integer by an integer to get quotient and remainder)?
And how do you guarantee that the final integer result will be exact?
(I guess you convert the dividend to a float, get the reciprocal of
the divisor, which will be a float, do float multiplication, and integerise
the result, right? Are there enough bits of precision in a float to
guarantee an exact result for integer division done this way? I
doubt that, since AFAIK Alpha has usual 32-bit and 64-bit floats,
which have other things besides mantissa in those bits, but has
64-bit integers.) And how do you get the remainder? Floating division
(whether direct or via multiplication by the reciprocal) doesn't produce
a remainder at all.
REMAINDER = NUMERATOR - ((int)QUOTIENT * DENOMINATOR) ;
which adds an otherwise unnecessary integer multiply and integer
subtraction.
7404
days inactive
7404
days old
3 comments
4 participants
participants (4)
-
cisin＠xenosoft.com -
msokolov＠ivan.Harhan.ORG -
pat＠computer-refuge.org -
pkoning＠equallogic.com