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