diff options
Diffstat (limited to 'Lib/fractions.py')
| -rwxr-xr-x | Lib/fractions.py | 160 |
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) |