Project

General

Profile

Actions

Bug #3589

closed

Converting Bignums to Float for equality checks is wrong

Added by taw (Tomasz Wegrzanowski) over 13 years ago. Updated almost 12 years ago.

Status:
Closed
Target version:
ruby -v:
ruby 1.9.1p429 (2010-07-02 revision 28523) [i386-darwin9]
Backport:
[ruby-core:31376]

Description

=begin
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 ==.
=end

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0