RCR 320: Extend Rational to interoperate better with floats

The proposed solution allows Floats, Strings and BigDecimals to be passed to Rational(), adds a to_r method to String and Float, and adds reduction methods to Rational (trim(max_denominator) and approximate(max_err)).

• a way to create a Rational from a String
• a way to create a Rational from a Float
• a way to approximately simplify (reduce the denominator of) a Rational (e.g. 9999/20000 => 1/2, 0.1 => 1/10)

Also Rational#to_f should not return NaN for Rationals with large numerators and denominators, as happens now if the numerator and denominator are not both convertible to Float.

• Rational() should accept strings (e.g. "0.1") and floats
• Float#to_r should return a Rational that's equal in value to self, or 0 if self is NaN or Infinity. Note: 0.1 == 0.1.to_r == Rational(3602879701896397, 36028797018963968)
• String#to_r, for strings that look like integer or float literals with an optional "/" to separate a numerator from a denominator, should return the equivalent Rational. 0 should be returned on failure.
• Rational#trim(max_denominator) should return the Rational closest to self whose denominator is at most max_denominator.
• Rational#approximate(err) should return the Rational with the smallest denominator whose value differs from self by at most err. The parameter should have a default that is sensible for removing the extraneous part of a Rational created from a Float: 0.1.to_r.approximate #=> Rational(1, 10)
• Rational#to_f should not return NaN for Rationals with large numerators and denominators.

Additionally, the following minor changes are included in the implementation below:

• Rational#to_s should accept a radix, and use it in the same manner as Integer#to_s
• Rational#hash should return numerator.hash if the denominator is 1
• Rational#inv should return the reciprocal of self

These are backwards-compatible changes that add needed functionality to the Rational class, allowing interoperability with Float.

Some people would expect that 0.1 would convert to Rational(1, 10); for some cases, that type of approximate conversion is needed. The best way to deal with this unambiguously is to always convert exactly by default, but to also provide approximation methods:

  0.1.to_r #=> Rational(3602879701896397, 36028797018963968)
  0.1.to_r.approximate #=> Rational(1, 10)

