Yitzchak Gale gale at sefer.org
Thu Feb 5 05:52:11 EST 2009

Manlio Perillo wrote:
>> I'm looking for an exact integer division that avoids overflows, if
>> possible.

Richard O'Keefe wrote:
> What this sounds like to me is a request that the Prelude
> function 'fromRational' should work well...
> If you cannot divide two Integers n, d accurately using
>   (fromRational (n Ratio.% d) :: Double)
> that casts doubt on the trustworthiness of floating point literals.

No, that works fine:

Prelude Data.Ratio> fromRational \$ (3*10^1000)%(2*10^1000+1)
1.5

> Suppose we have a function
>    decodeIntegerAsFloat :: RealFloat a => Integer -> (Integer,a)
> such that if (s,m) = decodeIntegerAsFloat x
> then either x = 0 and s = 0 and m = 0
>         or x = m * 2**s (mathematically) and abs m \in [0.5,1.0).

Yes, that is what Manlio wants. Sometimes you need to divide
two very large Integers with a floating point number as result,
without the overhead of constructing a Rational from them.

> Then
>    integer_ratio_as_float :: Floating a => Integer -> Integer -> a
>    integer_ratio_as_float p q = (mp/mq)*(2.0^(sp-sq))
>        where (sp,mp) = decodeIntegerAsFloat p
>              (sq,mq) = decodeIntegerAsFloat q
>
> You'd actually use scaleFloat; if the difference sp-sq is outside
> the range of Int the answer is going to be a signed zero or a signed
> infinity anyway.

You have just duplicated the CPython interpreter source code

> decodeIntegerAsFloat would sit very well in the
> RealFloat class alongside its model, decodeFloat.  It has other uses.

I agree, though I'm not sure it needs to be a method.

> For example, you can use it to compute logarithms of Integers with
> much less worry about overflow.

Actually, efficient integer-valued logarithms for Integers are exactly
what you need to implement decodeIntegerAsFloat.

Best would be if we could just read that off from the internal
representation of an Integer. Would you like to file a GHC
issue for that?

In the meantime, we could already expose the integer log function
in a library using an efficient algorithm.

Thanks,
Yitz