1edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# Originally contributed by Sjoerd Mullender. 2edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>. 3edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 4edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep"""Rational, infinite-precision, real numbers.""" 5edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 6edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepfrom __future__ import division 7edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepfrom decimal import Decimal 8edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepimport math 9edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepimport numbers 10edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepimport operator 11edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepimport re 12edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 13edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep__all__ = ['Fraction', 'gcd'] 14edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 15edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander StoepRational = numbers.Rational 16edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 17edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 18edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepdef gcd(a, b): 19edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """Calculate the Greatest Common Divisor of a and b. 20edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 21edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Unless b==0, the result will have the same sign as b (so that when 22edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep b is divided by it, the result comes out positive). 23edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 24edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep while b: 25edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep a, b = b, a%b 26edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a 27edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 28edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 29edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep_RATIONAL_FORMAT = re.compile(r""" 30edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep \A\s* # optional whitespace at the start, then 31edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep (?P<sign>[-+]?) # an optional sign, then 32edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep (?=\d|\.\d) # lookahead for digit or .digit 33edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep (?P<num>\d*) # numerator (possibly empty) 34edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep (?: # followed by 35edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep (?:/(?P<denom>\d+))? # an optional denominator 36edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep | # or 37edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep (?:\.(?P<decimal>\d*))? # an optional fractional part 38edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep (?:E(?P<exp>[-+]?\d+))? # and optional exponent 39edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep ) 40edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep \s*\Z # and optional whitespace to finish 41edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep""", re.VERBOSE | re.IGNORECASE) 42edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 43edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 44edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepclass Fraction(Rational): 45edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """This class implements rational numbers. 46edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 47edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep In the two-argument form of the constructor, Fraction(8, 6) will 48edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep produce a rational number equivalent to 4/3. Both arguments must 49edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep be Rational. The numerator defaults to 0 and the denominator 50edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep defaults to 1 so that Fraction(3) == 3 and Fraction() == 0. 51edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 52edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fractions can also be constructed from: 53edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 54edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep - numeric strings similar to those accepted by the 55edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep float constructor (for example, '-2.3' or '1e10') 56edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 57edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep - strings of the form '123/456' 58edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 59edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep - float and Decimal instances 60edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 61edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep - other Rational instances (including integers) 62edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 63edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 64edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 65edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep __slots__ = ('_numerator', '_denominator') 66edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 67edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # We're immutable, so use __new__ not __init__ 68edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __new__(cls, numerator=0, denominator=None): 69edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """Constructs a Fraction. 70edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 71edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Takes a string like '3/2' or '1.5', another Rational instance, a 72edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep numerator/denominator pair, or a float. 73edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 74edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Examples 75edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep -------- 76edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 77edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction(10, -8) 78edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(-5, 4) 79edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction(Fraction(1, 7), 5) 80edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(1, 35) 81edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction(Fraction(1, 7), Fraction(2, 3)) 82edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(3, 14) 83edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction('314') 84edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(314, 1) 85edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction('-35/4') 86edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(-35, 4) 87edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction('3.1415') # conversion from numeric string 88edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(6283, 2000) 89edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction('-47e-2') # string may include a decimal exponent 90edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(-47, 100) 91edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction(1.47) # direct construction from float (exact conversion) 92edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(6620291452234629, 4503599627370496) 93edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction(2.25) 94edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(9, 4) 95edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction(Decimal('1.47')) 96edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(147, 100) 97edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 98edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 99edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self = super(Fraction, cls).__new__(cls) 100edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 101edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if denominator is None: 102edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(numerator, Rational): 103edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._numerator = numerator.numerator 104edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._denominator = numerator.denominator 105edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self 106edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 107edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif isinstance(numerator, float): 108edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Exact conversion from float 109edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep value = Fraction.from_float(numerator) 110edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._numerator = value._numerator 111edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._denominator = value._denominator 112edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self 113edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 114edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif isinstance(numerator, Decimal): 115edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep value = Fraction.from_decimal(numerator) 116edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._numerator = value._numerator 117edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._denominator = value._denominator 118edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self 119edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 120edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif isinstance(numerator, basestring): 121edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Handle construction from strings. 122edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep m = _RATIONAL_FORMAT.match(numerator) 123edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if m is None: 124edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise ValueError('Invalid literal for Fraction: %r' % 125edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep numerator) 126edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep numerator = int(m.group('num') or '0') 127edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep denom = m.group('denom') 128edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if denom: 129edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep denominator = int(denom) 130edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 131edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep denominator = 1 132edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep decimal = m.group('decimal') 133edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if decimal: 134edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep scale = 10**len(decimal) 135edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep numerator = numerator * scale + int(decimal) 136edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep denominator *= scale 137edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep exp = m.group('exp') 138edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if exp: 139edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep exp = int(exp) 140edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if exp >= 0: 141edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep numerator *= 10**exp 142edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 143edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep denominator *= 10**-exp 144edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if m.group('sign') == '-': 145edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep numerator = -numerator 146edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 147edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 148edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise TypeError("argument should be a string " 149edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "or a Rational instance") 150edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 151edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif (isinstance(numerator, Rational) and 152edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep isinstance(denominator, Rational)): 153edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep numerator, denominator = ( 154edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep numerator.numerator * denominator.denominator, 155edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep denominator.numerator * numerator.denominator 156edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep ) 157edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 158edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise TypeError("both arguments should be " 159edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "Rational instances") 160edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 161edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if denominator == 0: 162edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise ZeroDivisionError('Fraction(%s, 0)' % numerator) 163edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep g = gcd(numerator, denominator) 164edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._numerator = numerator // g 165edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._denominator = denominator // g 166edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self 167edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 168edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep @classmethod 169edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def from_float(cls, f): 170edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """Converts a finite float to a rational number, exactly. 171edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 172edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Beware that Fraction.from_float(0.3) != Fraction(3, 10). 173edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 174edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 175edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(f, numbers.Integral): 176edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return cls(f) 177edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif not isinstance(f, float): 178edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise TypeError("%s.from_float() only takes floats, not %r (%s)" % 179edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep (cls.__name__, f, type(f).__name__)) 180edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if math.isnan(f) or math.isinf(f): 181edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise TypeError("Cannot convert %r to %s." % (f, cls.__name__)) 182edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return cls(*f.as_integer_ratio()) 183edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 184edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep @classmethod 185edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def from_decimal(cls, dec): 186edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """Converts a finite Decimal instance to a rational number, exactly.""" 187edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep from decimal import Decimal 188edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(dec, numbers.Integral): 189edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep dec = Decimal(int(dec)) 190edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif not isinstance(dec, Decimal): 191edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise TypeError( 192edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "%s.from_decimal() only takes Decimals, not %r (%s)" % 193edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep (cls.__name__, dec, type(dec).__name__)) 194edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if not dec.is_finite(): 195edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Catches infinities and nans. 196edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__)) 197edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep sign, digits, exp = dec.as_tuple() 198edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep digits = int(''.join(map(str, digits))) 199edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if sign: 200edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep digits = -digits 201edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if exp >= 0: 202edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return cls(digits * 10 ** exp) 203edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 204edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return cls(digits, 10 ** -exp) 205edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 206edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def limit_denominator(self, max_denominator=1000000): 207edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """Closest Fraction to self with denominator at most max_denominator. 208edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 209edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction('3.141592653589793').limit_denominator(10) 210edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(22, 7) 211edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction('3.141592653589793').limit_denominator(100) 212edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(311, 99) 213edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep >>> Fraction(4321, 8765).limit_denominator(10000) 214edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction(4321, 8765) 215edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 216edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 217edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Algorithm notes: For any real number x, define a *best upper 218edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # approximation* to x to be a rational number p/q such that: 219edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 220edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # (1) p/q >= x, and 221edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # (2) if p/q > r/s >= x then s > q, for any rational r/s. 222edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 223edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Define *best lower approximation* similarly. Then it can be 224edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # proved that a rational number is a best upper or lower 225edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # approximation to x if, and only if, it is a convergent or 226edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # semiconvergent of the (unique shortest) continued fraction 227edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # associated to x. 228edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 229edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # To find a best rational approximation with denominator <= M, 230edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # we find the best upper and lower approximations with 231edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # denominator <= M and take whichever of these is closer to x. 232edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # In the event of a tie, the bound with smaller denominator is 233edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # chosen. If both denominators are equal (which can happen 234edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # only when max_denominator == 1 and self is midway between 235edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # two integers) the lower bound---i.e., the floor of self, is 236edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # taken. 237edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 238edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if max_denominator < 1: 239edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise ValueError("max_denominator should be at least 1") 240edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self._denominator <= max_denominator: 241edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(self) 242edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 243edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep p0, q0, p1, q1 = 0, 1, 1, 0 244edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep n, d = self._numerator, self._denominator 245edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep while True: 246edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep a = n//d 247edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep q2 = q0+a*q1 248edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if q2 > max_denominator: 249edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep break 250edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep p0, q0, p1, q1 = p1, q1, p0+a*p1, q2 251edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep n, d = d, n-a*d 252edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 253edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep k = (max_denominator-q0)//q1 254edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep bound1 = Fraction(p0+k*p1, q0+k*q1) 255edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep bound2 = Fraction(p1, q1) 256edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if abs(bound2 - self) <= abs(bound1-self): 257edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return bound2 258edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 259edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return bound1 260edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 261edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep @property 262edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def numerator(a): 263edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a._numerator 264edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 265edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep @property 266edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def denominator(a): 267edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a._denominator 268edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 269edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __repr__(self): 270edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """repr(self)""" 271edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return ('Fraction(%s, %s)' % (self._numerator, self._denominator)) 272edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 273edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __str__(self): 274edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """str(self)""" 275edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self._denominator == 1: 276edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return str(self._numerator) 277edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 278edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return '%s/%s' % (self._numerator, self._denominator) 279edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 280edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def _operator_fallbacks(monomorphic_operator, fallback_operator): 281edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """Generates forward and reverse operators given a purely-rational 282edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep operator and a function from the operator module. 283edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 284edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Use this like: 285edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op) 286edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 287edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep In general, we want to implement the arithmetic operations so 288edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep that mixed-mode operations either call an implementation whose 289edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep author knew about the types of both arguments, or convert both 290edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep to the nearest built in type and do the operation there. In 291edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction, that means that we define __add__ and __radd__ as: 292edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 293edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __add__(self, other): 294edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Both types have numerators/denominator attributes, 295edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # so do the operation directly 296edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(other, (int, long, Fraction)): 297edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(self.numerator * other.denominator + 298edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep other.numerator * self.denominator, 299edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.denominator * other.denominator) 300edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # float and complex don't have those operations, but we 301edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # know about those types, so special case them. 302edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif isinstance(other, float): 303edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return float(self) + other 304edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif isinstance(other, complex): 305edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return complex(self) + other 306edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Let the other type take over. 307edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return NotImplemented 308edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 309edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __radd__(self, other): 310edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # radd handles more types than add because there's 311edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # nothing left to fall back to. 312edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(other, Rational): 313edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(self.numerator * other.denominator + 314edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep other.numerator * self.denominator, 315edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.denominator * other.denominator) 316edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif isinstance(other, Real): 317edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return float(other) + float(self) 318edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif isinstance(other, Complex): 319edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return complex(other) + complex(self) 320edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return NotImplemented 321edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 322edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 323edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep There are 5 different cases for a mixed-type addition on 324edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction. I'll refer to all of the above code that doesn't 325edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep refer to Fraction, float, or complex as "boilerplate". 'r' 326edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep will be an instance of Fraction, which is a subtype of 327edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Rational (r : Fraction <: Rational), and b : B <: 328edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Complex. The first three involve 'r + b': 329edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 330edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 1. If B <: Fraction, int, float, or complex, we handle 331edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep that specially, and all is well. 332edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 2. If Fraction falls back to the boilerplate code, and it 333edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep were to return a value from __add__, we'd miss the 334edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep possibility that B defines a more intelligent __radd__, 335edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep so the boilerplate should return NotImplemented from 336edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep __add__. In particular, we don't handle Rational 337edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep here, even though we could get an exact answer, in case 338edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep the other type wants to do something special. 339edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 3. If B <: Fraction, Python tries B.__radd__ before 340edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Fraction.__add__. This is ok, because it was 341edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep implemented with knowledge of Fraction, so it can 342edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep handle those instances before delegating to Real or 343edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Complex. 344edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 345edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep The next two situations describe 'b + r'. We assume that b 346edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep didn't know about Fraction in its implementation, and that it 347edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep uses similar boilerplate code: 348edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 349edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 4. If B <: Rational, then __radd_ converts both to the 350edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep builtin rational type (hey look, that's us) and 351edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep proceeds. 352edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 5. Otherwise, __radd__ tries to find the nearest common 353edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep base ABC, and fall back to its builtin type. Since this 354edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep class doesn't subclass a concrete type, there's no 355edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep implementation to fall back to, so we need to try as 356edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep hard as possible to return an actual value, or the user 357edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep will get a TypeError. 358edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 359edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 360edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def forward(a, b): 361edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(b, (int, long, Fraction)): 362edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return monomorphic_operator(a, b) 363edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif isinstance(b, float): 364edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return fallback_operator(float(a), b) 365edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif isinstance(b, complex): 366edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return fallback_operator(complex(a), b) 367edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 368edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return NotImplemented 369edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep forward.__name__ = '__' + fallback_operator.__name__ + '__' 370edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep forward.__doc__ = monomorphic_operator.__doc__ 371edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 372edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def reverse(b, a): 373edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(a, Rational): 374edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Includes ints. 375edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return monomorphic_operator(a, b) 376edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif isinstance(a, numbers.Real): 377edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return fallback_operator(float(a), float(b)) 378edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif isinstance(a, numbers.Complex): 379edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return fallback_operator(complex(a), complex(b)) 380edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 381edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return NotImplemented 382edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep reverse.__name__ = '__r' + fallback_operator.__name__ + '__' 383edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep reverse.__doc__ = monomorphic_operator.__doc__ 384edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 385edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return forward, reverse 386edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 387edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def _add(a, b): 388edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a + b""" 389edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(a.numerator * b.denominator + 390edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep b.numerator * a.denominator, 391edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep a.denominator * b.denominator) 392edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 393edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep __add__, __radd__ = _operator_fallbacks(_add, operator.add) 394edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 395edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def _sub(a, b): 396edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a - b""" 397edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(a.numerator * b.denominator - 398edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep b.numerator * a.denominator, 399edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep a.denominator * b.denominator) 400edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 401edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub) 402edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 403edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def _mul(a, b): 404edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a * b""" 405edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(a.numerator * b.numerator, a.denominator * b.denominator) 406edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 407edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul) 408edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 409edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def _div(a, b): 410edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a / b""" 411edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(a.numerator * b.denominator, 412edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep a.denominator * b.numerator) 413edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 414edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv) 415edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep __div__, __rdiv__ = _operator_fallbacks(_div, operator.div) 416edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 417edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __floordiv__(a, b): 418edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a // b""" 419edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Will be math.floor(a / b) in 3.0. 420edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep div = a / b 421edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(div, Rational): 422edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # trunc(math.floor(div)) doesn't work if the rational is 423edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # more precise than a float because the intermediate 424edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # rounding may cross an integer boundary. 425edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return div.numerator // div.denominator 426edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 427edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return math.floor(div) 428edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 429edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __rfloordiv__(b, a): 430edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a // b""" 431edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Will be math.floor(a / b) in 3.0. 432edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep div = a / b 433edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(div, Rational): 434edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # trunc(math.floor(div)) doesn't work if the rational is 435edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # more precise than a float because the intermediate 436edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # rounding may cross an integer boundary. 437edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return div.numerator // div.denominator 438edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 439edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return math.floor(div) 440edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 441edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __mod__(a, b): 442edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a % b""" 443edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep div = a // b 444edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a - b * div 445edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 446edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __rmod__(b, a): 447edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a % b""" 448edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep div = a // b 449edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a - b * div 450edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 451edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __pow__(a, b): 452edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a ** b 453edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 454edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep If b is not an integer, the result will be a float or complex 455edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep since roots are generally irrational. If b is an integer, the 456edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep result will be rational. 457edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 458edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 459edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(b, Rational): 460edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if b.denominator == 1: 461edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep power = b.numerator 462edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if power >= 0: 463edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(a._numerator ** power, 464edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep a._denominator ** power) 465edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 466edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(a._denominator ** -power, 467edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep a._numerator ** -power) 468edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 469edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # A fractional power will generally produce an 470edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # irrational number. 471edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return float(a) ** float(b) 472edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 473edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return float(a) ** b 474edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 475edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __rpow__(b, a): 476edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a ** b""" 477edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if b._denominator == 1 and b._numerator >= 0: 478edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # If a is an int, keep it that way if possible. 479edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a ** b._numerator 480edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 481edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(a, Rational): 482edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(a.numerator, a.denominator) ** b 483edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 484edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if b._denominator == 1: 485edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a ** b._numerator 486edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 487edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a ** float(b) 488edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 489edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __pos__(a): 490edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """+a: Coerces a subclass instance to Fraction""" 491edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(a._numerator, a._denominator) 492edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 493edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __neg__(a): 494edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """-a""" 495edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(-a._numerator, a._denominator) 496edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 497edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __abs__(a): 498edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """abs(a)""" 499edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return Fraction(abs(a._numerator), a._denominator) 500edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 501edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __trunc__(a): 502edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """trunc(a)""" 503edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if a._numerator < 0: 504edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return -(-a._numerator // a._denominator) 505edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 506edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a._numerator // a._denominator 507edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 508edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __hash__(self): 509edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """hash(self) 510edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 511edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Tricky because values that are exactly representable as a 512edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep float must have the same hash as that float. 513edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 514edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 515edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # XXX since this method is expensive, consider caching the result 516edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self._denominator == 1: 517edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Get integers right. 518edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return hash(self._numerator) 519edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Expensive check, but definitely correct. 520edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self == float(self): 521edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return hash(float(self)) 522edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 523edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Use tuple's hash to avoid a high collision rate on 524edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # simple fractions. 525edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return hash((self._numerator, self._denominator)) 526edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 527edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __eq__(a, b): 528edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a == b""" 529edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(b, Rational): 530edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return (a._numerator == b.numerator and 531edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep a._denominator == b.denominator) 532edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(b, numbers.Complex) and b.imag == 0: 533edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep b = b.real 534edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(b, float): 535edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if math.isnan(b) or math.isinf(b): 536edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # comparisons with an infinity or nan should behave in 537edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # the same way for any finite a, so treat a as zero. 538edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return 0.0 == b 539edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 540edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a == a.from_float(b) 541edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 542edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Since a doesn't know how to compare with b, let's give b 543edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # a chance to compare itself with a. 544edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return NotImplemented 545edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 546edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def _richcmp(self, other, op): 547edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """Helper for comparison operators, for internal use only. 548edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 549edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Implement comparison between a Rational instance `self`, and 550edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep either another Rational instance or a float `other`. If 551edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep `other` is not a Rational instance or a float, return 552edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep NotImplemented. `op` should be one of the six standard 553edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep comparison operators. 554edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 555edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 556edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # convert other to a Rational instance where reasonable. 557edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(other, Rational): 558edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return op(self._numerator * other.denominator, 559edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._denominator * other.numerator) 560edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # comparisons with complex should raise a TypeError, for consistency 561edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # with int<->complex, float<->complex, and complex<->complex comparisons. 562edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(other, complex): 563edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise TypeError("no ordering relation is defined for complex numbers") 564edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(other, float): 565edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if math.isnan(other) or math.isinf(other): 566edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return op(0.0, other) 567edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 568edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return op(self, self.from_float(other)) 569edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 570edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return NotImplemented 571edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 572edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __lt__(a, b): 573edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a < b""" 574edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a._richcmp(b, operator.lt) 575edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 576edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __gt__(a, b): 577edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a > b""" 578edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a._richcmp(b, operator.gt) 579edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 580edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __le__(a, b): 581edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a <= b""" 582edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a._richcmp(b, operator.le) 583edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 584edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __ge__(a, b): 585edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a >= b""" 586edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a._richcmp(b, operator.ge) 587edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 588edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __nonzero__(a): 589edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """a != 0""" 590edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return a._numerator != 0 591edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 592edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # support for pickling, copy, and deepcopy 593edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 594edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __reduce__(self): 595edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return (self.__class__, (str(self),)) 596edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 597edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __copy__(self): 598edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if type(self) == Fraction: 599edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self # I'm immutable; therefore I am my own clone 600edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self.__class__(self._numerator, self._denominator) 601edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 602edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __deepcopy__(self, memo): 603edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if type(self) == Fraction: 604edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self # My components are also immutable 605edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self.__class__(self._numerator, self._denominator) 606