Re: rational to floating point?

[Followup to comp.arch.arithmetic]


Thant Tessman <thant@acm.org> writes:
>Can anyone recommend a source of information on converting
>arbitrary-precision rationals to floating-point numbers? I'm sure I
>could make something work, but doing it accurately, efficiently, and
>portably seems a little tricky. Google turns up lots of man pages of
>languages that support the capability, but a description of *how* they
>do it is harder to unearth.




Assume the input is x = n/d where n, d are positive integers (if you
can handle this case, you can handle negative and zero inputs too).
Assume you want a b-bit mantissa for your floating point output.


          Find an exponent e such that 2^(e-1) <= n/d < 2^e
This e is approximately LOG2(n) - LOG2(d) where LOG2
denotes the truncated base-2 logarithm.


          Let n1/d1 = (n/d)*2^(b - e).
The simple way to multiply by 2^(b-e) multiplies the numerator of n/d
by 2^(b-e) when b >= e, and multiplies the denominator of n/d
by 2^(e-b) when b < e. A more sophisticated algorithm
ensures the new n1 and d1 are not both even.


        We observe that 2^(b-1) <= n1/d1 < 2^b.
Carry out the integer division n1 div d1,
getting quotient q and remainder r.


        For round toward zero, or if the remainder r is zero,
answer is q*2^(e-b). You should check whether
the exponent is too large (overflow) for floating point arithmetic.


        For round toward +infinity, answer is (q+1)*2^(e-b).
Be aware that q+1 may overflow to 2^b, requiring an exponent adjustment.


        For round to nearest, with round to even in case of a tie,
compare r to d1/2. More precisely,


                If q is even, then round down if r <= d1 - r, up if r > d1 - r.


                If q is odd, then round down if r < d1 - r, up if r >= d1 - r.
--
                Peter-Lawrence.Montgomery@cwi.nl Home: San Rafael, California
                Microsoft Research and CWI

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