Lib/fractions.py

   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)