14710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# Originally contributed by Sjoerd Mullender. 24710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>. 34710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 44710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm"""Rational, infinite-precision, real numbers.""" 54710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 64710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrom __future__ import division 74710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrom decimal import Decimal 84710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport math 94710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport numbers 104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport operator 114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport re 124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm__all__ = ['Fraction', 'gcd'] 144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmRational = numbers.Rational 164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef gcd(a, b): 194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """Calculate the Greatest Common Divisor of a and b. 204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Unless b==0, the result will have the same sign as b (so that when 224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b is divided by it, the result comes out positive). 234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """ 244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while b: 254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a, b = b, a%b 264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a 274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm_RATIONAL_FORMAT = re.compile(r""" 304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm \A\s* # optional whitespace at the start, then 314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (?P<sign>[-+]?) # an optional sign, then 324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (?=\d|\.\d) # lookahead for digit or .digit 334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (?P<num>\d*) # numerator (possibly empty) 344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (?: # followed by 354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (?:/(?P<denom>\d+))? # an optional denominator 364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm | # or 374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (?:\.(?P<decimal>\d*))? # an optional fractional part 384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (?:E(?P<exp>[-+]?\d+))? # and optional exponent 394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ) 404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm \s*\Z # and optional whitespace to finish 414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm""", re.VERBOSE | re.IGNORECASE) 424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass Fraction(Rational): 454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """This class implements rational numbers. 464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm In the two-argument form of the constructor, Fraction(8, 6) will 484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm produce a rational number equivalent to 4/3. Both arguments must 494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm be Rational. The numerator defaults to 0 and the denominator 504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm defaults to 1 so that Fraction(3) == 3 and Fraction() == 0. 514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fractions can also be constructed from: 534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm - numeric strings similar to those accepted by the 554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm float constructor (for example, '-2.3' or '1e10') 564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm - strings of the form '123/456' 584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm - float and Decimal instances 604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm - other Rational instances (including integers) 624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """ 644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __slots__ = ('_numerator', '_denominator') 664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # We're immutable, so use __new__ not __init__ 684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __new__(cls, numerator=0, denominator=None): 694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """Constructs a Fraction. 704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Takes a string like '3/2' or '1.5', another Rational instance, a 724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm numerator/denominator pair, or a float. 734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Examples 754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm -------- 764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction(10, -8) 784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(-5, 4) 794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction(Fraction(1, 7), 5) 804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(1, 35) 814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction(Fraction(1, 7), Fraction(2, 3)) 824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(3, 14) 834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction('314') 844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(314, 1) 854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction('-35/4') 864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(-35, 4) 874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction('3.1415') # conversion from numeric string 884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(6283, 2000) 894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction('-47e-2') # string may include a decimal exponent 904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(-47, 100) 914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction(1.47) # direct construction from float (exact conversion) 924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(6620291452234629, 4503599627370496) 934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction(2.25) 944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(9, 4) 954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction(Decimal('1.47')) 964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(147, 100) 974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """ 994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self = super(Fraction, cls).__new__(cls) 1004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if denominator is None: 1024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(numerator, Rational): 1034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._numerator = numerator.numerator 1044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._denominator = numerator.denominator 1054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self 1064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif isinstance(numerator, float): 1084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Exact conversion from float 1094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm value = Fraction.from_float(numerator) 1104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._numerator = value._numerator 1114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._denominator = value._denominator 1124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self 1134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif isinstance(numerator, Decimal): 1154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm value = Fraction.from_decimal(numerator) 1164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._numerator = value._numerator 1174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._denominator = value._denominator 1184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self 1194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif isinstance(numerator, basestring): 1214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Handle construction from strings. 1224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm m = _RATIONAL_FORMAT.match(numerator) 1234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if m is None: 1244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise ValueError('Invalid literal for Fraction: %r' % 1254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm numerator) 1264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm numerator = int(m.group('num') or '0') 1274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm denom = m.group('denom') 1284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if denom: 1294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm denominator = int(denom) 1304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 1314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm denominator = 1 1324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm decimal = m.group('decimal') 1334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if decimal: 1344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm scale = 10**len(decimal) 1354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm numerator = numerator * scale + int(decimal) 1364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm denominator *= scale 1374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm exp = m.group('exp') 1384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if exp: 1394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm exp = int(exp) 1404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if exp >= 0: 1414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm numerator *= 10**exp 1424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 1434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm denominator *= 10**-exp 1444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if m.group('sign') == '-': 1454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm numerator = -numerator 1464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 1484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise TypeError("argument should be a string " 1494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "or a Rational instance") 1504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif (isinstance(numerator, Rational) and 1524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm isinstance(denominator, Rational)): 1534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm numerator, denominator = ( 1544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm numerator.numerator * denominator.denominator, 1554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm denominator.numerator * numerator.denominator 1564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ) 1574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 1584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise TypeError("both arguments should be " 1594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "Rational instances") 1604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if denominator == 0: 1624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise ZeroDivisionError('Fraction(%s, 0)' % numerator) 1634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm g = gcd(numerator, denominator) 1644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._numerator = numerator // g 1654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._denominator = denominator // g 1664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self 1674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm @classmethod 1694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def from_float(cls, f): 1704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """Converts a finite float to a rational number, exactly. 1714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Beware that Fraction.from_float(0.3) != Fraction(3, 10). 1734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """ 1754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(f, numbers.Integral): 1764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return cls(f) 1774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif not isinstance(f, float): 1784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise TypeError("%s.from_float() only takes floats, not %r (%s)" % 1794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (cls.__name__, f, type(f).__name__)) 1804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if math.isnan(f) or math.isinf(f): 1814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise TypeError("Cannot convert %r to %s." % (f, cls.__name__)) 1824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return cls(*f.as_integer_ratio()) 1834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm @classmethod 1854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def from_decimal(cls, dec): 1864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """Converts a finite Decimal instance to a rational number, exactly.""" 1874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm from decimal import Decimal 1884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(dec, numbers.Integral): 1894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dec = Decimal(int(dec)) 1904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif not isinstance(dec, Decimal): 1914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise TypeError( 1924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "%s.from_decimal() only takes Decimals, not %r (%s)" % 1934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (cls.__name__, dec, type(dec).__name__)) 1944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not dec.is_finite(): 1954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Catches infinities and nans. 1964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__)) 1974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sign, digits, exp = dec.as_tuple() 1984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm digits = int(''.join(map(str, digits))) 1994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if sign: 2004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm digits = -digits 2014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if exp >= 0: 2024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return cls(digits * 10 ** exp) 2034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 2044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return cls(digits, 10 ** -exp) 2054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def limit_denominator(self, max_denominator=1000000): 2074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """Closest Fraction to self with denominator at most max_denominator. 2084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction('3.141592653589793').limit_denominator(10) 2104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(22, 7) 2114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction('3.141592653589793').limit_denominator(100) 2124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(311, 99) 2134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Fraction(4321, 8765).limit_denominator(10000) 2144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction(4321, 8765) 2154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """ 2174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Algorithm notes: For any real number x, define a *best upper 2184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # approximation* to x to be a rational number p/q such that: 2194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # 2204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # (1) p/q >= x, and 2214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # (2) if p/q > r/s >= x then s > q, for any rational r/s. 2224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # 2234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Define *best lower approximation* similarly. Then it can be 2244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # proved that a rational number is a best upper or lower 2254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # approximation to x if, and only if, it is a convergent or 2264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # semiconvergent of the (unique shortest) continued fraction 2274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # associated to x. 2284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # 2294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # To find a best rational approximation with denominator <= M, 2304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # we find the best upper and lower approximations with 2314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # denominator <= M and take whichever of these is closer to x. 2324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # In the event of a tie, the bound with smaller denominator is 2334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # chosen. If both denominators are equal (which can happen 2344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # only when max_denominator == 1 and self is midway between 2354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # two integers) the lower bound---i.e., the floor of self, is 2364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # taken. 2374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if max_denominator < 1: 2394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise ValueError("max_denominator should be at least 1") 2404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if self._denominator <= max_denominator: 2414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(self) 2424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm p0, q0, p1, q1 = 0, 1, 1, 0 2444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm n, d = self._numerator, self._denominator 2454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while True: 2464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a = n//d 2474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm q2 = q0+a*q1 2484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if q2 > max_denominator: 2494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm break 2504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm p0, q0, p1, q1 = p1, q1, p0+a*p1, q2 2514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm n, d = d, n-a*d 2524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm k = (max_denominator-q0)//q1 2544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm bound1 = Fraction(p0+k*p1, q0+k*q1) 2554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm bound2 = Fraction(p1, q1) 2564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if abs(bound2 - self) <= abs(bound1-self): 2574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return bound2 2584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 2594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return bound1 2604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm @property 2624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def numerator(a): 2634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a._numerator 2644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm @property 2664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def denominator(a): 2674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a._denominator 2684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __repr__(self): 2704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """repr(self)""" 2714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return ('Fraction(%s, %s)' % (self._numerator, self._denominator)) 2724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __str__(self): 2744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """str(self)""" 2754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if self._denominator == 1: 2764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return str(self._numerator) 2774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 2784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return '%s/%s' % (self._numerator, self._denominator) 2794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def _operator_fallbacks(monomorphic_operator, fallback_operator): 2814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """Generates forward and reverse operators given a purely-rational 2824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm operator and a function from the operator module. 2834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Use this like: 2854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op) 2864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm In general, we want to implement the arithmetic operations so 2884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm that mixed-mode operations either call an implementation whose 2894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm author knew about the types of both arguments, or convert both 2904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm to the nearest built in type and do the operation there. In 2914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction, that means that we define __add__ and __radd__ as: 2924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __add__(self, other): 2944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Both types have numerators/denominator attributes, 2954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # so do the operation directly 2964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(other, (int, long, Fraction)): 2974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(self.numerator * other.denominator + 2984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm other.numerator * self.denominator, 2994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.denominator * other.denominator) 3004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # float and complex don't have those operations, but we 3014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # know about those types, so special case them. 3024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif isinstance(other, float): 3034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return float(self) + other 3044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif isinstance(other, complex): 3054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return complex(self) + other 3064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Let the other type take over. 3074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NotImplemented 3084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __radd__(self, other): 3104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # radd handles more types than add because there's 3114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # nothing left to fall back to. 3124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(other, Rational): 3134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(self.numerator * other.denominator + 3144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm other.numerator * self.denominator, 3154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.denominator * other.denominator) 3164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif isinstance(other, Real): 3174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return float(other) + float(self) 3184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif isinstance(other, Complex): 3194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return complex(other) + complex(self) 3204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NotImplemented 3214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm There are 5 different cases for a mixed-type addition on 3244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction. I'll refer to all of the above code that doesn't 3254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm refer to Fraction, float, or complex as "boilerplate". 'r' 3264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm will be an instance of Fraction, which is a subtype of 3274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Rational (r : Fraction <: Rational), and b : B <: 3284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Complex. The first three involve 'r + b': 3294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1. If B <: Fraction, int, float, or complex, we handle 3314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm that specially, and all is well. 3324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2. If Fraction falls back to the boilerplate code, and it 3334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm were to return a value from __add__, we'd miss the 3344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm possibility that B defines a more intelligent __radd__, 3354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm so the boilerplate should return NotImplemented from 3364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __add__. In particular, we don't handle Rational 3374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm here, even though we could get an exact answer, in case 3384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm the other type wants to do something special. 3394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3. If B <: Fraction, Python tries B.__radd__ before 3404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Fraction.__add__. This is ok, because it was 3414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm implemented with knowledge of Fraction, so it can 3424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm handle those instances before delegating to Real or 3434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Complex. 3444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm The next two situations describe 'b + r'. We assume that b 3464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm didn't know about Fraction in its implementation, and that it 3474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm uses similar boilerplate code: 3484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4. If B <: Rational, then __radd_ converts both to the 3504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm builtin rational type (hey look, that's us) and 3514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm proceeds. 3524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5. Otherwise, __radd__ tries to find the nearest common 3534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm base ABC, and fall back to its builtin type. Since this 3544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm class doesn't subclass a concrete type, there's no 3554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm implementation to fall back to, so we need to try as 3564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm hard as possible to return an actual value, or the user 3574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm will get a TypeError. 3584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """ 3604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def forward(a, b): 3614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(b, (int, long, Fraction)): 3624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return monomorphic_operator(a, b) 3634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif isinstance(b, float): 3644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return fallback_operator(float(a), b) 3654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif isinstance(b, complex): 3664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return fallback_operator(complex(a), b) 3674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 3684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NotImplemented 3694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm forward.__name__ = '__' + fallback_operator.__name__ + '__' 3704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm forward.__doc__ = monomorphic_operator.__doc__ 3714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def reverse(b, a): 3734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(a, Rational): 3744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Includes ints. 3754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return monomorphic_operator(a, b) 3764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif isinstance(a, numbers.Real): 3774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return fallback_operator(float(a), float(b)) 3784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm elif isinstance(a, numbers.Complex): 3794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return fallback_operator(complex(a), complex(b)) 3804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 3814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NotImplemented 3824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm reverse.__name__ = '__r' + fallback_operator.__name__ + '__' 3834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm reverse.__doc__ = monomorphic_operator.__doc__ 3844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return forward, reverse 3864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def _add(a, b): 3884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a + b""" 3894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(a.numerator * b.denominator + 3904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b.numerator * a.denominator, 3914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a.denominator * b.denominator) 3924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __add__, __radd__ = _operator_fallbacks(_add, operator.add) 3944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def _sub(a, b): 3964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a - b""" 3974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(a.numerator * b.denominator - 3984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b.numerator * a.denominator, 3994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a.denominator * b.denominator) 4004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub) 4024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def _mul(a, b): 4044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a * b""" 4054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(a.numerator * b.numerator, a.denominator * b.denominator) 4064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul) 4084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def _div(a, b): 4104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a / b""" 4114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(a.numerator * b.denominator, 4124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a.denominator * b.numerator) 4134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv) 4154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __div__, __rdiv__ = _operator_fallbacks(_div, operator.div) 4164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __floordiv__(a, b): 4184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a // b""" 4194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Will be math.floor(a / b) in 3.0. 4204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm div = a / b 4214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(div, Rational): 4224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # trunc(math.floor(div)) doesn't work if the rational is 4234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # more precise than a float because the intermediate 4244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # rounding may cross an integer boundary. 4254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return div.numerator // div.denominator 4264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 4274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return math.floor(div) 4284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __rfloordiv__(b, a): 4304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a // b""" 4314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Will be math.floor(a / b) in 3.0. 4324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm div = a / b 4334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(div, Rational): 4344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # trunc(math.floor(div)) doesn't work if the rational is 4354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # more precise than a float because the intermediate 4364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # rounding may cross an integer boundary. 4374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return div.numerator // div.denominator 4384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 4394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return math.floor(div) 4404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __mod__(a, b): 4424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a % b""" 4434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm div = a // b 4444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a - b * div 4454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __rmod__(b, a): 4474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a % b""" 4484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm div = a // b 4494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a - b * div 4504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __pow__(a, b): 4524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a ** b 4534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm If b is not an integer, the result will be a float or complex 4554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm since roots are generally irrational. If b is an integer, the 4564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result will be rational. 4574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """ 4594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(b, Rational): 4604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if b.denominator == 1: 4614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm power = b.numerator 4624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if power >= 0: 4634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(a._numerator ** power, 4644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a._denominator ** power) 4654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 4664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(a._denominator ** -power, 4674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a._numerator ** -power) 4684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 4694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # A fractional power will generally produce an 4704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # irrational number. 4714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return float(a) ** float(b) 4724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 4734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return float(a) ** b 4744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __rpow__(b, a): 4764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a ** b""" 4774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if b._denominator == 1 and b._numerator >= 0: 4784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # If a is an int, keep it that way if possible. 4794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a ** b._numerator 4804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(a, Rational): 4824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(a.numerator, a.denominator) ** b 4834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if b._denominator == 1: 4854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a ** b._numerator 4864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a ** float(b) 4884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __pos__(a): 4904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """+a: Coerces a subclass instance to Fraction""" 4914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(a._numerator, a._denominator) 4924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __neg__(a): 4944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """-a""" 4954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(-a._numerator, a._denominator) 4964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __abs__(a): 4984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """abs(a)""" 4994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return Fraction(abs(a._numerator), a._denominator) 5004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __trunc__(a): 5024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """trunc(a)""" 5034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if a._numerator < 0: 5044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return -(-a._numerator // a._denominator) 5054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 5064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a._numerator // a._denominator 5074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __hash__(self): 5094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """hash(self) 5104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Tricky because values that are exactly representable as a 5124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm float must have the same hash as that float. 5134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """ 5154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # XXX since this method is expensive, consider caching the result 5164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if self._denominator == 1: 5174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Get integers right. 5184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return hash(self._numerator) 5194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Expensive check, but definitely correct. 5204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if self == float(self): 5214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return hash(float(self)) 5224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 5234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Use tuple's hash to avoid a high collision rate on 5244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # simple fractions. 5254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return hash((self._numerator, self._denominator)) 5264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __eq__(a, b): 5284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a == b""" 5294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(b, Rational): 5304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (a._numerator == b.numerator and 5314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a._denominator == b.denominator) 5324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(b, numbers.Complex) and b.imag == 0: 5334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm b = b.real 5344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(b, float): 5354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if math.isnan(b) or math.isinf(b): 5364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # comparisons with an infinity or nan should behave in 5374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # the same way for any finite a, so treat a as zero. 5384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0.0 == b 5394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 5404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a == a.from_float(b) 5414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 5424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Since a doesn't know how to compare with b, let's give b 5434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # a chance to compare itself with a. 5444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NotImplemented 5454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def _richcmp(self, other, op): 5474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """Helper for comparison operators, for internal use only. 5484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Implement comparison between a Rational instance `self`, and 5504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm either another Rational instance or a float `other`. If 5514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm `other` is not a Rational instance or a float, return 5524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm NotImplemented. `op` should be one of the six standard 5534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm comparison operators. 5544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """ 5564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # convert other to a Rational instance where reasonable. 5574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(other, Rational): 5584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return op(self._numerator * other.denominator, 5594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self._denominator * other.numerator) 5604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # comparisons with complex should raise a TypeError, for consistency 5614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # with int<->complex, float<->complex, and complex<->complex comparisons. 5624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(other, complex): 5634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise TypeError("no ordering relation is defined for complex numbers") 5644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(other, float): 5654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if math.isnan(other) or math.isinf(other): 5664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return op(0.0, other) 5674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 5684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return op(self, self.from_float(other)) 5694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 5704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NotImplemented 5714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __lt__(a, b): 5734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a < b""" 5744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a._richcmp(b, operator.lt) 5754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __gt__(a, b): 5774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a > b""" 5784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a._richcmp(b, operator.gt) 5794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __le__(a, b): 5814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a <= b""" 5824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a._richcmp(b, operator.le) 5834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __ge__(a, b): 5854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a >= b""" 5864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a._richcmp(b, operator.ge) 5874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __nonzero__(a): 5894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """a != 0""" 5904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return a._numerator != 0 5914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # support for pickling, copy, and deepcopy 5934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __reduce__(self): 5954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (self.__class__, (str(self),)) 5964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __copy__(self): 5984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(self) == Fraction: 5994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self # I'm immutable; therefore I am my own clone 6004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self.__class__(self._numerator, self._denominator) 6014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __deepcopy__(self, memo): 6034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if type(self) == Fraction: 6044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self # My components are also immutable 6054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self.__class__(self._numerator, self._denominator) 606