fractions.py revision 909e334e8a525e8430f1532c0ecf133f19d3d185
1d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin# Originally contributed by Sjoerd Mullender. 2d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>. 3d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 4d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin"""Rational, infinite-precision, real numbers.""" 5d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 6d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskinfrom __future__ import division 7d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskinimport math 8d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskinimport numbers 9d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskinimport operator 1045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskinimport re 11d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 12d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin__all__ = ["Rational"] 13d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 14d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey YasskinRationalAbc = numbers.Rational 15d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 16d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 17d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskindef _gcd(a, b): 18d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """Calculate the Greatest Common Divisor. 19d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 20d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Unless b==0, the result will have the same sign as b (so that when 21d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin b is divided by it, the result comes out positive). 22d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 23d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin while b: 24d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin a, b = b, a%b 25d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a 26d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 27d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 28d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskindef _binary_float_to_ratio(x): 29d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """x -> (top, bot), a pair of ints s.t. x = top/bot. 30d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 31d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin The conversion is done exactly, without rounding. 32d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin bot > 0 guaranteed. 33d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Some form of binary fp is assumed. 34d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Pass NaNs or infinities at your own risk. 35d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 36d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin >>> _binary_float_to_ratio(10.0) 37d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin (10, 1) 38d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin >>> _binary_float_to_ratio(0.0) 39d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin (0, 1) 40d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin >>> _binary_float_to_ratio(-.25) 41d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin (-1, 4) 42d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 43d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 44d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if x == 0: 45d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return 0, 1 46d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin f, e = math.frexp(x) 47d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin signbit = 1 48d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if f < 0: 49d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin f = -f 50d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin signbit = -1 51d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin assert 0.5 <= f < 1.0 52d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # x = signbit * f * 2**e exactly 53d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 54d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Suck up CHUNK bits at a time; 28 is enough so that we suck 55d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # up all bits in 2 iterations for all known binary double- 56d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # precision formats, and small enough to fit in an int. 57d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin CHUNK = 28 58d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin top = 0 59d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # invariant: x = signbit * (top + f) * 2**e exactly 60d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin while f: 61d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin f = math.ldexp(f, CHUNK) 62d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin digit = trunc(f) 63d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin assert digit >> CHUNK == 0 64d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin top = (top << CHUNK) | digit 65d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin f = f - digit 66d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin assert 0.0 <= f < 1.0 67d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin e = e - CHUNK 68d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin assert top 69d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 70d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Add in the sign bit. 71d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin top = signbit * top 72d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 73d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # now x = top * 2**e exactly; fold in 2**e 74d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if e>0: 75d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return (top * 2**e, 1) 76d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 77d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return (top, 2 ** -e) 78d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 79d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 8045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin_RATIONAL_FORMAT = re.compile( 8145169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin r'^\s*(?P<sign>[-+]?)(?P<num>\d+)(?:/(?P<denom>\d+))?\s*$') 8245169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 8345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 84d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskinclass Rational(RationalAbc): 85d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """This class implements rational numbers. 86d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 87d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Rational(8, 6) will produce a rational number equivalent to 88d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 4/3. Both arguments must be Integral. The numerator defaults to 0 89d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin and the denominator defaults to 1 so that Rational(3) == 3 and 90d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Rational() == 0. 91d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 9245169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin Rationals can also be constructed from strings of the form 9345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin '[-+]?[0-9]+(/[0-9]+)?', optionally surrounded by spaces. 9445169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 95d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 96d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 977a6eacd2ca6322640ca99adbeeed6a134ed7009aRaymond Hettinger __slots__ = ('numerator', 'denominator') 98d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 9945169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin # We're immutable, so use __new__ not __init__ 10045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin def __new__(cls, numerator=0, denominator=1): 10145169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin """Constructs a Rational. 10245169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 10345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin Takes a string, another Rational, or a numerator/denominator pair. 10445169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 10545169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin """ 10645169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin self = super(Rational, cls).__new__(cls) 10745169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 10845169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if denominator == 1: 10945169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if isinstance(numerator, basestring): 11045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin # Handle construction from strings. 11145169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin input = numerator 11245169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin m = _RATIONAL_FORMAT.match(input) 11345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if m is None: 11445169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin raise ValueError('Invalid literal for Rational: ' + input) 11545169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin numerator = int(m.group('num')) 11645169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin # Default denominator to 1. That's the only optional group. 11745169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin denominator = int(m.group('denom') or 1) 11845169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if m.group('sign') == '-': 11945169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin numerator = -numerator 12045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 12145169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin elif (not isinstance(numerator, numbers.Integral) and 12245169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin isinstance(numerator, RationalAbc)): 12345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin # Handle copies from other rationals. 12445169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin other_rational = numerator 12545169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin numerator = other_rational.numerator 12645169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin denominator = other_rational.denominator 127d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 128d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if (not isinstance(numerator, numbers.Integral) or 129d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin not isinstance(denominator, numbers.Integral)): 130d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin raise TypeError("Rational(%(numerator)s, %(denominator)s):" 131d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin " Both arguments must be integral." % locals()) 132d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 133d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if denominator == 0: 134d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin raise ZeroDivisionError('Rational(%s, 0)' % numerator) 135d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 136d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin g = _gcd(numerator, denominator) 1377a6eacd2ca6322640ca99adbeeed6a134ed7009aRaymond Hettinger self.numerator = int(numerator // g) 1387a6eacd2ca6322640ca99adbeeed6a134ed7009aRaymond Hettinger self.denominator = int(denominator // g) 13945169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin return self 140d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 141d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin @classmethod 142d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def from_float(cls, f): 14345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin """Converts a finite float to a rational number, exactly. 14445169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 14545169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin Beware that Rational.from_float(0.3) != Rational(3, 10). 14645169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 14745169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin """ 148d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if not isinstance(f, float): 149d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin raise TypeError("%s.from_float() only takes floats, not %r (%s)" % 150d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin (cls.__name__, f, type(f).__name__)) 151d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if math.isnan(f) or math.isinf(f): 152d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin raise TypeError("Cannot convert %r to %s." % (f, cls.__name__)) 153d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return cls(*_binary_float_to_ratio(f)) 154d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 15545169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin @classmethod 15645169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin def from_decimal(cls, dec): 15745169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin """Converts a finite Decimal instance to a rational number, exactly.""" 15845169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin from decimal import Decimal 15945169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if not isinstance(dec, Decimal): 16045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin raise TypeError( 16145169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin "%s.from_decimal() only takes Decimals, not %r (%s)" % 16245169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin (cls.__name__, dec, type(dec).__name__)) 16345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if not dec.is_finite(): 16445169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin # Catches infinities and nans. 16545169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__)) 16645169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin sign, digits, exp = dec.as_tuple() 16745169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin digits = int(''.join(map(str, digits))) 16845169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if sign: 16945169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin digits = -digits 17045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if exp >= 0: 17145169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin return cls(digits * 10 ** exp) 17245169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin else: 17345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin return cls(digits, 10 ** -exp) 17445169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 175cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger @classmethod 176cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger def from_continued_fraction(cls, seq): 177cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger 'Build a Rational from a continued fraction expessed as a sequence' 178cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger n, d = 1, 0 179cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger for e in reversed(seq): 180cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger n, d = d, n 181cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger n += e * d 182f336c8b7e91f389c8af4255f589849b16ee3dcb5Raymond Hettinger return cls(n, d) if seq else cls(0) 183cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger 184cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger def as_continued_fraction(self): 185cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger 'Return continued fraction expressed as a list' 186cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger n = self.numerator 187cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger d = self.denominator 188cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger cf = [] 189cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger while d: 190cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger e = int(n // d) 191cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger cf.append(e) 192cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger n -= e * d 193cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger n, d = d, n 194cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger return cf 195cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger 196cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger @classmethod 197cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger def approximate_from_float(cls, f, max_denominator): 198cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger 'Best rational approximation to f with a denominator <= max_denominator' 199cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger # XXX First cut at algorithm 200cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger # Still needs rounding rules as specified at 201cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger # http://en.wikipedia.org/wiki/Continued_fraction 202cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger cf = cls.from_float(f).as_continued_fraction() 203eb461904eb277c5a92a7d2672f941cb095cf1a93Raymond Hettinger result = Rational(0) 204cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger for i in range(1, len(cf)): 205cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger new = cls.from_continued_fraction(cf[:i]) 206cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger if new.denominator > max_denominator: 207cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger break 208cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger result = new 209cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger return result 210cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger 211d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __repr__(self): 212d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """repr(self)""" 21345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin return ('Rational(%r,%r)' % (self.numerator, self.denominator)) 214d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 215d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __str__(self): 216d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """str(self)""" 217d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if self.denominator == 1: 218d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return str(self.numerator) 219d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 22045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin return '%s/%s' % (self.numerator, self.denominator) 221d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 222d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def _operator_fallbacks(monomorphic_operator, fallback_operator): 223d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """Generates forward and reverse operators given a purely-rational 224d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin operator and a function from the operator module. 225d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 226d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Use this like: 227d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op) 228d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 229d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 230d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def forward(a, b): 231d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(b, RationalAbc): 232d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Includes ints. 233d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return monomorphic_operator(a, b) 234d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin elif isinstance(b, float): 235d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return fallback_operator(float(a), b) 236d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin elif isinstance(b, complex): 237d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return fallback_operator(complex(a), b) 238d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 239d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return NotImplemented 240d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin forward.__name__ = '__' + fallback_operator.__name__ + '__' 241d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin forward.__doc__ = monomorphic_operator.__doc__ 242d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 243d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def reverse(b, a): 244d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(a, RationalAbc): 245d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Includes ints. 246d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return monomorphic_operator(a, b) 247d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin elif isinstance(a, numbers.Real): 248d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return fallback_operator(float(a), float(b)) 249d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin elif isinstance(a, numbers.Complex): 250d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return fallback_operator(complex(a), complex(b)) 251d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 252d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return NotImplemented 253d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin reverse.__name__ = '__r' + fallback_operator.__name__ + '__' 254d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin reverse.__doc__ = monomorphic_operator.__doc__ 255d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 256d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return forward, reverse 257d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 258d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def _add(a, b): 259d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a + b""" 260d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational(a.numerator * b.denominator + 261d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin b.numerator * a.denominator, 262d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin a.denominator * b.denominator) 263d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 264d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __add__, __radd__ = _operator_fallbacks(_add, operator.add) 265d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 266d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def _sub(a, b): 267d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a - b""" 268d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational(a.numerator * b.denominator - 269d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin b.numerator * a.denominator, 270d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin a.denominator * b.denominator) 271d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 272d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub) 273d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 274d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def _mul(a, b): 275d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a * b""" 276d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational(a.numerator * b.numerator, a.denominator * b.denominator) 277d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 278d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul) 279d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 280d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def _div(a, b): 281d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a / b""" 282d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational(a.numerator * b.denominator, 283d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin a.denominator * b.numerator) 284d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 285d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv) 286d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __div__, __rdiv__ = _operator_fallbacks(_div, operator.div) 287d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 288909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger def __floordiv__(a, b): 289909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger """a // b""" 290909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger # Will be math.floor(a / b) in 3.0. 291d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin div = a / b 292d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(div, RationalAbc): 293d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # trunc(math.floor(div)) doesn't work if the rational is 294d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # more precise than a float because the intermediate 295d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # rounding may cross an integer boundary. 296d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return div.numerator // div.denominator 297d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 298d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return math.floor(div) 299d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 300d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __rfloordiv__(b, a): 301d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a // b""" 302d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Will be math.floor(a / b) in 3.0. 303909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger div = a / b 304909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger if isinstance(div, RationalAbc): 305909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger # trunc(math.floor(div)) doesn't work if the rational is 306909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger # more precise than a float because the intermediate 307909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger # rounding may cross an integer boundary. 308909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger return div.numerator // div.denominator 309909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger else: 310909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger return math.floor(div) 311d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 312d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __mod__(a, b): 313d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a % b""" 314909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger div = a // b 315909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger return a - b * div 316d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 317d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __rmod__(b, a): 318d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a % b""" 319909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger div = a // b 320909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger return a - b * div 321d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 322d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __pow__(a, b): 323d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a ** b 324d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 325d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin If b is not an integer, the result will be a float or complex 326d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin since roots are generally irrational. If b is an integer, the 327d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin result will be rational. 328d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 329d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 330d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(b, RationalAbc): 331d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if b.denominator == 1: 332d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin power = b.numerator 333d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if power >= 0: 334d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational(a.numerator ** power, 335d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin a.denominator ** power) 336d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 337d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational(a.denominator ** -power, 338d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin a.numerator ** -power) 339d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 340d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # A fractional power will generally produce an 341d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # irrational number. 342d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return float(a) ** float(b) 343d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 344d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return float(a) ** b 345d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 346d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __rpow__(b, a): 347d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a ** b""" 348d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if b.denominator == 1 and b.numerator >= 0: 349d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # If a is an int, keep it that way if possible. 350d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a ** b.numerator 351d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 352d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(a, RationalAbc): 353d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational(a.numerator, a.denominator) ** b 354d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 355d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if b.denominator == 1: 356d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a ** b.numerator 357d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 358d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a ** float(b) 359d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 360d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __pos__(a): 361d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """+a: Coerces a subclass instance to Rational""" 362d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational(a.numerator, a.denominator) 363d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 364d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __neg__(a): 365d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """-a""" 366d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational(-a.numerator, a.denominator) 367d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 368d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __abs__(a): 369d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """abs(a)""" 370d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational(abs(a.numerator), a.denominator) 371d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 372d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __trunc__(a): 373d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """trunc(a)""" 374d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if a.numerator < 0: 375d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return -(-a.numerator // a.denominator) 376d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 377d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a.numerator // a.denominator 378d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 3795b0e27e50d33f33515f31ff6fec123f5e2be9d73Raymond Hettinger __int__ = __trunc__ 3805b0e27e50d33f33515f31ff6fec123f5e2be9d73Raymond Hettinger 381d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __floor__(a): 382d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """Will be math.floor(a) in 3.0.""" 383d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a.numerator // a.denominator 384d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 385d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __ceil__(a): 386d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """Will be math.ceil(a) in 3.0.""" 387d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # The negations cleverly convince floordiv to return the ceiling. 388d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return -(-a.numerator // a.denominator) 389d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 390d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __round__(self, ndigits=None): 391d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """Will be round(self, ndigits) in 3.0. 392d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 393d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Rounds half toward even. 394d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 395d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if ndigits is None: 396d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin floor, remainder = divmod(self.numerator, self.denominator) 397d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if remainder * 2 < self.denominator: 398d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return floor 399d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin elif remainder * 2 > self.denominator: 400d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return floor + 1 401d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Deal with the half case: 402d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin elif floor % 2 == 0: 403d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return floor 404d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 405d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return floor + 1 406d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin shift = 10**abs(ndigits) 407d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # See _operator_fallbacks.forward to check that the results of 408d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # these operations will always be Rational and therefore have 409d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # __round__(). 410d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if ndigits > 0: 411d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational((self * shift).__round__(), shift) 412d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 413d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return Rational((self / shift).__round__() * shift) 414d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 415d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __hash__(self): 416d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """hash(self) 417d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 418d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Tricky because values that are exactly representable as a 419d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin float must have the same hash as that float. 420d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 421d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 422d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if self.denominator == 1: 423d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Get integers right. 424d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return hash(self.numerator) 425d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Expensive check, but definitely correct. 426d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if self == float(self): 427d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return hash(float(self)) 428d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 429d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Use tuple's hash to avoid a high collision rate on 430d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # simple fractions. 431d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return hash((self.numerator, self.denominator)) 432d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 433d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __eq__(a, b): 434d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a == b""" 435d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(b, RationalAbc): 436d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return (a.numerator == b.numerator and 437d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin a.denominator == b.denominator) 438d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(b, numbers.Complex) and b.imag == 0: 439d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin b = b.real 440d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(b, float): 441d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a == a.from_float(b) 442d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 443d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # XXX: If b.__eq__ is implemented like this method, it may 444d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # give the wrong answer after float(a) changes a's 445d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # value. Better ways of doing this are welcome. 446d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return float(a) == b 447d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 448d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def _subtractAndCompareToZero(a, b, op): 449d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """Helper function for comparison operators. 450d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 451d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Subtracts b from a, exactly if possible, and compares the 452d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin result with 0 using op, in such a way that the comparison 453d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin won't recurse. If the difference raises a TypeError, returns 454d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin NotImplemented instead. 455d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 456d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 457d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(b, numbers.Complex) and b.imag == 0: 458d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin b = b.real 459d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(b, float): 460d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin b = a.from_float(b) 461d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin try: 462d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # XXX: If b <: Real but not <: RationalAbc, this is likely 463d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # to fall back to a float. If the actual values differ by 464d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # less than MIN_FLOAT, this could falsely call them equal, 465d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # which would make <= inconsistent with ==. Better ways of 466d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # doing this are welcome. 467d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin diff = a - b 468d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin except TypeError: 469d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return NotImplemented 470d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(diff, RationalAbc): 471d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return op(diff.numerator, 0) 472d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return op(diff, 0) 473d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 474d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __lt__(a, b): 475d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a < b""" 476d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a._subtractAndCompareToZero(b, operator.lt) 477d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 478d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __gt__(a, b): 479d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a > b""" 480d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a._subtractAndCompareToZero(b, operator.gt) 481d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 482d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __le__(a, b): 483d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a <= b""" 484d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a._subtractAndCompareToZero(b, operator.le) 485d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 486d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __ge__(a, b): 487d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a >= b""" 488d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a._subtractAndCompareToZero(b, operator.ge) 489d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 490d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __nonzero__(a): 491d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a != 0""" 492d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a.numerator != 0 493a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger