Re: [boost] Re: rationals initialization bug

From: Lutz Kettner (kettner_at_[hidden])
Date: 2000-11-28 02:04:49

Hi,

> From: Paul Moore 
>
> I believe that mathematically, it is possible to view machine doubles as
> representing a series of discrete points on the mathematical real line. The
> problem I am looking to solve is to find the simplest rational (a
> well-defined concept) which is closer (in the absolute mathematical sense)
> to the supplied double than to any other value representable as a double. I
> believe this is calculable, and furthermore, I believe that there exist
> implementations of the algorithm. Unfortunately, I don't know of existing
> code, nor do I have the expertise to implement the algorithm from first
> principles.

I wonder if there is a misconception on my side. For me the 
"algorithm" of converting a float/double to a rational is simple
and easy, and it is exact except for overflow errors in num/denom. 
The rounding and approximation errors happen always when converting
towards doubles/floats. The rounding error in:

  rational<..> rat = 0.1;

happens when 0.1 gets scanned and converted to double, not when
the double gets converted to a rational.

The details are implementation dependent and might get a bit messy, I am 
not an expert there either. Details are things such as how many bits are
there in the mantissa and where are these bits in the type. Maybe there
is a standard header file already around capturing all this. IEEE floats
would make things already more predictable. Other details such as NaN 
and +-Inf have also to be considered (maybe raising an exception).

The actual conversion starts from the general representation of
floats in base 2 (which makes the conversion always exact. Of course
if there are machines out there using a decimal system for floats that 
would invalidate my above claim):

float_value = m * 2^e, where m is an integer mantissa and e an 
integer exponent. The float sign is usually stored separately. 
I assume m>0 now. e has a sign.

The conversion: 
    If e == 0, set rational to m/1
    If e >  0, set rational to (m*2^e)/1
    If e <  0, set rational to m/(2^(-e)) and shift num/denom to the right
        as long as both are even. That shifting factors out the gcd. The 
        shifting should be done before  assigning to the integer number 
        type to avoid unnecesary overflows if the integer type is smaller
        than the mantissa.

The *2^e and *2^(-e) operations are also just shifts.

I would welcome a conversion of float/doubles to rational. I am 
not sure if I have encouraged or discouraged (I hope not) with 
this email, 

Best regards,

Lutz Kettner 

----------------------------------------------------------------------
UNC Computer Science                       email: kettner_at_[hidden]
CB 3175, Sitterson Hall                    phone: [phone] x7759
Chapel Hill, NC 27599-3175, USA            fax:   [phone]
----------------------------------------------------------------------