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