10a8c90248264a8b26970b4473770bcc3df8515fJosh Gao# Originally contributed by Sjoerd Mullender. 20a8c90248264a8b26970b4473770bcc3df8515fJosh Gao# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>. 30a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 40a8c90248264a8b26970b4473770bcc3df8515fJosh Gao"""Rational, infinite-precision, real numbers.""" 50a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 60a8c90248264a8b26970b4473770bcc3df8515fJosh Gaofrom __future__ import division 70a8c90248264a8b26970b4473770bcc3df8515fJosh Gaofrom decimal import Decimal 80a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoimport math 90a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoimport numbers 100a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoimport operator 110a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoimport re 120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao__all__ = ['Fraction', 'gcd'] 140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 150a8c90248264a8b26970b4473770bcc3df8515fJosh GaoRational = numbers.Rational 160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 180a8c90248264a8b26970b4473770bcc3df8515fJosh Gaodef gcd(a, b): 190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Calculate the Greatest Common Divisor of a and b. 200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Unless b==0, the result will have the same sign as b (so that when 220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao b is divided by it, the result comes out positive). 230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao while b: 250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao a, b = b, a%b 260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a 270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao_RATIONAL_FORMAT = re.compile(r""" 300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao \A\s* # optional whitespace at the start, then 310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao (?P<sign>[-+]?) # an optional sign, then 320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao (?=\d|\.\d) # lookahead for digit or .digit 330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao (?P<num>\d*) # numerator (possibly empty) 340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao (?: # followed by 350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao (?:/(?P<denom>\d+))? # an optional denominator 360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao | # or 370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao (?:\.(?P<decimal>\d*))? # an optional fractional part 380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao (?:E(?P<exp>[-+]?\d+))? # and optional exponent 390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ) 400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao \s*\Z # and optional whitespace to finish 410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao""", re.VERBOSE | re.IGNORECASE) 420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 440a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass Fraction(Rational): 450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """This class implements rational numbers. 460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao In the two-argument form of the constructor, Fraction(8, 6) will 480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao produce a rational number equivalent to 4/3. Both arguments must 490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao be Rational. The numerator defaults to 0 and the denominator 500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao defaults to 1 so that Fraction(3) == 3 and Fraction() == 0. 510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fractions can also be constructed from: 530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao - numeric strings similar to those accepted by the 550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao float constructor (for example, '-2.3' or '1e10') 560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao - strings of the form '123/456' 580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao - float and Decimal instances 600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao - other Rational instances (including integers) 620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __slots__ = ('_numerator', '_denominator') 660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # We're immutable, so use __new__ not __init__ 680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __new__(cls, numerator=0, denominator=None): 690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Constructs a Fraction. 700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Takes a string like '3/2' or '1.5', another Rational instance, a 720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao numerator/denominator pair, or a float. 730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Examples 750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao -------- 760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction(10, -8) 780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(-5, 4) 790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction(Fraction(1, 7), 5) 800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(1, 35) 810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction(Fraction(1, 7), Fraction(2, 3)) 820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(3, 14) 830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction('314') 840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(314, 1) 850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction('-35/4') 860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(-35, 4) 870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction('3.1415') # conversion from numeric string 880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(6283, 2000) 890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction('-47e-2') # string may include a decimal exponent 900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(-47, 100) 910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction(1.47) # direct construction from float (exact conversion) 920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(6620291452234629, 4503599627370496) 930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction(2.25) 940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(9, 4) 950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction(Decimal('1.47')) 960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(147, 100) 970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self = super(Fraction, cls).__new__(cls) 1000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if denominator is None: 1020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(numerator, Rational): 1030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self._numerator = numerator.numerator 1040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self._denominator = numerator.denominator 1050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self 1060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif isinstance(numerator, float): 1080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Exact conversion from float 1090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao value = Fraction.from_float(numerator) 1100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self._numerator = value._numerator 1110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self._denominator = value._denominator 1120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self 1130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif isinstance(numerator, Decimal): 1150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao value = Fraction.from_decimal(numerator) 1160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self._numerator = value._numerator 1170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self._denominator = value._denominator 1180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self 1190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif isinstance(numerator, basestring): 1210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Handle construction from strings. 1220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao m = _RATIONAL_FORMAT.match(numerator) 1230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if m is None: 1240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise ValueError('Invalid literal for Fraction: %r' % 1250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao numerator) 1260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao numerator = int(m.group('num') or '0') 1270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao denom = m.group('denom') 1280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if denom: 1290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao denominator = int(denom) 1300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 1310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao denominator = 1 1320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao decimal = m.group('decimal') 1330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if decimal: 1340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao scale = 10**len(decimal) 1350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao numerator = numerator * scale + int(decimal) 1360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao denominator *= scale 1370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao exp = m.group('exp') 1380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if exp: 1390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao exp = int(exp) 1400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if exp >= 0: 1410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao numerator *= 10**exp 1420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 1430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao denominator *= 10**-exp 1440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if m.group('sign') == '-': 1450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao numerator = -numerator 1460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 1480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise TypeError("argument should be a string " 1490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "or a Rational instance") 1500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif (isinstance(numerator, Rational) and 1520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao isinstance(denominator, Rational)): 1530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao numerator, denominator = ( 1540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao numerator.numerator * denominator.denominator, 1550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao denominator.numerator * numerator.denominator 1560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ) 1570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 1580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise TypeError("both arguments should be " 1590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "Rational instances") 1600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if denominator == 0: 1620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise ZeroDivisionError('Fraction(%s, 0)' % numerator) 1630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao g = gcd(numerator, denominator) 1640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self._numerator = numerator // g 1650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self._denominator = denominator // g 1660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self 1670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 1690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def from_float(cls, f): 1700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Converts a finite float to a rational number, exactly. 1710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Beware that Fraction.from_float(0.3) != Fraction(3, 10). 1730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 1750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(f, numbers.Integral): 1760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return cls(f) 1770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif not isinstance(f, float): 1780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise TypeError("%s.from_float() only takes floats, not %r (%s)" % 1790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao (cls.__name__, f, type(f).__name__)) 1800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if math.isnan(f) or math.isinf(f): 1810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise TypeError("Cannot convert %r to %s." % (f, cls.__name__)) 1820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return cls(*f.as_integer_ratio()) 1830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 1850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def from_decimal(cls, dec): 1860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Converts a finite Decimal instance to a rational number, exactly.""" 1870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao from decimal import Decimal 1880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(dec, numbers.Integral): 1890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao dec = Decimal(int(dec)) 1900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif not isinstance(dec, Decimal): 1910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise TypeError( 1920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "%s.from_decimal() only takes Decimals, not %r (%s)" % 1930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao (cls.__name__, dec, type(dec).__name__)) 1940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not dec.is_finite(): 1950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Catches infinities and nans. 1960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__)) 1970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao sign, digits, exp = dec.as_tuple() 1980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao digits = int(''.join(map(str, digits))) 1990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if sign: 2000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao digits = -digits 2010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if exp >= 0: 2020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return cls(digits * 10 ** exp) 2030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 2040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return cls(digits, 10 ** -exp) 2050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def limit_denominator(self, max_denominator=1000000): 2070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Closest Fraction to self with denominator at most max_denominator. 2080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction('3.141592653589793').limit_denominator(10) 2100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(22, 7) 2110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction('3.141592653589793').limit_denominator(100) 2120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(311, 99) 2130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Fraction(4321, 8765).limit_denominator(10000) 2140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction(4321, 8765) 2150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 2170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Algorithm notes: For any real number x, define a *best upper 2180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # approximation* to x to be a rational number p/q such that: 2190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # 2200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # (1) p/q >= x, and 2210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # (2) if p/q > r/s >= x then s > q, for any rational r/s. 2220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # 2230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Define *best lower approximation* similarly. Then it can be 2240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # proved that a rational number is a best upper or lower 2250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # approximation to x if, and only if, it is a convergent or 2260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # semiconvergent of the (unique shortest) continued fraction 2270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # associated to x. 2280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # 2290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # To find a best rational approximation with denominator <= M, 2300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # we find the best upper and lower approximations with 2310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # denominator <= M and take whichever of these is closer to x. 2320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # In the event of a tie, the bound with smaller denominator is 2330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # chosen. If both denominators are equal (which can happen 2340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # only when max_denominator == 1 and self is midway between 2350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # two integers) the lower bound---i.e., the floor of self, is 2360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # taken. 2370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if max_denominator < 1: 2390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise ValueError("max_denominator should be at least 1") 2400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if self._denominator <= max_denominator: 2410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(self) 2420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao p0, q0, p1, q1 = 0, 1, 1, 0 2440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao n, d = self._numerator, self._denominator 2450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao while True: 2460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao a = n//d 2470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao q2 = q0+a*q1 2480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if q2 > max_denominator: 2490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao break 2500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao p0, q0, p1, q1 = p1, q1, p0+a*p1, q2 2510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao n, d = d, n-a*d 2520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao k = (max_denominator-q0)//q1 2540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao bound1 = Fraction(p0+k*p1, q0+k*q1) 2550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao bound2 = Fraction(p1, q1) 2560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if abs(bound2 - self) <= abs(bound1-self): 2570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return bound2 2580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 2590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return bound1 2600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @property 2620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def numerator(a): 2630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a._numerator 2640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @property 2660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def denominator(a): 2670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a._denominator 2680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __repr__(self): 2700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """repr(self)""" 2710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return ('Fraction(%s, %s)' % (self._numerator, self._denominator)) 2720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __str__(self): 2740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """str(self)""" 2750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if self._denominator == 1: 2760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return str(self._numerator) 2770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 2780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return '%s/%s' % (self._numerator, self._denominator) 2790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _operator_fallbacks(monomorphic_operator, fallback_operator): 2810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Generates forward and reverse operators given a purely-rational 2820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao operator and a function from the operator module. 2830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Use this like: 2850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op) 2860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao In general, we want to implement the arithmetic operations so 2880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao that mixed-mode operations either call an implementation whose 2890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao author knew about the types of both arguments, or convert both 2900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao to the nearest built in type and do the operation there. In 2910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction, that means that we define __add__ and __radd__ as: 2920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __add__(self, other): 2940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Both types have numerators/denominator attributes, 2950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # so do the operation directly 2960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(other, (int, long, Fraction)): 2970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(self.numerator * other.denominator + 2980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao other.numerator * self.denominator, 2990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.denominator * other.denominator) 3000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # float and complex don't have those operations, but we 3010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # know about those types, so special case them. 3020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif isinstance(other, float): 3030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return float(self) + other 3040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif isinstance(other, complex): 3050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return complex(self) + other 3060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Let the other type take over. 3070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 3080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __radd__(self, other): 3100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # radd handles more types than add because there's 3110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # nothing left to fall back to. 3120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(other, Rational): 3130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(self.numerator * other.denominator + 3140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao other.numerator * self.denominator, 3150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.denominator * other.denominator) 3160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif isinstance(other, Real): 3170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return float(other) + float(self) 3180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif isinstance(other, Complex): 3190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return complex(other) + complex(self) 3200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 3210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao There are 5 different cases for a mixed-type addition on 3240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction. I'll refer to all of the above code that doesn't 3250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao refer to Fraction, float, or complex as "boilerplate". 'r' 3260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao will be an instance of Fraction, which is a subtype of 3270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Rational (r : Fraction <: Rational), and b : B <: 3280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Complex. The first three involve 'r + b': 3290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1. If B <: Fraction, int, float, or complex, we handle 3310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao that specially, and all is well. 3320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2. If Fraction falls back to the boilerplate code, and it 3330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao were to return a value from __add__, we'd miss the 3340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao possibility that B defines a more intelligent __radd__, 3350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao so the boilerplate should return NotImplemented from 3360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __add__. In particular, we don't handle Rational 3370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao here, even though we could get an exact answer, in case 3380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao the other type wants to do something special. 3390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3. If B <: Fraction, Python tries B.__radd__ before 3400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Fraction.__add__. This is ok, because it was 3410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao implemented with knowledge of Fraction, so it can 3420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao handle those instances before delegating to Real or 3430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Complex. 3440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao The next two situations describe 'b + r'. We assume that b 3460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao didn't know about Fraction in its implementation, and that it 3470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao uses similar boilerplate code: 3480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4. If B <: Rational, then __radd_ converts both to the 3500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao builtin rational type (hey look, that's us) and 3510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao proceeds. 3520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5. Otherwise, __radd__ tries to find the nearest common 3530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao base ABC, and fall back to its builtin type. Since this 3540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao class doesn't subclass a concrete type, there's no 3550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao implementation to fall back to, so we need to try as 3560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao hard as possible to return an actual value, or the user 3570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao will get a TypeError. 3580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 3600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def forward(a, b): 3610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(b, (int, long, Fraction)): 3620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return monomorphic_operator(a, b) 3630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif isinstance(b, float): 3640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return fallback_operator(float(a), b) 3650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif isinstance(b, complex): 3660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return fallback_operator(complex(a), b) 3670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 3680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 3690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao forward.__name__ = '__' + fallback_operator.__name__ + '__' 3700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao forward.__doc__ = monomorphic_operator.__doc__ 3710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def reverse(b, a): 3730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(a, Rational): 3740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Includes ints. 3750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return monomorphic_operator(a, b) 3760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif isinstance(a, numbers.Real): 3770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return fallback_operator(float(a), float(b)) 3780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao elif isinstance(a, numbers.Complex): 3790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return fallback_operator(complex(a), complex(b)) 3800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 3810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 3820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao reverse.__name__ = '__r' + fallback_operator.__name__ + '__' 3830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao reverse.__doc__ = monomorphic_operator.__doc__ 3840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return forward, reverse 3860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _add(a, b): 3880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a + b""" 3890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(a.numerator * b.denominator + 3900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao b.numerator * a.denominator, 3910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao a.denominator * b.denominator) 3920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __add__, __radd__ = _operator_fallbacks(_add, operator.add) 3940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _sub(a, b): 3960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a - b""" 3970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(a.numerator * b.denominator - 3980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao b.numerator * a.denominator, 3990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao a.denominator * b.denominator) 4000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub) 4020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _mul(a, b): 4040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a * b""" 4050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(a.numerator * b.numerator, a.denominator * b.denominator) 4060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul) 4080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _div(a, b): 4100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a / b""" 4110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(a.numerator * b.denominator, 4120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao a.denominator * b.numerator) 4130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv) 4150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __div__, __rdiv__ = _operator_fallbacks(_div, operator.div) 4160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __floordiv__(a, b): 4180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a // b""" 4190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Will be math.floor(a / b) in 3.0. 4200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao div = a / b 4210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(div, Rational): 4220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # trunc(math.floor(div)) doesn't work if the rational is 4230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # more precise than a float because the intermediate 4240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # rounding may cross an integer boundary. 4250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return div.numerator // div.denominator 4260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 4270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return math.floor(div) 4280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __rfloordiv__(b, a): 4300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a // b""" 4310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Will be math.floor(a / b) in 3.0. 4320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao div = a / b 4330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(div, Rational): 4340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # trunc(math.floor(div)) doesn't work if the rational is 4350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # more precise than a float because the intermediate 4360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # rounding may cross an integer boundary. 4370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return div.numerator // div.denominator 4380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 4390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return math.floor(div) 4400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __mod__(a, b): 4420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a % b""" 4430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao div = a // b 4440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a - b * div 4450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __rmod__(b, a): 4470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a % b""" 4480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao div = a // b 4490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a - b * div 4500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __pow__(a, b): 4520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a ** b 4530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao If b is not an integer, the result will be a float or complex 4550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao since roots are generally irrational. If b is an integer, the 4560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result will be rational. 4570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 4590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(b, Rational): 4600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if b.denominator == 1: 4610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao power = b.numerator 4620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if power >= 0: 4630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(a._numerator ** power, 4640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao a._denominator ** power) 4650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 4660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(a._denominator ** -power, 4670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao a._numerator ** -power) 4680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 4690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # A fractional power will generally produce an 4700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # irrational number. 4710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return float(a) ** float(b) 4720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 4730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return float(a) ** b 4740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __rpow__(b, a): 4760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a ** b""" 4770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if b._denominator == 1 and b._numerator >= 0: 4780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # If a is an int, keep it that way if possible. 4790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a ** b._numerator 4800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(a, Rational): 4820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(a.numerator, a.denominator) ** b 4830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if b._denominator == 1: 4850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a ** b._numerator 4860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a ** float(b) 4880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __pos__(a): 4900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """+a: Coerces a subclass instance to Fraction""" 4910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(a._numerator, a._denominator) 4920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __neg__(a): 4940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """-a""" 4950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(-a._numerator, a._denominator) 4960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __abs__(a): 4980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """abs(a)""" 4990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return Fraction(abs(a._numerator), a._denominator) 5000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __trunc__(a): 5020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """trunc(a)""" 5030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if a._numerator < 0: 5040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return -(-a._numerator // a._denominator) 5050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 5060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a._numerator // a._denominator 5070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __hash__(self): 5090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """hash(self) 5100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Tricky because values that are exactly representable as a 5120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao float must have the same hash as that float. 5130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 5150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # XXX since this method is expensive, consider caching the result 5160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if self._denominator == 1: 5170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Get integers right. 5180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return hash(self._numerator) 5190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Expensive check, but definitely correct. 5200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if self == float(self): 5210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return hash(float(self)) 5220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 5230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Use tuple's hash to avoid a high collision rate on 5240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # simple fractions. 5250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return hash((self._numerator, self._denominator)) 5260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __eq__(a, b): 5280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a == b""" 5290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(b, Rational): 5300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return (a._numerator == b.numerator and 5310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao a._denominator == b.denominator) 5320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(b, numbers.Complex) and b.imag == 0: 5330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao b = b.real 5340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(b, float): 5350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if math.isnan(b) or math.isinf(b): 5360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # comparisons with an infinity or nan should behave in 5370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # the same way for any finite a, so treat a as zero. 5380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return 0.0 == b 5390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 5400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a == a.from_float(b) 5410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 5420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Since a doesn't know how to compare with b, let's give b 5430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # a chance to compare itself with a. 5440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 5450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _richcmp(self, other, op): 5470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Helper for comparison operators, for internal use only. 5480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Implement comparison between a Rational instance `self`, and 5500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao either another Rational instance or a float `other`. If 5510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao `other` is not a Rational instance or a float, return 5520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao NotImplemented. `op` should be one of the six standard 5530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao comparison operators. 5540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 5560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # convert other to a Rational instance where reasonable. 5570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(other, Rational): 5580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return op(self._numerator * other.denominator, 5590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self._denominator * other.numerator) 5600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # comparisons with complex should raise a TypeError, for consistency 5610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # with int<->complex, float<->complex, and complex<->complex comparisons. 5620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(other, complex): 5630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise TypeError("no ordering relation is defined for complex numbers") 5640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(other, float): 5650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if math.isnan(other) or math.isinf(other): 5660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return op(0.0, other) 5670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 5680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return op(self, self.from_float(other)) 5690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 5700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 5710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __lt__(a, b): 5730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a < b""" 5740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a._richcmp(b, operator.lt) 5750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __gt__(a, b): 5770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a > b""" 5780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a._richcmp(b, operator.gt) 5790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __le__(a, b): 5810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a <= b""" 5820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a._richcmp(b, operator.le) 5830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __ge__(a, b): 5850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a >= b""" 5860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a._richcmp(b, operator.ge) 5870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __nonzero__(a): 5890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """a != 0""" 5900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return a._numerator != 0 5910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # support for pickling, copy, and deepcopy 5930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __reduce__(self): 5950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return (self.__class__, (str(self),)) 5960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __copy__(self): 5980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if type(self) == Fraction: 5990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self # I'm immutable; therefore I am my own clone 6000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self.__class__(self._numerator, self._denominator) 6010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __deepcopy__(self, memo): 6030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if type(self) == Fraction: 6040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self # My components are also immutable 6050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self.__class__(self._numerator, self._denominator) 606