1d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin# Originally contributed by Sjoerd Mullender. 2d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>. 3d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 4d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin"""Rational, infinite-precision, real numbers.""" 5d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 6d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskinfrom __future__ import division 77c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinsonfrom decimal import Decimal 8d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskinimport math 9d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskinimport numbers 10d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskinimport operator 1145169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskinimport re 12d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 13cf98f03a62c1e85eff9067cc980b630b619a1fc1Raymond Hettinger__all__ = ['Fraction', 'gcd'] 14d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 15d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark DickinsonRational = numbers.Rational 16d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 17d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 183e1a3736169fbd7e1a2234899faa64e5de75bc3eJeffrey Yasskindef gcd(a, b): 193e1a3736169fbd7e1a2234899faa64e5de75bc3eJeffrey Yasskin """Calculate the Greatest Common Divisor of a and b. 20d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 21d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Unless b==0, the result will have the same sign as b (so that when 22d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin b is divided by it, the result comes out positive). 23d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 24d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin while b: 25d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin a, b = b, a%b 26d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a 27d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 28d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 291dabdb25f83d55737c2154b63bc463240fd7bc03Mark Dickinson_RATIONAL_FORMAT = re.compile(r""" 301dabdb25f83d55737c2154b63bc463240fd7bc03Mark Dickinson \A\s* # optional whitespace at the start, then 311dabdb25f83d55737c2154b63bc463240fd7bc03Mark Dickinson (?P<sign>[-+]?) # an optional sign, then 321dabdb25f83d55737c2154b63bc463240fd7bc03Mark Dickinson (?=\d|\.\d) # lookahead for digit or .digit 331dabdb25f83d55737c2154b63bc463240fd7bc03Mark Dickinson (?P<num>\d*) # numerator (possibly empty) 348100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson (?: # followed by 358100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson (?:/(?P<denom>\d+))? # an optional denominator 361dabdb25f83d55737c2154b63bc463240fd7bc03Mark Dickinson | # or 378100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson (?:\.(?P<decimal>\d*))? # an optional fractional part 388100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson (?:E(?P<exp>[-+]?\d+))? # and optional exponent 398100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson ) 401dabdb25f83d55737c2154b63bc463240fd7bc03Mark Dickinson \s*\Z # and optional whitespace to finish 418100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson""", re.VERBOSE | re.IGNORECASE) 4245169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 4345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 44d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinsonclass Fraction(Rational): 45d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """This class implements rational numbers. 46d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 477c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson In the two-argument form of the constructor, Fraction(8, 6) will 487c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson produce a rational number equivalent to 4/3. Both arguments must 497c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson be Rational. The numerator defaults to 0 and the denominator 507c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson defaults to 1 so that Fraction(3) == 3 and Fraction() == 0. 51d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 527c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Fractions can also be constructed from: 537c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson 547c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson - numeric strings similar to those accepted by the 557c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson float constructor (for example, '-2.3' or '1e10') 567c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson 577c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson - strings of the form '123/456' 587c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson 597c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson - float and Decimal instances 607c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson 617c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson - other Rational instances (including integers) 6245169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 63d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 64d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 65dc2964b0d849389bffde95b8f76fd112049e114fJeffrey Yasskin __slots__ = ('_numerator', '_denominator') 66d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 6745169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin # We're immutable, so use __new__ not __init__ 684af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson def __new__(cls, numerator=0, denominator=None): 69d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson """Constructs a Fraction. 7045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 717c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Takes a string like '3/2' or '1.5', another Rational instance, a 727c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson numerator/denominator pair, or a float. 737c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson 747c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Examples 757c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson -------- 767c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson 777c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson >>> Fraction(10, -8) 787c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Fraction(-5, 4) 797c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson >>> Fraction(Fraction(1, 7), 5) 807c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Fraction(1, 35) 817c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson >>> Fraction(Fraction(1, 7), Fraction(2, 3)) 827c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Fraction(3, 14) 837c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson >>> Fraction('314') 847c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Fraction(314, 1) 857c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson >>> Fraction('-35/4') 867c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Fraction(-35, 4) 877c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson >>> Fraction('3.1415') # conversion from numeric string 887c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Fraction(6283, 2000) 897c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson >>> Fraction('-47e-2') # string may include a decimal exponent 907c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Fraction(-47, 100) 917c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson >>> Fraction(1.47) # direct construction from float (exact conversion) 927c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Fraction(6620291452234629, 4503599627370496) 937c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson >>> Fraction(2.25) 947c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Fraction(9, 4) 957c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson >>> Fraction(Decimal('1.47')) 967c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson Fraction(147, 100) 9745169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 9845169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin """ 99d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson self = super(Fraction, cls).__new__(cls) 10045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 1014af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson if denominator is None: 1024af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson if isinstance(numerator, Rational): 1034af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson self._numerator = numerator.numerator 1044af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson self._denominator = numerator.denominator 1054af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson return self 1064af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson 1077c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson elif isinstance(numerator, float): 1087c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson # Exact conversion from float 1097c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson value = Fraction.from_float(numerator) 1107c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson self._numerator = value._numerator 1117c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson self._denominator = value._denominator 1127c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson return self 1137c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson 1147c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson elif isinstance(numerator, Decimal): 1157c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson value = Fraction.from_decimal(numerator) 1167c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson self._numerator = value._numerator 1177c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson self._denominator = value._denominator 1187c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson return self 1197c63eee4854ef4227ce7a79c4b153e75af6aab46Mark Dickinson 1204af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson elif isinstance(numerator, basestring): 12145169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin # Handle construction from strings. 1228100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson m = _RATIONAL_FORMAT.match(numerator) 12345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if m is None: 1248100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson raise ValueError('Invalid literal for Fraction: %r' % 1258100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson numerator) 1268100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson numerator = int(m.group('num') or '0') 1278100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson denom = m.group('denom') 1288100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson if denom: 1298100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson denominator = int(denom) 1303e1a3736169fbd7e1a2234899faa64e5de75bc3eJeffrey Yasskin else: 1318100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson denominator = 1 1328100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson decimal = m.group('decimal') 1338100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson if decimal: 1348100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson scale = 10**len(decimal) 1358100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson numerator = numerator * scale + int(decimal) 1368100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson denominator *= scale 1378100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson exp = m.group('exp') 1388100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson if exp: 1398100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson exp = int(exp) 1408100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson if exp >= 0: 1418100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson numerator *= 10**exp 1428100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson else: 1438100bd8431cae4b079ffc1f0c3e33ba019661994Mark Dickinson denominator *= 10**-exp 14445169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if m.group('sign') == '-': 14545169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin numerator = -numerator 14645169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 1474af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson else: 1484af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson raise TypeError("argument should be a string " 1494af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson "or a Rational instance") 1504af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson 1514af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson elif (isinstance(numerator, Rational) and 1524af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson isinstance(denominator, Rational)): 1534af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson numerator, denominator = ( 1544af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson numerator.numerator * denominator.denominator, 1554af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson denominator.numerator * numerator.denominator 1564af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson ) 1574af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson else: 1584af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson raise TypeError("both arguments should be " 1594af8e745c4a8a225af3c3025909a8c042aafcca0Mark Dickinson "Rational instances") 160d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 161d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if denominator == 0: 162d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson raise ZeroDivisionError('Fraction(%s, 0)' % numerator) 1633e1a3736169fbd7e1a2234899faa64e5de75bc3eJeffrey Yasskin g = gcd(numerator, denominator) 1641c214d6c942df3fc7af548f7c7e10961dcaba3eeJeffrey Yasskin self._numerator = numerator // g 1651c214d6c942df3fc7af548f7c7e10961dcaba3eeJeffrey Yasskin self._denominator = denominator // g 16645169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin return self 167d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 1680aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson @classmethod 1690aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson def from_float(cls, f): 17045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin """Converts a finite float to a rational number, exactly. 17145169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 172d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson Beware that Fraction.from_float(0.3) != Fraction(3, 10). 17345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 17445169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin """ 175b01713e7dc26721e821a2b3ed8a67600d68940fbRaymond Hettinger if isinstance(f, numbers.Integral): 176fe427895b58769840f1f61a82ea0cdfe55150347Georg Brandl return cls(f) 177b01713e7dc26721e821a2b3ed8a67600d68940fbRaymond Hettinger elif not isinstance(f, float): 1780aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson raise TypeError("%s.from_float() only takes floats, not %r (%s)" % 1790aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson (cls.__name__, f, type(f).__name__)) 180d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if math.isnan(f) or math.isinf(f): 1810aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson raise TypeError("Cannot convert %r to %s." % (f, cls.__name__)) 1820aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson return cls(*f.as_integer_ratio()) 183d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 1840aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson @classmethod 1850aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson def from_decimal(cls, dec): 18645169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin """Converts a finite Decimal instance to a rational number, exactly.""" 18745169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin from decimal import Decimal 188b01713e7dc26721e821a2b3ed8a67600d68940fbRaymond Hettinger if isinstance(dec, numbers.Integral): 189b01713e7dc26721e821a2b3ed8a67600d68940fbRaymond Hettinger dec = Decimal(int(dec)) 190b01713e7dc26721e821a2b3ed8a67600d68940fbRaymond Hettinger elif not isinstance(dec, Decimal): 19145169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin raise TypeError( 1920aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson "%s.from_decimal() only takes Decimals, not %r (%s)" % 1930aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson (cls.__name__, dec, type(dec).__name__)) 19445169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if not dec.is_finite(): 19545169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin # Catches infinities and nans. 1960aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__)) 19745169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin sign, digits, exp = dec.as_tuple() 19845169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin digits = int(''.join(map(str, digits))) 19945169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if sign: 20045169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin digits = -digits 20145169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin if exp >= 0: 2020aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson return cls(digits * 10 ** exp) 20345169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin else: 2040aa52a1658adee3c9ccf32e87f5034a188592b49Mark Dickinson return cls(digits, 10 ** -exp) 20545169fbc800d573ddd01d3f440f264caaa93c622Jeffrey Yasskin 206e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson def limit_denominator(self, max_denominator=1000000): 207e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson """Closest Fraction to self with denominator at most max_denominator. 208e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson 209e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson >>> Fraction('3.141592653589793').limit_denominator(10) 210e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson Fraction(22, 7) 211e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson >>> Fraction('3.141592653589793').limit_denominator(100) 212e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson Fraction(311, 99) 213e13dc3e6d5448668bbe9adae3ea141964f829e0bMark Dickinson >>> Fraction(4321, 8765).limit_denominator(10000) 214e13dc3e6d5448668bbe9adae3ea141964f829e0bMark Dickinson Fraction(4321, 8765) 215e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson 216e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson """ 217e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # Algorithm notes: For any real number x, define a *best upper 218e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # approximation* to x to be a rational number p/q such that: 219e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # 220e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # (1) p/q >= x, and 221e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # (2) if p/q > r/s >= x then s > q, for any rational r/s. 222e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # 223e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # Define *best lower approximation* similarly. Then it can be 224e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # proved that a rational number is a best upper or lower 225e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # approximation to x if, and only if, it is a convergent or 226e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # semiconvergent of the (unique shortest) continued fraction 227e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # associated to x. 228e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # 229e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # To find a best rational approximation with denominator <= M, 230e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # we find the best upper and lower approximations with 231e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # denominator <= M and take whichever of these is closer to x. 232e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # In the event of a tie, the bound with smaller denominator is 233e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # chosen. If both denominators are equal (which can happen 234e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # only when max_denominator == 1 and self is midway between 235e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # two integers) the lower bound---i.e., the floor of self, is 236e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson # taken. 237e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson 238e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson if max_denominator < 1: 239e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson raise ValueError("max_denominator should be at least 1") 240339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin if self._denominator <= max_denominator: 241e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson return Fraction(self) 242e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson 243e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson p0, q0, p1, q1 = 0, 1, 1, 0 244339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin n, d = self._numerator, self._denominator 245e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson while True: 246e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson a = n//d 247e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson q2 = q0+a*q1 248e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson if q2 > max_denominator: 249cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger break 250e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson p0, q0, p1, q1 = p1, q1, p0+a*p1, q2 251e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson n, d = d, n-a*d 252e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson 253e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson k = (max_denominator-q0)//q1 254e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson bound1 = Fraction(p0+k*p1, q0+k*q1) 255e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson bound2 = Fraction(p1, q1) 256e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson if abs(bound2 - self) <= abs(bound1-self): 257e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson return bound2 258e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson else: 259e1b824793a4b10d5119459b47546b122a17c18b4Mark Dickinson return bound1 260cf10926088c1e8a4f2d3097e095fa0fd7d5d681aRaymond Hettinger 261dc2964b0d849389bffde95b8f76fd112049e114fJeffrey Yasskin @property 262dc2964b0d849389bffde95b8f76fd112049e114fJeffrey Yasskin def numerator(a): 263dc2964b0d849389bffde95b8f76fd112049e114fJeffrey Yasskin return a._numerator 264dc2964b0d849389bffde95b8f76fd112049e114fJeffrey Yasskin 265dc2964b0d849389bffde95b8f76fd112049e114fJeffrey Yasskin @property 266dc2964b0d849389bffde95b8f76fd112049e114fJeffrey Yasskin def denominator(a): 267dc2964b0d849389bffde95b8f76fd112049e114fJeffrey Yasskin return a._denominator 268dc2964b0d849389bffde95b8f76fd112049e114fJeffrey Yasskin 269d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __repr__(self): 270d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """repr(self)""" 2713af386a5cb935a7efbfa30f33be3be80ed4d71faMark Dickinson return ('Fraction(%s, %s)' % (self._numerator, self._denominator)) 272d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 273d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __str__(self): 274d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """str(self)""" 275339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin if self._denominator == 1: 276339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return str(self._numerator) 277d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 278339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return '%s/%s' % (self._numerator, self._denominator) 279d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 280d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def _operator_fallbacks(monomorphic_operator, fallback_operator): 281d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """Generates forward and reverse operators given a purely-rational 282d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin operator and a function from the operator module. 283d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 284d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Use this like: 285d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op) 286d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 287b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin In general, we want to implement the arithmetic operations so 288b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin that mixed-mode operations either call an implementation whose 289b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin author knew about the types of both arguments, or convert both 290b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin to the nearest built in type and do the operation there. In 291d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson Fraction, that means that we define __add__ and __radd__ as: 292b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin 293b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin def __add__(self, other): 2942df20a3e0816537db68618cef0603e89773beac4Raymond Hettinger # Both types have numerators/denominator attributes, 2952df20a3e0816537db68618cef0603e89773beac4Raymond Hettinger # so do the operation directly 296d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson if isinstance(other, (int, long, Fraction)): 297d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson return Fraction(self.numerator * other.denominator + 298b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin other.numerator * self.denominator, 299b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin self.denominator * other.denominator) 3002df20a3e0816537db68618cef0603e89773beac4Raymond Hettinger # float and complex don't have those operations, but we 3012df20a3e0816537db68618cef0603e89773beac4Raymond Hettinger # know about those types, so special case them. 302b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin elif isinstance(other, float): 303b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin return float(self) + other 304b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin elif isinstance(other, complex): 305b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin return complex(self) + other 3062df20a3e0816537db68618cef0603e89773beac4Raymond Hettinger # Let the other type take over. 3072df20a3e0816537db68618cef0603e89773beac4Raymond Hettinger return NotImplemented 308b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin 309b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin def __radd__(self, other): 310b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin # radd handles more types than add because there's 311b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin # nothing left to fall back to. 312d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson if isinstance(other, Rational): 313d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson return Fraction(self.numerator * other.denominator + 314b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin other.numerator * self.denominator, 315b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin self.denominator * other.denominator) 316b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin elif isinstance(other, Real): 317b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin return float(other) + float(self) 318b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin elif isinstance(other, Complex): 319b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin return complex(other) + complex(self) 3202df20a3e0816537db68618cef0603e89773beac4Raymond Hettinger return NotImplemented 321b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin 322b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin 323b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin There are 5 different cases for a mixed-type addition on 324d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson Fraction. I'll refer to all of the above code that doesn't 325d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson refer to Fraction, float, or complex as "boilerplate". 'r' 326d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson will be an instance of Fraction, which is a subtype of 327d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson Rational (r : Fraction <: Rational), and b : B <: 328b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin Complex. The first three involve 'r + b': 329b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin 330d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson 1. If B <: Fraction, int, float, or complex, we handle 331b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin that specially, and all is well. 332d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson 2. If Fraction falls back to the boilerplate code, and it 333b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin were to return a value from __add__, we'd miss the 334b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin possibility that B defines a more intelligent __radd__, 335b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin so the boilerplate should return NotImplemented from 336d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson __add__. In particular, we don't handle Rational 337b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin here, even though we could get an exact answer, in case 338b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin the other type wants to do something special. 339d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson 3. If B <: Fraction, Python tries B.__radd__ before 340d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson Fraction.__add__. This is ok, because it was 341d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson implemented with knowledge of Fraction, so it can 342b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin handle those instances before delegating to Real or 343b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin Complex. 344b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin 345b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin The next two situations describe 'b + r'. We assume that b 346d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson didn't know about Fraction in its implementation, and that it 347b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin uses similar boilerplate code: 348b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin 349d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson 4. If B <: Rational, then __radd_ converts both to the 350b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin builtin rational type (hey look, that's us) and 351b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin proceeds. 352b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin 5. Otherwise, __radd__ tries to find the nearest common 353b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin base ABC, and fall back to its builtin type. Since this 354b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin class doesn't subclass a concrete type, there's no 355b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin implementation to fall back to, so we need to try as 356b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin hard as possible to return an actual value, or the user 357b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin will get a TypeError. 358b23dea6adb7eaf3f415e05b129afa01fa1c4dd5cJeffrey Yasskin 359d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 360d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def forward(a, b): 361d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson if isinstance(b, (int, long, Fraction)): 362d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return monomorphic_operator(a, b) 363d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin elif isinstance(b, float): 364d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return fallback_operator(float(a), b) 365d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin elif isinstance(b, complex): 366d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return fallback_operator(complex(a), b) 367d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 368d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return NotImplemented 369d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin forward.__name__ = '__' + fallback_operator.__name__ + '__' 370d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin forward.__doc__ = monomorphic_operator.__doc__ 371d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 372d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def reverse(b, a): 373d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson if isinstance(a, Rational): 374d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Includes ints. 375d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return monomorphic_operator(a, b) 376d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin elif isinstance(a, numbers.Real): 377d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return fallback_operator(float(a), float(b)) 378d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin elif isinstance(a, numbers.Complex): 379d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return fallback_operator(complex(a), complex(b)) 380d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 381d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return NotImplemented 382d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin reverse.__name__ = '__r' + fallback_operator.__name__ + '__' 383d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin reverse.__doc__ = monomorphic_operator.__doc__ 384d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 385d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return forward, reverse 386d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 387d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def _add(a, b): 388d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a + b""" 389d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson return Fraction(a.numerator * b.denominator + 390d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin b.numerator * a.denominator, 391d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin a.denominator * b.denominator) 392d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 393d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __add__, __radd__ = _operator_fallbacks(_add, operator.add) 394d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 395d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def _sub(a, b): 396d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a - b""" 397d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson return Fraction(a.numerator * b.denominator - 398d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin b.numerator * a.denominator, 399d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin a.denominator * b.denominator) 400d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 401d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub) 402d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 403d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def _mul(a, b): 404d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a * b""" 405d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson return Fraction(a.numerator * b.numerator, a.denominator * b.denominator) 406d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 407d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul) 408d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 409d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def _div(a, b): 410d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a / b""" 411d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson return Fraction(a.numerator * b.denominator, 412d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin a.denominator * b.numerator) 413d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 414d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv) 415d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin __div__, __rdiv__ = _operator_fallbacks(_div, operator.div) 416d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 417909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger def __floordiv__(a, b): 418909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger """a // b""" 419909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger # Will be math.floor(a / b) in 3.0. 420d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin div = a / b 421d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson if isinstance(div, Rational): 422d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # trunc(math.floor(div)) doesn't work if the rational is 423d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # more precise than a float because the intermediate 424d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # rounding may cross an integer boundary. 425d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return div.numerator // div.denominator 426d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 427d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return math.floor(div) 428d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 429d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __rfloordiv__(b, a): 430d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a // b""" 431d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Will be math.floor(a / b) in 3.0. 432909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger div = a / b 433d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson if isinstance(div, Rational): 434909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger # trunc(math.floor(div)) doesn't work if the rational is 435909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger # more precise than a float because the intermediate 436909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger # rounding may cross an integer boundary. 437909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger return div.numerator // div.denominator 438909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger else: 439909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger return math.floor(div) 440d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 441d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __mod__(a, b): 442d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a % b""" 443909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger div = a // b 444909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger return a - b * div 445d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 446d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __rmod__(b, a): 447d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a % b""" 448909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger div = a // b 449909e334e8a525e8430f1532c0ecf133f19d3d185Raymond Hettinger return a - b * div 450d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 451d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __pow__(a, b): 452d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a ** b 453d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 454d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin If b is not an integer, the result will be a float or complex 455d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin since roots are generally irrational. If b is an integer, the 456d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin result will be rational. 457d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 458d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 459d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson if isinstance(b, Rational): 460d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if b.denominator == 1: 461d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin power = b.numerator 462d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if power >= 0: 463339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return Fraction(a._numerator ** power, 464339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin a._denominator ** power) 465d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 466339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return Fraction(a._denominator ** -power, 467339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin a._numerator ** -power) 468d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 469d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # A fractional power will generally produce an 470d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # irrational number. 471d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return float(a) ** float(b) 472d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 473d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return float(a) ** b 474d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 475d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __rpow__(b, a): 476d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a ** b""" 477339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin if b._denominator == 1 and b._numerator >= 0: 478d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # If a is an int, keep it that way if possible. 479339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return a ** b._numerator 480d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 481d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson if isinstance(a, Rational): 482d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson return Fraction(a.numerator, a.denominator) ** b 483d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 484339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin if b._denominator == 1: 485339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return a ** b._numerator 486d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 487d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return a ** float(b) 488d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 489d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __pos__(a): 490d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson """+a: Coerces a subclass instance to Fraction""" 491339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return Fraction(a._numerator, a._denominator) 492d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 493d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __neg__(a): 494d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """-a""" 495339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return Fraction(-a._numerator, a._denominator) 496d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 497d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __abs__(a): 498d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """abs(a)""" 499339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return Fraction(abs(a._numerator), a._denominator) 500d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 501d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __trunc__(a): 502d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """trunc(a)""" 503339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin if a._numerator < 0: 504339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return -(-a._numerator // a._denominator) 505d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 506339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return a._numerator // a._denominator 507d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 508d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __hash__(self): 509d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """hash(self) 510d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 511d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin Tricky because values that are exactly representable as a 512d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin float must have the same hash as that float. 513d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 514d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 515921cb5d3a3e823c6c225681d8e99f7baa8920f3eRaymond Hettinger # XXX since this method is expensive, consider caching the result 516339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin if self._denominator == 1: 517d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Get integers right. 518339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return hash(self._numerator) 519d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Expensive check, but definitely correct. 520d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if self == float(self): 521d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return hash(float(self)) 522d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 523d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # Use tuple's hash to avoid a high collision rate on 524d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin # simple fractions. 525339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return hash((self._numerator, self._denominator)) 526d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 527d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __eq__(a, b): 528d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a == b""" 529d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson if isinstance(b, Rational): 530339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return (a._numerator == b.numerator and 531339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin a._denominator == b.denominator) 532d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(b, numbers.Complex) and b.imag == 0: 533d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin b = b.real 534d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin if isinstance(b, float): 53588a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson if math.isnan(b) or math.isinf(b): 53688a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson # comparisons with an infinity or nan should behave in 53788a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson # the same way for any finite a, so treat a as zero. 53888a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson return 0.0 == b 53988a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson else: 54088a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson return a == a.from_float(b) 541d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin else: 54288a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson # Since a doesn't know how to compare with b, let's give b 54388a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson # a chance to compare itself with a. 54488a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson return NotImplemented 545d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 54688a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson def _richcmp(self, other, op): 54788a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson """Helper for comparison operators, for internal use only. 548d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 54988a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson Implement comparison between a Rational instance `self`, and 55088a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson either another Rational instance or a float `other`. If 55188a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson `other` is not a Rational instance or a float, return 55288a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson NotImplemented. `op` should be one of the six standard 55388a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson comparison operators. 554d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 555d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """ 55688a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson # convert other to a Rational instance where reasonable. 55788a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson if isinstance(other, Rational): 55888a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson return op(self._numerator * other.denominator, 55988a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson self._denominator * other.numerator) 56071b7fac07ba978630844bdabee59492e329d036cMark Dickinson # comparisons with complex should raise a TypeError, for consistency 56171b7fac07ba978630844bdabee59492e329d036cMark Dickinson # with int<->complex, float<->complex, and complex<->complex comparisons. 56271b7fac07ba978630844bdabee59492e329d036cMark Dickinson if isinstance(other, complex): 56371b7fac07ba978630844bdabee59492e329d036cMark Dickinson raise TypeError("no ordering relation is defined for complex numbers") 56488a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson if isinstance(other, float): 56588a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson if math.isnan(other) or math.isinf(other): 56688a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson return op(0.0, other) 56788a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson else: 56888a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson return op(self, self.from_float(other)) 56988a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson else: 570d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin return NotImplemented 571d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 572d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __lt__(a, b): 573d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a < b""" 57488a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson return a._richcmp(b, operator.lt) 575d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 576d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __gt__(a, b): 577d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a > b""" 57888a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson return a._richcmp(b, operator.gt) 579d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 580d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __le__(a, b): 581d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a <= b""" 58288a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson return a._richcmp(b, operator.le) 583d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 584d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __ge__(a, b): 585d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a >= b""" 58688a0a2e47fa60c26b3662ef5ee152fd78181c7b1Mark Dickinson return a._richcmp(b, operator.ge) 587d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin 588d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin def __nonzero__(a): 589d7b00334f3cbf7a802e875238b9f2bd95e190436Jeffrey Yasskin """a != 0""" 590339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return a._numerator != 0 591a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger 592a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger # support for pickling, copy, and deepcopy 593a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger 594a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger def __reduce__(self): 595a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger return (self.__class__, (str(self),)) 596a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger 597a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger def __copy__(self): 598d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson if type(self) == Fraction: 599a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger return self # I'm immutable; therefore I am my own clone 600339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return self.__class__(self._numerator, self._denominator) 601a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger 602a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger def __deepcopy__(self, memo): 603d058cd2cc8e2a3f61609b92a8fc821ea8ec524caMark Dickinson if type(self) == Fraction: 604a6216749fb88fb508cd469839d77d4264a881bd4Raymond Hettinger return self # My components are also immutable 605339f5e3ffc4d1005020ffc2fc85fcc618c7461faJeffrey Yasskin return self.__class__(self._numerator, self._denominator) 606