ruby picture

RCR 320: Extend Rational to interoperate better with floats

Submitted by dburt (Tue Oct 11 00:47:36 UTC 2005)

Abstract

Converting a real number like 0.1 or 1/3 to a Rational is a fairly common problem if you want to use rational numbers in Ruby, but Rational doesn't provide this kind of interoperability, limiting its domain to Integers.

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)).

Problem

Rational, Ruby's accurate numbers, are missing:

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.

Proposal

I propose the following features be added to Rational:

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

Analysis

Rational is part of the standard library. It's Ruby's standard solution for representing all rational numbers.

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)

Implementation

 #
 # 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
ruby picture
Comments Current voting
You are proposing way too much in one RCR. An RCR should be very simple. I agree with a little bit of this but most of it I disagree with.


What bits do you like? What bits don't you like? Why? -- Dave Burt


The main thing I dislike is this RCR is too complex for a single proposal. I see several proposals:

  • convert from Float to Rational

  • convert from String to Rational

  • various aliasing of these conversions to other places

  • other miscellaneous Rational stuff

Here are a few things I don't like:

  • overloaded methods. I don't like this in general because it inhibits the polymorphism that normal duck-typing give you.

  • why should Rational.from_s handle floats in the numerator and denominator? To me, it only needs to handle what #to_s generates and a simple integer.

  • Rational.from_f should go ahead and do "approximate". A Float has an error of the LSB of the mantissa. You are assuming the Float is exact when converting it - forcing the denominator to be a power of 2. from_f should be multiplying the denominator by various numbers (at least small primes), not just 2. I gave a solution on ruby-talk at one time.

I do like that you are using Rational.from_* methods like my RCR. It promotes better encapsulation in addition to more flexibility if it was done elswhere. I do like the idea of having conversions from Float and String to Rational.

- Eric


Eric, thanks for the response. To your objections:
  • That the RCR is too large:
    • This RCR is about conversion from floats. Conversion from string is provided primarily to support this: consider Rational(1.3.to_s). Approximation is also a supporting tool for the same function.
  • That the various conversions are separate issues:
    • Rational() and to_r are already standard, and this RCR just changes these to fit the above goals. Rational.from_* are an implementation detail that would ideally be hidden, but I don't know how to hide a method so that Kernel.Rational() can still use it.
  • That I include other miscellaneous stuff:
    • Yes - to_s, hash and inv are separate issues.
  • Overloaded methods:
    • What overloaded methods?
  • That from_s shouldn't handle floats:
    • It's simple, unambiguous, and it's useful for the core aim here of converting from floats. Rational(1.3.to_s). I believe the implentation is simpler than allowing "1/2" and "1.2e3" but disallowing "1.2/3.4".
  • That from_f should approximate:
    • I think it's important that from_f be reversible by to_f. Your solution (ruby-talk:141388) only seems to work for numbers with small denominators. For automatic approximation, I think it would be important to consistently return the rational with the least denominator closer to the given float than any other. You'd have to calculate the significance of the LSB.

from_s and from_f exist because Rational() needs to perform both of these non-trivial operations, and Float and String's to_r can be defined in terms of Rational(), but not the other way around. Ideally, they would not be part of the public interface. I've moved their documentation to Rational().

This RCR is about conversions from float (and string) to rational.


What I mean by overloading is the same "overloading" functionality you get in java - where one method can have different functionalities depending on "type". In java you simply give multiple definitions for the same method and in ruby you have a case statement or some conditional based on "type" to do it. This clashes with the duck-typing concepts. I know this overloading (based on type) is done all over the ruby core. I would hope additional overloading could be minimized.


But it's a validating type-cast method -- it needs to accept objects of different types! And it's consistent: it's Rational(numerator, denominator), where denominator is optional and defaults to 1. Makes sense to me.


I know many disagree with me, but I just don't think type-based overloading is appropriate for ruby. You should just use multiple methods instead. I don't have a problem with other kinds of overloading (based on number of args, existence of block, arg flags, arbitrary non type-based condition of an arg, etc). I think the only value that overloading gives you is fewer method names to remember.


Strongly opposed 0
Opposed 1
Neutral 0
In favor 1
Strongly advocate 1
ruby picture
If you have registered at RCRchive, you may now sign in below. If you have not registered, you may sign up for a username and password. Registering enables you to submit new RCRs, and vote and leave comments on existing RCRs.
Your username:
Your password:

ruby picture

Powered by .