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: ' + 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
 100         numerator = numerator.__index__()
 101         denominator = denominator.__index__()
 102         g = gcd(numerator, denominator)
 103         self._numerator = numerator // g
 104         self._denominator = denominator // g
 105         return self
 106
 107     @classmethod
 108     def from_float(cls, f):
 109         """Converts a finite float to a rational number, exactly.
 110
 111         Beware that Fraction.from_float(0.3) != Fraction(3, 10).
 112
 113         """
 114         if not isinstance(f, float):
 115             raise TypeError("%s.from_float() only takes floats, not %r (%s)" %
 116                             (cls.__name__, f, type(f).__name__))
 117         if math.isnan(f) or math.isinf(f):
 118             raise TypeError("Cannot convert %r to %s." % (f, cls.__name__))
 119         return cls(*f.as_integer_ratio())
 120
 121     @classmethod
 122     def from_decimal(cls, dec):
 123         """Converts a finite Decimal instance to a rational number, exactly."""
 124         from decimal import Decimal
 125         if not isinstance(dec, Decimal):
 126             raise TypeError(
 127                 "%s.from_decimal() only takes Decimals, not %r (%s)" %
 128                 (cls.__name__, dec, type(dec).__name__))
 129         if not dec.is_finite():
 130             # Catches infinities and nans.
 131             raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__))
 132         sign, digits, exp = dec.as_tuple()
 133         digits = int(''.join(map(str, digits)))
 134         if sign:
 135             digits = -digits
 136         if exp >= 0:
 137             return cls(digits * 10 ** exp)
 138         else:
 139             return cls(digits, 10 ** -exp)
 140
 141     def limit_denominator(self, max_denominator=1000000):
 142         """Closest Fraction to self with denominator at most max_denominator.
 143
 144         >>> Fraction('3.141592653589793').limit_denominator(10)
 145         Fraction(22, 7)
 146         >>> Fraction('3.141592653589793').limit_denominator(100)
 147         Fraction(311, 99)
 148         >>> Fraction(1234, 5678).limit_denominator(10000)
 149         Fraction(1234, 5678)
 150
 151         """
 152         # Algorithm notes: For any real number x, define a *best upper
 153         # approximation* to x to be a rational number p/q such that:
 154         #
 155         #   (1) p/q >= x, and
 156         #   (2) if p/q > r/s >= x then s > q, for any rational r/s.
 157         #
 158         # Define *best lower approximation* similarly.  Then it can be
 159         # proved that a rational number is a best upper or lower
 160         # approximation to x if, and only if, it is a convergent or
 161         # semiconvergent of the (unique shortest) continued fraction
 162         # associated to x.
 163         #
 164         # To find a best rational approximation with denominator <= M,
 165         # we find the best upper and lower approximations with
 166         # denominator <= M and take whichever of these is closer to x.
 167         # In the event of a tie, the bound with smaller denominator is
 168         # chosen.  If both denominators are equal (which can happen
 169         # only when max_denominator == 1 and self is midway between
 170         # two integers) the lower bound---i.e., the floor of self, is
 171         # taken.
 172
 173         if max_denominator < 1:
 174             raise ValueError("max_denominator should be at least 1")
 175         if self._denominator <= max_denominator:
 176             return Fraction(self)
 177
 178         p0, q0, p1, q1 = 0, 1, 1, 0
 179         n, d = self._numerator, self._denominator
 180         while True:
 181             a = n//d
 182             q2 = q0+a*q1
 183             if q2 > max_denominator:
 184                 break
 185             p0, q0, p1, q1 = p1, q1, p0+a*p1, q2
 186             n, d = d, n-a*d
 187
 188         k = (max_denominator-q0)//q1
 189         bound1 = Fraction(p0+k*p1, q0+k*q1)
 190         bound2 = Fraction(p1, q1)
 191         if abs(bound2 - self) <= abs(bound1-self):
 192             return bound2
 193         else:
 194             return bound1
 195
 196     @property
 197     def numerator(a):
 198         return a._numerator
 199
 200     @property
 201     def denominator(a):
 202         return a._denominator
 203
 204     def __repr__(self):
 205         """repr(self)"""
 206         return ('Fraction(%r, %r)' % (self._numerator, self._denominator))
 207
 208     def __str__(self):
 209         """str(self)"""
 210         if self._denominator == 1:
 211             return str(self._numerator)
 212         else:
 213             return '%s/%s' % (self._numerator, self._denominator)
 214
 215     def _operator_fallbacks(monomorphic_operator, fallback_operator):
 216         """Generates forward and reverse operators given a purely-rational
 217         operator and a function from the operator module.
 218
 219         Use this like:
 220         __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op)
 221
 222         In general, we want to implement the arithmetic operations so
 223         that mixed-mode operations either call an implementation whose
 224         author knew about the types of both arguments, or convert both
 225         to the nearest built in type and do the operation there. In
 226         Fraction, that means that we define __add__ and __radd__ as:
 227
 228             def __add__(self, other):
 229                 # Both types have numerators/denominator attributes,
 230                 # so do the operation directly
 231                 if isinstance(other, (int, long, Fraction)):
 232                     return Fraction(self.numerator * other.denominator +
 233                                     other.numerator * self.denominator,
 234                                     self.denominator * other.denominator)
 235                 # float and complex don't have those operations, but we
 236                 # know about those types, so special case them.
 237                 elif isinstance(other, float):
 238                     return float(self) + other
 239                 elif isinstance(other, complex):
 240                     return complex(self) + other
 241                 # Let the other type take over.
 242                 return NotImplemented
 243
 244             def __radd__(self, other):
 245                 # radd handles more types than add because there's
 246                 # nothing left to fall back to.
 247                 if isinstance(other, Rational):
 248                     return Fraction(self.numerator * other.denominator +
 249                                     other.numerator * self.denominator,
 250                                     self.denominator * other.denominator)
 251                 elif isinstance(other, Real):
 252                     return float(other) + float(self)
 253                 elif isinstance(other, Complex):
 254                     return complex(other) + complex(self)
 255                 return NotImplemented
 256
 257
 258         There are 5 different cases for a mixed-type addition on
 259         Fraction. I'll refer to all of the above code that doesn't
 260         refer to Fraction, float, or complex as "boilerplate". 'r'
 261         will be an instance of Fraction, which is a subtype of
 262         Rational (r : Fraction <: Rational), and b : B <:
 263         Complex. The first three involve 'r + b':
 264
 265             1. If B <: Fraction, int, float, or complex, we handle
 266                that specially, and all is well.
 267             2. If Fraction falls back to the boilerplate code, and it
 268                were to return a value from __add__, we'd miss the
 269                possibility that B defines a more intelligent __radd__,
 270                so the boilerplate should return NotImplemented from
 271                __add__. In particular, we don't handle Rational
 272                here, even though we could get an exact answer, in case
 273                the other type wants to do something special.
 274             3. If B <: Fraction, Python tries B.__radd__ before
 275                Fraction.__add__. This is ok, because it was
 276                implemented with knowledge of Fraction, so it can
 277                handle those instances before delegating to Real or
 278                Complex.
 279
 280         The next two situations describe 'b + r'. We assume that b
 281         didn't know about Fraction in its implementation, and that it
 282         uses similar boilerplate code:
 283
 284             4. If B <: Rational, then __radd_ converts both to the
 285                builtin rational type (hey look, that's us) and
 286                proceeds.
 287             5. Otherwise, __radd__ tries to find the nearest common
 288                base ABC, and fall back to its builtin type. Since this
 289                class doesn't subclass a concrete type, there's no
 290                implementation to fall back to, so we need to try as
 291                hard as possible to return an actual value, or the user
 292                will get a TypeError.
 293
 294         """
 295         def forward(a, b):
 296             if isinstance(b, (int, long, Fraction)):
 297                 return monomorphic_operator(a, b)
 298             elif isinstance(b, float):
 299                 return fallback_operator(float(a), b)
 300             elif isinstance(b, complex):
 301                 return fallback_operator(complex(a), b)
 302             else:
 303                 return NotImplemented
 304         forward.__name__ = '__' + fallback_operator.__name__ + '__'
 305         forward.__doc__ = monomorphic_operator.__doc__
 306
 307         def reverse(b, a):
 308             if isinstance(a, Rational):
 309                 # Includes ints.
 310                 return monomorphic_operator(a, b)
 311             elif isinstance(a, numbers.Real):
 312                 return fallback_operator(float(a), float(b))
 313             elif isinstance(a, numbers.Complex):
 314                 return fallback_operator(complex(a), complex(b))
 315             else:
 316                 return NotImplemented
 317         reverse.__name__ = '__r' + fallback_operator.__name__ + '__'
 318         reverse.__doc__ = monomorphic_operator.__doc__
 319
 320         return forward, reverse
 321
 322     def _add(a, b):
 323         """a + b"""
 324         return Fraction(a.numerator * b.denominator +
 325                         b.numerator * a.denominator,
 326                         a.denominator * b.denominator)
 327
 328     __add__, __radd__ = _operator_fallbacks(_add, operator.add)
 329
 330     def _sub(a, b):
 331         """a - b"""
 332         return Fraction(a.numerator * b.denominator -
 333                         b.numerator * a.denominator,
 334                         a.denominator * b.denominator)
 335
 336     __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)
 337
 338     def _mul(a, b):
 339         """a * b"""
 340         return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)
 341
 342     __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)
 343
 344     def _div(a, b):
 345         """a / b"""
 346         return Fraction(a.numerator * b.denominator,
 347                         a.denominator * b.numerator)
 348
 349     __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)
 350     __div__, __rdiv__ = _operator_fallbacks(_div, operator.div)
 351
 352     def __floordiv__(a, b):
 353         """a // b"""
 354         # Will be math.floor(a / b) in 3.0.
 355         div = a / b
 356         if isinstance(div, Rational):
 357             # trunc(math.floor(div)) doesn't work if the rational is
 358             # more precise than a float because the intermediate
 359             # rounding may cross an integer boundary.
 360             return div.numerator // div.denominator
 361         else:
 362             return math.floor(div)
 363
 364     def __rfloordiv__(b, a):
 365         """a // b"""
 366         # Will be math.floor(a / b) in 3.0.
 367         div = a / b
 368         if isinstance(div, Rational):
 369             # trunc(math.floor(div)) doesn't work if the rational is
 370             # more precise than a float because the intermediate
 371             # rounding may cross an integer boundary.
 372             return div.numerator // div.denominator
 373         else:
 374             return math.floor(div)
 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, 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, 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 __hash__(self):
 444         """hash(self)
 445
 446         Tricky because values that are exactly representable as a
 447         float must have the same hash as that float.
 448
 449         """
 450         # XXX since this method is expensive, consider caching the result
 451         if self._denominator == 1:
 452             # Get integers right.
 453             return hash(self._numerator)
 454         # Expensive check, but definitely correct.
 455         if self == float(self):
 456             return hash(float(self))
 457         else:
 458             # Use tuple's hash to avoid a high collision rate on
 459             # simple fractions.
 460             return hash((self._numerator, self._denominator))
 461
 462     def __eq__(a, b):
 463         """a == b"""
 464         if isinstance(b, Rational):
 465             return (a._numerator == b.numerator and
 466                     a._denominator == b.denominator)
 467         if isinstance(b, numbers.Complex) and b.imag == 0:
 468             b = b.real
 469         if isinstance(b, float):
 470             return a == a.from_float(b)
 471         else:
 472             # XXX: If b.__eq__ is implemented like this method, it may
 473             # give the wrong answer after float(a) changes a's
 474             # value. Better ways of doing this are welcome.
 475             return float(a) == b
 476
 477     def _subtractAndCompareToZero(a, b, op):
 478         """Helper function for comparison operators.
 479
 480         Subtracts b from a, exactly if possible, and compares the
 481         result with 0 using op, in such a way that the comparison
 482         won't recurse. If the difference raises a TypeError, returns
 483         NotImplemented instead.
 484
 485         """
 486         if isinstance(b, numbers.Complex) and b.imag == 0:
 487             b = b.real
 488         if isinstance(b, float):
 489             b = a.from_float(b)
 490         try:
 491             # XXX: If b <: Real but not <: Rational, this is likely
 492             # to fall back to a float. If the actual values differ by
 493             # less than MIN_FLOAT, this could falsely call them equal,
 494             # which would make <= inconsistent with ==. Better ways of
 495             # doing this are welcome.
 496             diff = a - b
 497         except TypeError:
 498             return NotImplemented
 499         if isinstance(diff, Rational):
 500             return op(diff.numerator, 0)
 501         return op(diff, 0)
 502
 503     def __lt__(a, b):
 504         """a < b"""
 505         return a._subtractAndCompareToZero(b, operator.lt)
 506
 507     def __gt__(a, b):
 508         """a > b"""
 509         return a._subtractAndCompareToZero(b, operator.gt)
 510
 511     def __le__(a, b):
 512         """a <= b"""
 513         return a._subtractAndCompareToZero(b, operator.le)
 514
 515     def __ge__(a, b):
 516         """a >= b"""
 517         return a._subtractAndCompareToZero(b, operator.ge)
 518
 519     def __nonzero__(a):
 520         """a != 0"""
 521         return a._numerator != 0
 522
 523     # support for pickling, copy, and deepcopy
 524
 525     def __reduce__(self):
 526         return (self.__class__, (str(self),))
 527
 528     def __copy__(self):
 529         if type(self) == Fraction:
 530             return self     # I'm immutable; therefore I am my own clone
 531         return self.__class__(self._numerator, self._denominator)
 532
 533     def __deepcopy__(self, memo):
 534         if type(self) == Fraction:
 535             return self     # My components are also immutable
 536         return self.__class__(self._numerator, self._denominator)