Lib/fractions.py

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