From: Dave Burt <dave@...>
Date: 2005-05-11T23:35:27+09:00
Subject: Standard Library patches - rational, delegate

Hi,

I have two small things I would like to see changed in the standard library:
delegate.rb
rational.rb

I would like to hear from the list:
* how this might happen
* any comments on my changes

The first is a small change to Delegate to prevent infinite recursion from 
occurring when an object is assigned to delegate to itself.

The second are some enhancements to Rational, mainly to make it more 
friendly with Floats and Strings, allowing rationals to be made like 
Rational("2/3"), Rational("1.2e-10"), Rational(0.5), as well as adding to_r 
methods to String and Float.
I've added approximation methods (similar to those recently discussed), 
which are useful when trying to reduce an approximate Float to its original 
representation, like this:
1.6.to_r  #=> Rational(3602879701896397, 2251799813685248)
1.6.to_r.approximate  #=> Rational(8, 5)
I've also fixed to_f so that it doesn't return NaN for rationals with large 
denominators, and added radix selection in to_s like Integers have.

Thanks,
Dave


>diff -u delegate.rb.bak delegate.rb
--- delegate.rb.bak     Thu May 12 00:16:14 2005
+++ delegate.rb Thu May 12 00:16:17 2005
@@ -73,7 +73,7 @@
   end

   def __setobj__(obj)
-    @_sd_obj = obj
+    @_sd_obj = obj unless eql?(obj)
   end

   def clone
@@ -110,7 +110,7 @@
       @_dc_obj
     end
     def __setobj__(obj)
-      @_dc_obj = obj
+      @_dc_obj = obj unless eql?(obj)
     end
     def clone
       super


>diff -u rational.rb.bak rational.rb
--- rational.rb.bak     Fri May 07 17:48:23 2004
+++ rational.rb Wed May 11 23:48:15 2005
@@ -10,7 +10,7 @@
 #   class Rational < Numeric
 #      (include Comparable)
 #
-#   Rational(a, b) --> a/b
+#   Rational(n, d=1) --> n/d
 #
 #   Rational::+
 #   Rational::-
@@ -23,13 +23,19 @@
 #   Rational::<=>
 #   Rational::to_i
 #   Rational::to_f
-#   Rational::to_s
+#   Rational::to_s(base=10)
+#   Rational::trim(max_d)
+#   Rational::approximate(err=1e-12)
+#   Rational::inv
 #
 #   Integer::gcd
 #   Integer::lcm
 #   Integer::gcdlcm
 #   Integer::to_r
 #
+#   Float::to_r
+#   String::to_r
+#
 #   Fixnum::**
 #   Fixnum::quo
 #   Bignum::**
@@ -37,11 +43,36 @@
 #

 def Rational(a, b = 1)
-  if a.kind_of?(Rational) && b == 1
-    a
-  else
+  if b == 1
+    case a
+    when Rational
+      a
+    when String
+      case a
+      when /\//
+        n, d = a.split('/', 2)
+        Rational(n) / Rational(d)
+      when /e/
+        mant, exp = a.split('e', 2)
+        Rational(mant) * (10 ** Integer(exp))
+      when /\./
+        i, f = a.split('.', 2)
+        Rational(Integer(i)) + Rational(Integer(f), 10 ** f.length)
+      else
+        Rational(Integer(a))
+      end
+     when Float
+       a.to_r
+     when Integer
+       Rational.new!(a)
+    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: #{num.inspect}")
 end

 class Rational < Numeric
@@ -237,17 +268,79 @@
   end

   def to_f
-    @numerator.to_f/@denominator.to_f
+    r = if @denominator > (1 << 1022)
+      self.trim(1 << 1022)
+    else
+      self
+    end
+    r.numerator.to_f / r.denominator.to_f
   end

-  def to_s
+  def to_s(base = 10)
     if @denominator == 1
-      @numerator.to_s
+      @numerator.to_s(base)
     else
-      @numerator.to_s+"/"+@denominator.to_s
+      @numerator.to_s(base) + "/" + @denominator.to_s(base)
+    end
+  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
+    p "mod==0" if mod == 0
+    app
+  end
+
+  # Return the inverse
+  def inv
+    Rational(@denominator, @numerator)
+  end
+
   def to_r
     self
   end
@@ -257,7 +350,7 @@
   end

   def hash
-    @numerator.hash ^ @denominator.hash
+    @numerator.hash ^ @denominator.hash ^ 1.hash
   end

   attr :numerator
@@ -326,6 +419,75 @@
     return gcd, (a.div(gcd)) * b
   end

+end
+
+class Float
+  #  Return Rational(top, bot), where top and bot are a pair of co-prime
+  #  integers such that x = top/bot.
+  #
+  #  The conversion is done exactly, without rounding.
+  #  bot > 0 guaranteed.
+  #  Some form of binary fp is assumed.
+  #  Pass NaNs or infinities at your own risk.
+  #
+  #  >>> rational(10.0)
+  #  rational(10L, 1L)
+  #  >>> rational(0.0)
+  #  rational(0L)
+  #  >>> rational(-.25)
+  #  rational(-1L, 4L)
+  def to_r
+    x = self
+
+    if x == 0.0
+      return Rational(0, 1)
+    end
+    signbit = false
+    if x < 0
+      x = -x
+      signbit = true
+    end
+    f, e = Math.frexp(x)
+    raise unless 0.5 <= f and f < 1.0
+    # 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
+    top = 0
+    # invariant: x = (top + f) * 2**e exactly
+    while f > 0.0
+      f = Math.ldexp(f, chunk)
+      digit = f.to_i
+      raise unless digit >> chunk == 0
+      top = (top << chunk) | digit
+      f = f - digit
+      raise unless 0.0 <= f and f < 1.0
+      e = e - chunk
+    end
+    raise if top == 0
+
+    # now x = top * 2**e exactly; fold in 2**e
+    r = Rational(top, 1)
+    if e > 0
+      r *= 2**e
+    else
+      r /= 2**-e
+    end
+    if signbit
+      -r
+    else
+      r
+    end
+  end
+end # class Float
+
+class String
+  # Convert to Rational, returning Rational(0) if it's can't be converted
+  def to_r
+    Rational(self) rescue Rational(0)
+  end
 end

 class Fixnum