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)