[ruby-core:31376] [Bug #3589] Converting Bignums to Float for equality checks is wrong

Bug #3589: Converting Bignums to Float for equality checks is wrong
http://redmine.ruby-lang.org/issues/show/3589

Author: Tomasz Wegrzanowski
Status: Open, Priority: Normal
ruby -v: ruby 1.9.1p429 (2010-07-02 revision 28523) [i386-darwin9]

In all versions of Ruby, when comparing Bignums with Floats, Bignum get converted to Floats first. This naturally results in wrong results, as this conversion is lossy. Not only will some unequal number be reported as equal, transitivity of equality gets broken:

big    = 10**20
bigger = big+1
flt    = big.to_f 
[big == bigger, big == flt, bigger == flt] #=> [false, true, true]

Ruby is so close to getting equality right, it would be a shame not to get it totally right. And it's not Float's fault - IEEE 754 defines correct results of all Float operations to the last bit, and all rounding and comparisons between Floats happens with what is mathematically equivalent to infinite precision.

= Solution 1 =

Now I could be missing something, but it seems to be that it's all as simple as:
* perform equality / comparison check like now with bignum.to_f and float
* if they're not equal so far, direction of inequality is correct
* compare bignum with float.to_i


As both Float <=> Float, and Bignum <=> Bignum are exact to the last bit (ignoring issues like -0.0 etc. - they're not relevant here), this means roundtrip conversion is identity, and there can exist no other Float that would be equal to this particular Bignum, and no other Bignum that would be equal to this particular Float. It also seems to me that they'd need to be mathematically equal for that unless I miss something big.

The first check ensures all fractional bits are correct (that is if flt has any it will fail as convertion of integer to float is guaranteed not to generate any). The second check ensures that all integer bits are correct (that is every bit exceeding limit of float representation is 0, as correct float to integer conversion is guaranteed not to geterate any there)

This leads where we want:
[bigger.to_f == flt, bigger == flt.to_i]
=> [true, false]


Some pictures:
* Huge BigNum XXXXXXXXXXXXXXXYYYYYYYYYYY.00000000000000
* Huge Float  XXXXXXXXXXXXXXX00000000000.00000000000000
* Small BigNum  XXXXXXX.000000000000000
* Small Float   XXXXXXX.YYYYYYYYY000000

0s are bits that cannot be represented, Xs bits represented by both, Ys bits represented in only one. Someone should double check with all the rounding etc. but it seems to that it's impossible for Ys to exist in both, if they're nearly equal.

= Solution 2 =

A completely different solution would be converting BigNum to Float with hardware (it's already universally supported, even if standard C tends to ignore it) in two modes - round up and round down (starting from low bits) - they will be the same or differ by 1ulp - so its impossible for the compared float to be between them. If bignum.to_f_up > flt, it's >. If bignum.to_f_down < flt, it's <. If they're all three equal, they're really ==.


----------------------------------------
http://redmine.ruby-lang.org