Merged revisions 60481,60485,60489-60492,60494-60496,60498-60499,60501-60503,60505-60506,60508-60509,60523-60524,60532,60543,60545,60547-60548,60552,60554,60556-60559,60561-60562,60569,60571-60572,60574,60576-60583,60585-60586,60589,60591,60594-60595,60597-60598,60600-60601,60606-60612,60615,60617,60619-60621,60623-60625,60627-60629,60631,60633,60635,60647,60650,60652,60654,60656,60658-60659,60664-60666,60668-60670,60672,60676,60678,60680-60683,60685-60686,60688,60690,60692-60694,60697-60700,60705-60706,60708,60711,60714,60720,60724-60730,60732,60736,60742,60744,60746,60748,60750-60766,60769-60786 via svnmerge from

svn+ssh://pythondev@svn.python.org/python/trunk

........
  r60752 | mark.dickinson | 2008-02-12 22:31:59 +0100 (Tue, 12 Feb 2008) | 5 lines

  Implementation of Fraction.limit_denominator.

  Remove Fraction.to_continued_fraction and
  Fraction.from_continued_fraction
........
  r60754 | mark.dickinson | 2008-02-12 22:40:53 +0100 (Tue, 12 Feb 2008) | 3 lines

  Revert change in r60712:  turn alternate constructors back into
  classmethods instead of staticmethods.
........
  r60755 | mark.dickinson | 2008-02-12 22:46:54 +0100 (Tue, 12 Feb 2008) | 4 lines

  Replace R=fractions.Fraction with F=fractions.Fraction in
  test_fractions.py.  This should have been part of the name
  change from Rational to Fraction.
........
  r60758 | georg.brandl | 2008-02-13 08:20:22 +0100 (Wed, 13 Feb 2008) | 3 lines

  #2063: correct order of utime and stime in os.times()
  result on Windows.
........
  r60762 | jeffrey.yasskin | 2008-02-13 18:58:04 +0100 (Wed, 13 Feb 2008) | 7 lines

  Working on issue #1762: Brought
    ./python.exe -m timeit -s 'from fractions import Fraction; f = Fraction(3, 2)' 'isinstance(3, Fraction); isinstance(f, Fraction)'
  from 12.3 usec/loop to 3.44 usec/loop and
    ./python.exe -m timeit -s 'from fractions import Fraction' 'Fraction(3, 2)'
  from 48.8 usec to 23.6 usec by avoiding genexps and sets in __instancecheck__
  and inlining the common case from __subclasscheck__.
........
  r60765 | brett.cannon | 2008-02-13 20:15:44 +0100 (Wed, 13 Feb 2008) | 5 lines

  Fix --enable-universalsdk and its comment line so that zsh's flag completion
  works.

  Thanks to Jeroen Ruigrok van der Werven for the fix.
........
  r60771 | kurt.kaiser | 2008-02-14 01:08:55 +0100 (Thu, 14 Feb 2008) | 2 lines

  Bring NEWS.txt up to date from check-in msgs.
........
  r60772 | raymond.hettinger | 2008-02-14 02:08:02 +0100 (Thu, 14 Feb 2008) | 3 lines

  Update notes on Decimal.
........
  r60773 | raymond.hettinger | 2008-02-14 03:41:22 +0100 (Thu, 14 Feb 2008) | 1 line

  Fix decimal repr which should have used single quotes like other reprs.
