Back to index

python3.2  3.2.2
fractions.py
Go to the documentation of this file.
00001 # Originally contributed by Sjoerd Mullender.
00002 # Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>.
00003 
00004 """Fraction, infinite-precision, real numbers."""
00005 
00006 from decimal import Decimal
00007 import math
00008 import numbers
00009 import operator
00010 import re
00011 import sys
00012 
00013 __all__ = ['Fraction', 'gcd']
00014 
00015 
00016 
00017 def gcd(a, b):
00018     """Calculate the Greatest Common Divisor of a and b.
00019 
00020     Unless b==0, the result will have the same sign as b (so that when
00021     b is divided by it, the result comes out positive).
00022     """
00023     while b:
00024         a, b = b, a%b
00025     return a
00026 
00027 # Constants related to the hash implementation;  hash(x) is based
00028 # on the reduction of x modulo the prime _PyHASH_MODULUS.
00029 _PyHASH_MODULUS = sys.hash_info.modulus
00030 # Value to be used for rationals that reduce to infinity modulo
00031 # _PyHASH_MODULUS.
00032 _PyHASH_INF = sys.hash_info.inf
00033 
00034 _RATIONAL_FORMAT = re.compile(r"""
00035     \A\s*                      # optional whitespace at the start, then
00036     (?P<sign>[-+]?)            # an optional sign, then
00037     (?=\d|\.\d)                # lookahead for digit or .digit
00038     (?P<num>\d*)               # numerator (possibly empty)
00039     (?:                        # followed by
00040        (?:/(?P<denom>\d+))?    # an optional denominator
00041     |                          # or
00042        (?:\.(?P<decimal>\d*))? # an optional fractional part
00043        (?:E(?P<exp>[-+]?\d+))? # and optional exponent
00044     )
00045     \s*\Z                      # and optional whitespace to finish
00046 """, re.VERBOSE | re.IGNORECASE)
00047 
00048 
00049 class Fraction(numbers.Rational):
00050     """This class implements rational numbers.
00051 
00052     In the two-argument form of the constructor, Fraction(8, 6) will
00053     produce a rational number equivalent to 4/3. Both arguments must
00054     be Rational. The numerator defaults to 0 and the denominator
00055     defaults to 1 so that Fraction(3) == 3 and Fraction() == 0.
00056 
00057     Fractions can also be constructed from:
00058 
00059       - numeric strings similar to those accepted by the
00060         float constructor (for example, '-2.3' or '1e10')
00061 
00062       - strings of the form '123/456'
00063 
00064       - float and Decimal instances
00065 
00066       - other Rational instances (including integers)
00067 
00068     """
00069 
00070     __slots__ = ('_numerator', '_denominator')
00071 
00072     # We're immutable, so use __new__ not __init__
00073     def __new__(cls, numerator=0, denominator=None):
00074         """Constructs a Rational.
00075 
00076         Takes a string like '3/2' or '1.5', another Rational instance, a
00077         numerator/denominator pair, or a float.
00078 
00079         Examples
00080         --------
00081 
00082         >>> Fraction(10, -8)
00083         Fraction(-5, 4)
00084         >>> Fraction(Fraction(1, 7), 5)
00085         Fraction(1, 35)
00086         >>> Fraction(Fraction(1, 7), Fraction(2, 3))
00087         Fraction(3, 14)
00088         >>> Fraction('314')
00089         Fraction(314, 1)
00090         >>> Fraction('-35/4')
00091         Fraction(-35, 4)
00092         >>> Fraction('3.1415') # conversion from numeric string
00093         Fraction(6283, 2000)
00094         >>> Fraction('-47e-2') # string may include a decimal exponent
00095         Fraction(-47, 100)
00096         >>> Fraction(1.47)  # direct construction from float (exact conversion)
00097         Fraction(6620291452234629, 4503599627370496)
00098         >>> Fraction(2.25)
00099         Fraction(9, 4)
00100         >>> Fraction(Decimal('1.47'))
00101         Fraction(147, 100)
00102 
00103         """
00104         self = super(Fraction, cls).__new__(cls)
00105 
00106         if denominator is None:
00107             if isinstance(numerator, numbers.Rational):
00108                 self._numerator = numerator.numerator
00109                 self._denominator = numerator.denominator
00110                 return self
00111 
00112             elif isinstance(numerator, float):
00113                 # Exact conversion from float
00114                 value = Fraction.from_float(numerator)
00115                 self._numerator = value._numerator
00116                 self._denominator = value._denominator
00117                 return self
00118 
00119             elif isinstance(numerator, Decimal):
00120                 value = Fraction.from_decimal(numerator)
00121                 self._numerator = value._numerator
00122                 self._denominator = value._denominator
00123                 return self
00124 
00125             elif isinstance(numerator, str):
00126                 # Handle construction from strings.
00127                 m = _RATIONAL_FORMAT.match(numerator)
00128                 if m is None:
00129                     raise ValueError('Invalid literal for Fraction: %r' %
00130                                      numerator)
00131                 numerator = int(m.group('num') or '0')
00132                 denom = m.group('denom')
00133                 if denom:
00134                     denominator = int(denom)
00135                 else:
00136                     denominator = 1
00137                     decimal = m.group('decimal')
00138                     if decimal:
00139                         scale = 10**len(decimal)
00140                         numerator = numerator * scale + int(decimal)
00141                         denominator *= scale
00142                     exp = m.group('exp')
00143                     if exp:
00144                         exp = int(exp)
00145                         if exp >= 0:
00146                             numerator *= 10**exp
00147                         else:
00148                             denominator *= 10**-exp
00149                 if m.group('sign') == '-':
00150                     numerator = -numerator
00151 
00152             else:
00153                 raise TypeError("argument should be a string "
00154                                 "or a Rational instance")
00155 
00156         elif (isinstance(numerator, numbers.Rational) and
00157             isinstance(denominator, numbers.Rational)):
00158             numerator, denominator = (
00159                 numerator.numerator * denominator.denominator,
00160                 denominator.numerator * numerator.denominator
00161                 )
00162         else:
00163             raise TypeError("both arguments should be "
00164                             "Rational instances")
00165 
00166         if denominator == 0:
00167             raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
00168         g = gcd(numerator, denominator)
00169         self._numerator = numerator // g
00170         self._denominator = denominator // g
00171         return self
00172 
00173     @classmethod
00174     def from_float(cls, f):
00175         """Converts a finite float to a rational number, exactly.
00176 
00177         Beware that Fraction.from_float(0.3) != Fraction(3, 10).
00178 
00179         """
00180         if isinstance(f, numbers.Integral):
00181             return cls(f)
00182         elif not isinstance(f, float):
00183             raise TypeError("%s.from_float() only takes floats, not %r (%s)" %
00184                             (cls.__name__, f, type(f).__name__))
00185         if math.isnan(f) or math.isinf(f):
00186             raise TypeError("Cannot convert %r to %s." % (f, cls.__name__))
00187         return cls(*f.as_integer_ratio())
00188 
00189     @classmethod
00190     def from_decimal(cls, dec):
00191         """Converts a finite Decimal instance to a rational number, exactly."""
00192         from decimal import Decimal
00193         if isinstance(dec, numbers.Integral):
00194             dec = Decimal(int(dec))
00195         elif not isinstance(dec, Decimal):
00196             raise TypeError(
00197                 "%s.from_decimal() only takes Decimals, not %r (%s)" %
00198                 (cls.__name__, dec, type(dec).__name__))
00199         if not dec.is_finite():
00200             # Catches infinities and nans.
00201             raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__))
00202         sign, digits, exp = dec.as_tuple()
00203         digits = int(''.join(map(str, digits)))
00204         if sign:
00205             digits = -digits
00206         if exp >= 0:
00207             return cls(digits * 10 ** exp)
00208         else:
00209             return cls(digits, 10 ** -exp)
00210 
00211     def limit_denominator(self, max_denominator=1000000):
00212         """Closest Fraction to self with denominator at most max_denominator.
00213 
00214         >>> Fraction('3.141592653589793').limit_denominator(10)
00215         Fraction(22, 7)
00216         >>> Fraction('3.141592653589793').limit_denominator(100)
00217         Fraction(311, 99)
00218         >>> Fraction(4321, 8765).limit_denominator(10000)
00219         Fraction(4321, 8765)
00220 
00221         """
00222         # Algorithm notes: For any real number x, define a *best upper
00223         # approximation* to x to be a rational number p/q such that:
00224         #
00225         #   (1) p/q >= x, and
00226         #   (2) if p/q > r/s >= x then s > q, for any rational r/s.
00227         #
00228         # Define *best lower approximation* similarly.  Then it can be
00229         # proved that a rational number is a best upper or lower
00230         # approximation to x if, and only if, it is a convergent or
00231         # semiconvergent of the (unique shortest) continued fraction
00232         # associated to x.
00233         #
00234         # To find a best rational approximation with denominator <= M,
00235         # we find the best upper and lower approximations with
00236         # denominator <= M and take whichever of these is closer to x.
00237         # In the event of a tie, the bound with smaller denominator is
00238         # chosen.  If both denominators are equal (which can happen
00239         # only when max_denominator == 1 and self is midway between
00240         # two integers) the lower bound---i.e., the floor of self, is
00241         # taken.
00242 
00243         if max_denominator < 1:
00244             raise ValueError("max_denominator should be at least 1")
00245         if self._denominator <= max_denominator:
00246             return Fraction(self)
00247 
00248         p0, q0, p1, q1 = 0, 1, 1, 0
00249         n, d = self._numerator, self._denominator
00250         while True:
00251             a = n//d
00252             q2 = q0+a*q1
00253             if q2 > max_denominator:
00254                 break
00255             p0, q0, p1, q1 = p1, q1, p0+a*p1, q2
00256             n, d = d, n-a*d
00257 
00258         k = (max_denominator-q0)//q1
00259         bound1 = Fraction(p0+k*p1, q0+k*q1)
00260         bound2 = Fraction(p1, q1)
00261         if abs(bound2 - self) <= abs(bound1-self):
00262             return bound2
00263         else:
00264             return bound1
00265 
00266     @property
00267     def numerator(a):
00268         return a._numerator
00269 
00270     @property
00271     def denominator(a):
00272         return a._denominator
00273 
00274     def __repr__(self):
00275         """repr(self)"""
00276         return ('Fraction(%s, %s)' % (self._numerator, self._denominator))
00277 
00278     def __str__(self):
00279         """str(self)"""
00280         if self._denominator == 1:
00281             return str(self._numerator)
00282         else:
00283             return '%s/%s' % (self._numerator, self._denominator)
00284 
00285     def _operator_fallbacks(monomorphic_operator, fallback_operator):
00286         """Generates forward and reverse operators given a purely-rational
00287         operator and a function from the operator module.
00288 
00289         Use this like:
00290         __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op)
00291 
00292         In general, we want to implement the arithmetic operations so
00293         that mixed-mode operations either call an implementation whose
00294         author knew about the types of both arguments, or convert both
00295         to the nearest built in type and do the operation there. In
00296         Fraction, that means that we define __add__ and __radd__ as:
00297 
00298             def __add__(self, other):
00299                 # Both types have numerators/denominator attributes,
00300                 # so do the operation directly
00301                 if isinstance(other, (int, Fraction)):
00302                     return Fraction(self.numerator * other.denominator +
00303                                     other.numerator * self.denominator,
00304                                     self.denominator * other.denominator)
00305                 # float and complex don't have those operations, but we
00306                 # know about those types, so special case them.
00307                 elif isinstance(other, float):
00308                     return float(self) + other
00309                 elif isinstance(other, complex):
00310                     return complex(self) + other
00311                 # Let the other type take over.
00312                 return NotImplemented
00313 
00314             def __radd__(self, other):
00315                 # radd handles more types than add because there's
00316                 # nothing left to fall back to.
00317                 if isinstance(other, numbers.Rational):
00318                     return Fraction(self.numerator * other.denominator +
00319                                     other.numerator * self.denominator,
00320                                     self.denominator * other.denominator)
00321                 elif isinstance(other, Real):
00322                     return float(other) + float(self)
00323                 elif isinstance(other, Complex):
00324                     return complex(other) + complex(self)
00325                 return NotImplemented
00326 
00327 
00328         There are 5 different cases for a mixed-type addition on
00329         Fraction. I'll refer to all of the above code that doesn't
00330         refer to Fraction, float, or complex as "boilerplate". 'r'
00331         will be an instance of Fraction, which is a subtype of
00332         Rational (r : Fraction <: Rational), and b : B <:
00333         Complex. The first three involve 'r + b':
00334 
00335             1. If B <: Fraction, int, float, or complex, we handle
00336                that specially, and all is well.
00337             2. If Fraction falls back to the boilerplate code, and it
00338                were to return a value from __add__, we'd miss the
00339                possibility that B defines a more intelligent __radd__,
00340                so the boilerplate should return NotImplemented from
00341                __add__. In particular, we don't handle Rational
00342                here, even though we could get an exact answer, in case
00343                the other type wants to do something special.
00344             3. If B <: Fraction, Python tries B.__radd__ before
00345                Fraction.__add__. This is ok, because it was
00346                implemented with knowledge of Fraction, so it can
00347                handle those instances before delegating to Real or
00348                Complex.
00349 
00350         The next two situations describe 'b + r'. We assume that b
00351         didn't know about Fraction in its implementation, and that it
00352         uses similar boilerplate code:
00353 
00354             4. If B <: Rational, then __radd_ converts both to the
00355                builtin rational type (hey look, that's us) and
00356                proceeds.
00357             5. Otherwise, __radd__ tries to find the nearest common
00358                base ABC, and fall back to its builtin type. Since this
00359                class doesn't subclass a concrete type, there's no
00360                implementation to fall back to, so we need to try as
00361                hard as possible to return an actual value, or the user
00362                will get a TypeError.
00363 
00364         """
00365         def forward(a, b):
00366             if isinstance(b, (int, Fraction)):
00367                 return monomorphic_operator(a, b)
00368             elif isinstance(b, float):
00369                 return fallback_operator(float(a), b)
00370             elif isinstance(b, complex):
00371                 return fallback_operator(complex(a), b)
00372             else:
00373                 return NotImplemented
00374         forward.__name__ = '__' + fallback_operator.__name__ + '__'
00375         forward.__doc__ = monomorphic_operator.__doc__
00376 
00377         def reverse(b, a):
00378             if isinstance(a, numbers.Rational):
00379                 # Includes ints.
00380                 return monomorphic_operator(a, b)
00381             elif isinstance(a, numbers.Real):
00382                 return fallback_operator(float(a), float(b))
00383             elif isinstance(a, numbers.Complex):
00384                 return fallback_operator(complex(a), complex(b))
00385             else:
00386                 return NotImplemented
00387         reverse.__name__ = '__r' + fallback_operator.__name__ + '__'
00388         reverse.__doc__ = monomorphic_operator.__doc__
00389 
00390         return forward, reverse
00391 
00392     def _add(a, b):
00393         """a + b"""
00394         return Fraction(a.numerator * b.denominator +
00395                         b.numerator * a.denominator,
00396                         a.denominator * b.denominator)
00397 
00398     __add__, __radd__ = _operator_fallbacks(_add, operator.add)
00399 
00400     def _sub(a, b):
00401         """a - b"""
00402         return Fraction(a.numerator * b.denominator -
00403                         b.numerator * a.denominator,
00404                         a.denominator * b.denominator)
00405 
00406     __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)
00407 
00408     def _mul(a, b):
00409         """a * b"""
00410         return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)
00411 
00412     __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)
00413 
00414     def _div(a, b):
00415         """a / b"""
00416         return Fraction(a.numerator * b.denominator,
00417                         a.denominator * b.numerator)
00418 
00419     __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)
00420 
00421     def __floordiv__(a, b):
00422         """a // b"""
00423         return math.floor(a / b)
00424 
00425     def __rfloordiv__(b, a):
00426         """a // b"""
00427         return math.floor(a / b)
00428 
00429     def __mod__(a, b):
00430         """a % b"""
00431         div = a // b
00432         return a - b * div
00433 
00434     def __rmod__(b, a):
00435         """a % b"""
00436         div = a // b
00437         return a - b * div
00438 
00439     def __pow__(a, b):
00440         """a ** b
00441 
00442         If b is not an integer, the result will be a float or complex
00443         since roots are generally irrational. If b is an integer, the
00444         result will be rational.
00445 
00446         """
00447         if isinstance(b, numbers.Rational):
00448             if b.denominator == 1:
00449                 power = b.numerator
00450                 if power >= 0:
00451                     return Fraction(a._numerator ** power,
00452                                     a._denominator ** power)
00453                 else:
00454                     return Fraction(a._denominator ** -power,
00455                                     a._numerator ** -power)
00456             else:
00457                 # A fractional power will generally produce an
00458                 # irrational number.
00459                 return float(a) ** float(b)
00460         else:
00461             return float(a) ** b
00462 
00463     def __rpow__(b, a):
00464         """a ** b"""
00465         if b._denominator == 1 and b._numerator >= 0:
00466             # If a is an int, keep it that way if possible.
00467             return a ** b._numerator
00468 
00469         if isinstance(a, numbers.Rational):
00470             return Fraction(a.numerator, a.denominator) ** b
00471 
00472         if b._denominator == 1:
00473             return a ** b._numerator
00474 
00475         return a ** float(b)
00476 
00477     def __pos__(a):
00478         """+a: Coerces a subclass instance to Fraction"""
00479         return Fraction(a._numerator, a._denominator)
00480 
00481     def __neg__(a):
00482         """-a"""
00483         return Fraction(-a._numerator, a._denominator)
00484 
00485     def __abs__(a):
00486         """abs(a)"""
00487         return Fraction(abs(a._numerator), a._denominator)
00488 
00489     def __trunc__(a):
00490         """trunc(a)"""
00491         if a._numerator < 0:
00492             return -(-a._numerator // a._denominator)
00493         else:
00494             return a._numerator // a._denominator
00495 
00496     def __floor__(a):
00497         """Will be math.floor(a) in 3.0."""
00498         return a.numerator // a.denominator
00499 
00500     def __ceil__(a):
00501         """Will be math.ceil(a) in 3.0."""
00502         # The negations cleverly convince floordiv to return the ceiling.
00503         return -(-a.numerator // a.denominator)
00504 
00505     def __round__(self, ndigits=None):
00506         """Will be round(self, ndigits) in 3.0.
00507 
00508         Rounds half toward even.
00509         """
00510         if ndigits is None:
00511             floor, remainder = divmod(self.numerator, self.denominator)
00512             if remainder * 2 < self.denominator:
00513                 return floor
00514             elif remainder * 2 > self.denominator:
00515                 return floor + 1
00516             # Deal with the half case:
00517             elif floor % 2 == 0:
00518                 return floor
00519             else:
00520                 return floor + 1
00521         shift = 10**abs(ndigits)
00522         # See _operator_fallbacks.forward to check that the results of
00523         # these operations will always be Fraction and therefore have
00524         # round().
00525         if ndigits > 0:
00526             return Fraction(round(self * shift), shift)
00527         else:
00528             return Fraction(round(self / shift) * shift)
00529 
00530     def __hash__(self):
00531         """hash(self)"""
00532 
00533         # XXX since this method is expensive, consider caching the result
00534 
00535         # In order to make sure that the hash of a Fraction agrees
00536         # with the hash of a numerically equal integer, float or
00537         # Decimal instance, we follow the rules for numeric hashes
00538         # outlined in the documentation.  (See library docs, 'Built-in
00539         # Types').
00540 
00541         # dinv is the inverse of self._denominator modulo the prime
00542         # _PyHASH_MODULUS, or 0 if self._denominator is divisible by
00543         # _PyHASH_MODULUS.
00544         dinv = pow(self._denominator, _PyHASH_MODULUS - 2, _PyHASH_MODULUS)
00545         if not dinv:
00546             hash_ = _PyHASH_INF
00547         else:
00548             hash_ = abs(self._numerator) * dinv % _PyHASH_MODULUS
00549         result = hash_ if self >= 0 else -hash_
00550         return -2 if result == -1 else result
00551 
00552     def __eq__(a, b):
00553         """a == b"""
00554         if isinstance(b, numbers.Rational):
00555             return (a._numerator == b.numerator and
00556                     a._denominator == b.denominator)
00557         if isinstance(b, numbers.Complex) and b.imag == 0:
00558             b = b.real
00559         if isinstance(b, float):
00560             if math.isnan(b) or math.isinf(b):
00561                 # comparisons with an infinity or nan should behave in
00562                 # the same way for any finite a, so treat a as zero.
00563                 return 0.0 == b
00564             else:
00565                 return a == a.from_float(b)
00566         else:
00567             # Since a doesn't know how to compare with b, let's give b
00568             # a chance to compare itself with a.
00569             return NotImplemented
00570 
00571     def _richcmp(self, other, op):
00572         """Helper for comparison operators, for internal use only.
00573 
00574         Implement comparison between a Rational instance `self`, and
00575         either another Rational instance or a float `other`.  If
00576         `other` is not a Rational instance or a float, return
00577         NotImplemented. `op` should be one of the six standard
00578         comparison operators.
00579 
00580         """
00581         # convert other to a Rational instance where reasonable.
00582         if isinstance(other, numbers.Rational):
00583             return op(self._numerator * other.denominator,
00584                       self._denominator * other.numerator)
00585         if isinstance(other, float):
00586             if math.isnan(other) or math.isinf(other):
00587                 return op(0.0, other)
00588             else:
00589                 return op(self, self.from_float(other))
00590         else:
00591             return NotImplemented
00592 
00593     def __lt__(a, b):
00594         """a < b"""
00595         return a._richcmp(b, operator.lt)
00596 
00597     def __gt__(a, b):
00598         """a > b"""
00599         return a._richcmp(b, operator.gt)
00600 
00601     def __le__(a, b):
00602         """a <= b"""
00603         return a._richcmp(b, operator.le)
00604 
00605     def __ge__(a, b):
00606         """a >= b"""
00607         return a._richcmp(b, operator.ge)
00608 
00609     def __bool__(a):
00610         """a != 0"""
00611         return a._numerator != 0
00612 
00613     # support for pickling, copy, and deepcopy
00614 
00615     def __reduce__(self):
00616         return (self.__class__, (str(self),))
00617 
00618     def __copy__(self):
00619         if type(self) == Fraction:
00620             return self     # I'm immutable; therefore I am my own clone
00621         return self.__class__(self._numerator, self._denominator)
00622 
00623     def __deepcopy__(self, memo):
00624         if type(self) == Fraction:
00625             return self     # My components are also immutable
00626         return self.__class__(self._numerator, self._denominator)