Here is some of what this RCR allows:

  # Rational() is backwards-compatible
  Rational(1)  #=> Rational(1, 1)
  Rational(1, 2)  #=> Rational(1, 2)
  # ... but also accepts floats
  Rational(1.3)  #=> Rational(5854679515581645, 4503599627370496)
  # ... and strings
  Rational("1.3")  #=> Rational(13, 10)
  Rational("1.2e-3")  #=> Rational(3, 2500)
  Rational("1/2")  #=> Rational(1, 2)
  Rational("1.5/2.3")  #=> Rational(15, 23)
  Rational("1.5", "2.3")  #=> Rational(15, 23)
  # Floats and strings have an explicit cast to_r method
  "1.5/2.3".to_r  #=> Rational(15, 23)
  -0.25.to_r  #=> Rational(-1, 4)
  # You can get fractions back from the floats:
  Rational(1.3).approximate  #=> Rational(13, 10)
  Rational(0.3333333333333).approximate  #=> Rational(1, 3)

 #
 # An extension to Ruby's standard Rational library
 #
 # Includes conversions from String and Float, inversion, reduction methods
 # (trim and approximate), and a to_s with a base conversion parameter.
 #
 # A bunch of this code is taken from the Python project:
 #   http://cvs.sourceforge.net/viewcvs.py/python/python/nondist/sandbox
 #   /rational/Rational.py?rev=1.3&view=markup
 #
 # Author: Dave Burt <dave at burt.id.au>
 # Created: 5 May 2005
 # Last modified: 11 Oct 2005
 #
 # Methods:
 #
 # Rational(n, d = 1)           # replaced - now accepts Floats and Strings
 #                              # like Rational(1.3e15) or Rational("4/5")
 #
 # Rational#to_s(n = 10)        # replaced - now accepts a radix
 # Rational#to_f                # replaced - doesn't return NaN any more
 # Rational#hash                # replaced - r.hash==r.to_i.hash if r==r.to_i
 # Rational#trim(max_d)         # simplify approximately, set max denominator
 # Rational#approximate(err = 1e-12)  # simplify approximately, within +/-err
 # Rational#inv                 # invert
 #
 # Rational::from_f(f)  # use Rational(f)
 # Rational::from_s(s)  # use Rational(s)
 #
 # Float#to_r   # converts to Rational, exactly
 # String#to_r  # converts to Rational if possible, or returns Rational(0)
 #
 require 'rational'
 #
 # This improved Rational() handles Floats and Strings, so you can do
 # +Rational(1.3e15)+ and +Rational("2/3")+
 #
 ##alias std_Rational Rational
 def Rational(a, b = 1)
   if b == 1
     case a
     when Rational
       a
     when String
       Rational.from_s(a)
     when Integer
       Rational.new!(a)
     when Float
       Rational.from_f(a)
     when BigDecimal
       a.to_r
     else
       raise ArgumentError
     end
   elsif a.kind_of?(Integer) and b.kind_of?(Integer)
     Rational.reduce(a, b)
   else
     Rational(a) / Rational(b)
   end
 rescue ArgumentError
   raise ArgumentError.new("invalid value for Rational: #{a} / #{b}")
 end
 class Rational
   #
   # Cast to Float. This improved version won't return NaN for Rationals with
   # large numerators or denominators.
   #
   def to_f
     r = if @denominator > (1 << 1022)  # Where did the extra bit go?
       self.trim(1 << 1022)             # (Python handles 1 << 1023)
     else
       self
     end
     r.numerator.to_f / r.denominator.to_f
   end
   #
   # This hash function returns the same hash as the numerator itself if
   # the denominator is 1.
   #
   def hash
     @numerator.hash ^ @denominator.hash ^ 1.hash
   end
   #
   # Return the closest rational number such that the denominator is at most
   # +max_d+
   #
   def trim(max_d)
     n, d = @numerator, @denominator
     if max_d == 1
       return Rational(n/d, 1)
     end
     last_n, last_d = 0, 1
     current_n, current_d = 1, 0
     begin
       div, mod = n.divmod(d)
       n, d = d, mod
       before_last_n, before_last_d = last_n, last_d
       next_n = last_n + current_n * div
       next_d = last_d + current_d * div
       last_n, last_d = current_n, current_d
       current_n, current_d = next_n, next_d
     end until mod == 0 or current_d >= max_d
     if current_d == max_d
       return Rational(current_n, current_d)
     end
     i = (max_d - before_last_d) / last_d
     alternative_n = before_last_n + i*last_n
     alternative_d = before_last_d + i*last_d
     alternative = Rational(alternative_n, alternative_d)
     last = Rational(last_n, last_d)
     if (alternative - self).abs < (last - self).abs
       alternative
     else
       last
     end
   end
   #
   # Return the simplest rational number within +err+
   #
   def approximate(err = Rational(1, 1e12))
     r = self
     n, d = @numerator, @denominator
     last_n, last_d = 0, 1
     current_n, current_d = 1, 0
     begin
       div, mod = n.divmod(d)
       n, d = d, mod
       next_n = last_n + current_n * div
       next_d = last_d + current_d * div
       last_n, last_d = current_n, current_d
       current_n, current_d = next_n, next_d
       app = Rational(current_n, current_d)
     end until mod == 0 or (app - r).abs < err
     app
   end
   #
   # Return the inverse
   #
   def inv
     Rational(@denominator, @numerator)
   end
   #
   # Represent the fraction as a string, in the given base.
   #
   def to_s(base = 10)
     if @denominator == 1
       @numerator.to_s(base)
     else
       @numerator.to_s(base) + "/" + @denominator.to_s(base)
     end
   end
   class << self
     #
     # Use Rational(s) instead.
     #
     def from_s(s)
       unless s.respond_to?(:to_str)
         raise TypeError.new("#{s.inspect} is not a String") 
       end
       s = s.to_str
         case s
       when /\//
         n, d = s.split('/', 2)
         Rational(n) / Rational(d)
       when /e/
         mant, exp = s.split('e', 2)
         Rational(mant) * (10 ** Integer(exp))
       when /\./
         i, f = s.split('.', 2)
         Rational(Integer(i)) + Rational(Integer(f), 10 ** f.length)
       else
         Rational(Integer(s))
       end
     end
     #
     #  Use Rational(x) instead.
     #  
     def from_f(x)
       raise TypeError.new("#{x} is not a Float") unless x.kind_of?(Float)
       if x == 0.0
         return Rational(0, 1)
       end
       signbit =
         if x < 0
           x = -x
           true
         else
           false
         end
       f, e = Math.frexp(x)
       # for Infinity and NaN, frexp returns [NaN, -1]
       unless 0.5 <= f and f < 1.0
         raise ArgumentError("invalid value for Rational: #{self}") 
       end
       # x = f * 2**e exactly
       # Suck up chunk bits at a time; 28 is enough so that we suck
       # up all bits in 2 iterations for all known binary double-
       # precision formats, and small enough to fit in an int.
       chunk = 28
       num = 0
       # invariant: x = (num + f) * 2**e exactly
       while f > 0.0
         f = Math.ldexp(f, chunk)
         digit = f.to_i
         raise unless digit >> chunk == 0
         num = (num << chunk) | digit
         f = f - digit
         raise unless 0.0 <= f and f < 1.0
         e = e - chunk
       end
       raise if num == 0
       # now x = num * 2**e exactly; fold in 2**e
       r = Rational(num, 1)
       if e > 0
         r *= 2**e
       else
         r /= 2**-e
       end
       if signbit
         -r
       else
         r
       end
     end
   end
 end
 class Float
   #
   # Convert to Rational exactly, returning Rational(0) if float can't be
   # converted.
   #
   #  Return Rational(num, den), where num and den are a pair of co-prime
   #  integers such that x = num/den.
   #  
   #  The conversion is done exactly, without rounding. Use
   #  Rational#approximate to round.
   #
   #   "0.1".to_r  #=> Rational(1, 10)
   #   0.1.to_r  #=> Rational(3602879701896397, 36028797018963968)
   #   0.1.to_r.approximate  #=> Rational(1, 10)
   #
   def to_r
     Rational(self) rescue Rational(0)
   end
 end # class Float
 class String
   #
   # Convert the string into a Rational, returning Rational(0) if it
   # can't be converted.
   #
   # Valid strings are valid Integer or Float literals, and may also include
   # a slash (/) separating a numerator and denominator.
   #  "2/3".to_r      #=> Rational(2, 3)
   #  "1/1.2e2".to_r  #=> Rational(1, 120)
   #
   def to_r
     Rational(self) rescue Rational(0)
   end
 end
 if $0 == __FILE__
   # http://www.dave.burt.id.au/ruby/rational_ext_test.rb
   require 'rational_ext_test'
 end