........
  r60785 | jeffrey.yasskin | 2008-02-14 07:12:24 +0100 (Thu, 14 Feb 2008) | 11 lines

  Performance optimizations on Fraction's constructor.

    ./python.exe -m timeit -s 'from fractions import Fraction' 'Fraction(3)`
  31.7 usec/loop -> 9.2 usec/loop

    ./python.exe -m timeit -s 'from fractions import Fraction' 'Fraction(3, 2)'`
  27.7 usec/loop -> 9.32 usec/loop

    ./python.exe -m timeit -s 'from fractions import Fraction; f = Fraction(3, 2)' 'Fraction(f)'
  31.9 usec/loop -> 14.3 usec/loop
........
  r60786 | jeffrey.yasskin | 2008-02-14 08:49:25 +0100 (Thu, 14 Feb 2008) | 5 lines

  Change simple instances (in Fraction) of self.numerator and self.denominator to
  self._numerator and self._denominator. This speeds abs() up from 12.2us to
  10.8us and trunc() from 2.07us to 1.11us. This doesn't change _add and friends
  because they're more complicated.
........

1 files changed, 88 insertions, 72 deletions

diff --git a/Lib/fractions.py b/Lib/fractions.py
index 25b9f02..f368576 100755
--- a/Lib/fractions.py
+++ b/Lib/fractions.py
@@ -62,7 +62,7 @@ class Fraction(numbers.Rational):
         """
         self = super(Fraction, cls).__new__(cls)
 
-        if denominator == 1:
+        if not isinstance(numerator, int) and denominator == 1:
             if isinstance(numerator, str):
                 # Handle construction from strings.
                 input = numerator
@@ -84,24 +84,22 @@ class Fraction(numbers.Rational):
                 if m.group('sign') == '-':
                     numerator = -numerator
 
-            elif (not isinstance(numerator, numbers.Integral) and
-                  isinstance(numerator, numbers.Rational)):
-                # Handle copies from other rationals.
+            elif isinstance(numerator, numbers.Rational):
+                # Handle copies from other rationals. Integrals get
+                # caught here too, but it doesn't matter because
+                # denominator is already 1.
                 other_rational = numerator
                 numerator = other_rational.numerator
                 denominator = other_rational.denominator
 
-        if (not isinstance(numerator, numbers.Integral) or
-            not isinstance(denominator, numbers.Integral)):
-            raise TypeError("Fraction(%(numerator)s, %(denominator)s):"
-                            " Both arguments must be integral." % locals())
-
         if denominator == 0:
             raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
 
+        numerator = numerator.__index__()
+        denominator = denominator.__index__()
         g = gcd(numerator, denominator)
-        self._numerator = int(numerator // g)
-        self._denominator = int(denominator // g)
+        self._numerator = numerator // g
+        self._denominator = denominator // g
         return self
 
     @classmethod
@@ -138,42 +136,60 @@ class Fraction(numbers.Rational):
         else:
             return cls(digits, 10 ** -exp)
 
-    @classmethod
-    def from_continued_fraction(cls, seq):
-        'Build a Fraction from a continued fraction expessed as a sequence'
-        n, d = 1, 0
-        for e in reversed(seq):
-            n, d = d, n
-            n += e * d
-        return cls(n, d) if seq else cls(0)
-
-    def as_continued_fraction(self):
-        'Return continued fraction expressed as a list'
-        n = self.numerator
-        d = self.denominator
-        cf = []
-        while d:
-            e = int(n // d)
-            cf.append(e)
-            n -= e * d
-            n, d = d, n
-        return cf
-
-    def approximate(self, max_denominator):
-        'Best rational approximation with a denominator <= max_denominator'
-        # XXX First cut at algorithm
-        # Still needs rounding rules as specified at
-        #       http://en.wikipedia.org/wiki/Continued_fraction
-        if self.denominator <= max_denominator:
-            return self
-        cf = self.as_continued_fraction()
-        result = Fraction(0)
-        for i in range(1, len(cf)):
-            new = self.from_continued_fraction(cf[:i])
-            if new.denominator > max_denominator:
+    def limit_denominator(self, max_denominator=1000000):
+        """Closest Fraction to self with denominator at most max_denominator.
+
+        >>> Fraction('3.141592653589793').limit_denominator(10)
+        Fraction(22, 7)
+        >>> Fraction('3.141592653589793').limit_denominator(100)
+        Fraction(311, 99)
+        >>> Fraction(1234, 5678).limit_denominator(10000)
+        Fraction(1234, 5678)
+
+        """
+        # Algorithm notes: For any real number x, define a *best upper
+        # approximation* to x to be a rational number p/q such that:
+        #
+        #   (1) p/q >= x, and
+        #   (2) if p/q > r/s >= x then s > q, for any rational r/s.
+        #
+        # Define *best lower approximation* similarly.  Then it can be
+        # proved that a rational number is a best upper or lower
+        # approximation to x if, and only if, it is a convergent or
+        # semiconvergent of the (unique shortest) continued fraction
+        # associated to x.
+        #
+        # To find a best rational approximation with denominator <= M,
+        # we find the best upper and lower approximations with
+        # denominator <= M and take whichever of these is closer to x.
+        # In the event of a tie, the bound with smaller denominator is
+        # chosen.  If both denominators are equal (which can happen
+        # only when max_denominator == 1 and self is midway between
+        # two integers) the lower bound---i.e., the floor of self, is
+        # taken.
+
+        if max_denominator < 1:
+            raise ValueError("max_denominator should be at least 1")
+        if self._denominator <= max_denominator:
+            return Fraction(self)
+
+        p0, q0, p1, q1 = 0, 1, 1, 0
+        n, d = self._numerator, self._denominator
+        while True:
+            a = n//d
+            q2 = q0+a*q1
+            if q2 > max_denominator:
                 break
-            result = new
-        return result
+            p0, q0, p1, q1 = p1, q1, p0+a*p1, q2
+            n, d = d, n-a*d
+
+        k = (max_denominator-q0)//q1
+        bound1 = Fraction(p0+k*p1, q0+k*q1)
+        bound2 = Fraction(p1, q1)
+        if abs(bound2 - self) <= abs(bound1-self):
+            return bound2
+        else:
+            return bound1
 
     @property
     def numerator(a):
@@ -185,14 +201,14 @@ class Fraction(numbers.Rational):
 
     def __repr__(self):
         """repr(self)"""
-        return ('Fraction(%r,%r)' % (self.numerator, self.denominator))
+        return ('Fraction(%r, %r)' % (self._numerator, self._denominator))
 
     def __str__(self):
         """str(self)"""
-        if self.denominator == 1:
-            return str(self.numerator)
+        if self._denominator == 1:
+            return str(self._numerator)
         else:
-            return '%s/%s' % (self.numerator, self.denominator)
+            return '%s/%s' % (self._numerator, self._denominator)
 
     def _operator_fallbacks(monomorphic_operator, fallback_operator):
         """Generates forward and reverse operators given a purely-rational
@@ -360,11 +376,11 @@ class Fraction(numbers.Rational):
             if b.denominator == 1:
                 power = b.numerator
                 if power >= 0:
-                    return Fraction(a.numerator ** power,
-                                    a.denominator ** power)
+                    return Fraction(a._numerator ** power,
+                                    a._denominator ** power)
                 else:
-                    return Fraction(a.denominator ** -power,
-                                    a.numerator ** -power)
+                    return Fraction(a._denominator ** -power,
+                                    a._numerator ** -power)
             else:
                 # A fractional power will generally produce an
                 # irrational number.
@@ -374,36 +390,36 @@ class Fraction(numbers.Rational):
 
     def __rpow__(b, a):
         """a ** b"""
-        if b.denominator == 1 and b.numerator >= 0:
+        if b._denominator == 1 and b._numerator >= 0:
             # If a is an int, keep it that way if possible.
-            return a ** b.numerator
+            return a ** b._numerator
 
         if isinstance(a, numbers.Rational):
             return Fraction(a.numerator, a.denominator) ** b
 
-        if b.denominator == 1:
-            return a ** b.numerator
+        if b._denominator == 1:
+            return a ** b._numerator
 
         return a ** float(b)
 
     def __pos__(a):
         """+a: Coerces a subclass instance to Fraction"""
-        return Fraction(a.numerator, a.denominator)
+        return Fraction(a._numerator, a._denominator)
 
     def __neg__(a):
         """-a"""
-        return Fraction(-a.numerator, a.denominator)
+        return Fraction(-a._numerator, a._denominator)
 
     def __abs__(a):
         """abs(a)"""
-        return Fraction(abs(a.numerator), a.denominator)
+        return Fraction(abs(a._numerator), a._denominator)
 
     def __trunc__(a):
         """trunc(a)"""
-        if a.numerator < 0:
-            return -(-a.numerator // a.denominator)
+        if a._numerator < 0:
+            return -(-a._numerator // a._denominator)
         else:
-            return a.numerator // a.denominator
+            return a._numerator // a._denominator
 
     def __floor__(a):
         """Will be math.floor(a) in 3.0."""
@@ -447,22 +463,22 @@ class Fraction(numbers.Rational):
 
         """
         # XXX since this method is expensive, consider caching the result
-        if self.denominator == 1:
+        if self._denominator == 1:
             # Get integers right.
-            return hash(self.numerator)
+            return hash(self._numerator)
         # Expensive check, but definitely correct.
         if self == float(self):
             return hash(float(self))
         else:
             # Use tuple's hash to avoid a high collision rate on
             # simple fractions.
-            return hash((self.numerator, self.denominator))
+            return hash((self._numerator, self._denominator))
 
     def __eq__(a, b):
         """a == b"""
         if isinstance(b, numbers.Rational):
-            return (a.numerator == b.numerator and
-                    a.denominator == b.denominator)
+            return (a._numerator == b.numerator and
+                    a._denominator == b.denominator)
         if isinstance(b, numbers.Complex) and b.imag == 0:
             b = b.real
         if isinstance(b, float):
@@ -517,7 +533,7 @@ class Fraction(numbers.Rational):
 
     def __bool__(a):
         """a != 0"""
-        return a.numerator != 0
+        return a._numerator != 0
 
     # support for pickling, copy, and deepcopy
 
@@ -527,9 +543,9 @@ class Fraction(numbers.Rational):
     def __copy__(self):
         if type(self) == Fraction:
             return self     # I'm immutable; therefore I am my own clone
-        return self.__class__(self.numerator, self.denominator)
+        return self.__class__(self._numerator, self._denominator)
 
     def __deepcopy__(self, memo):
         if type(self) == Fraction:
             return self     # My components are also immutable
-        return self.__class__(self.numerator, self.denominator)
+        return self.__class__(self._numerator, self._denominator)