 # 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:
• 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.

## Proposal

I propose the following features be added to Rational:
• 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

## 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
#
# 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
#
#
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
#
#
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
``` 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.
• 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  