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