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