Lib/rational.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
  11 __all__ = ["Rational"]
  12
  13 RationalAbc = numbers.Rational
  14
  15
  16 def _gcd(a, b):
  17     """Calculate the Greatest Common Divisor.
  18
  19     Unless b==0, the result will have the same sign as b (so that when
  20     b is divided by it, the result comes out positive).
  21     """
  22     while b:
  23         a, b = b, a%b
  24     return a
  25
  26
  27 def _binary_float_to_ratio(x):
  28     """x -> (top, bot), a pair of ints s.t. x = top/bot.
  29
  30     The conversion is done exactly, without rounding.
  31     bot > 0 guaranteed.
  32     Some form of binary fp is assumed.
  33     Pass NaNs or infinities at your own risk.
  34
  35     >>> _binary_float_to_ratio(10.0)
  36     (10, 1)
  37     >>> _binary_float_to_ratio(0.0)
  38     (0, 1)
  39     >>> _binary_float_to_ratio(-.25)
  40     (-1, 4)
  41     """
  42
  43     if x == 0:
  44         return 0, 1
  45     f, e = math.frexp(x)
  46     signbit = 1
  47     if f < 0:
  48         f = -f
  49         signbit = -1
  50     assert 0.5 <= f < 1.0
  51     # x = signbit * f * 2**e exactly
  52
  53     # Suck up CHUNK bits at a time; 28 is enough so that we suck
  54     # up all bits in 2 iterations for all known binary double-
  55     # precision formats, and small enough to fit in an int.
  56     CHUNK = 28
  57     top = 0
  58     # invariant: x = signbit * (top + f) * 2**e exactly
  59     while f:
  60         f = math.ldexp(f, CHUNK)
  61         digit = trunc(f)
  62         assert digit >> CHUNK == 0
  63         top = (top << CHUNK) | digit
  64         f = f - digit
  65         assert 0.0 <= f < 1.0
  66         e = e - CHUNK
  67     assert top
  68
  69     # Add in the sign bit.
  70     top = signbit * top
  71
  72     # now x = top * 2**e exactly; fold in 2**e
  73     if e>0:
  74         return (top * 2**e, 1)
  75     else:
  76         return (top, 2 ** -e)
  77
  78
  79 class Rational(RationalAbc):
  80     """This class implements rational numbers.
  81
  82     Rational(8, 6) will produce a rational number equivalent to
  83     4/3. Both arguments must be Integral. The numerator defaults to 0
  84     and the denominator defaults to 1 so that Rational(3) == 3 and
  85     Rational() == 0.
  86
  87     """
  88
  89     __slots__ = ('_numerator', '_denominator')
  90
  91     def __init__(self, numerator=0, denominator=1):
  92         if (not isinstance(numerator, numbers.Integral) and
  93             isinstance(numerator, RationalAbc) and
  94             denominator == 1):
  95             # Handle copies from other rationals.
  96             other_rational = numerator
  97             numerator = other_rational.numerator
  98             denominator = other_rational.denominator
  99
 100         if (not isinstance(numerator, numbers.Integral) or
 101             not isinstance(denominator, numbers.Integral)):
 102             raise TypeError("Rational(%(numerator)s, %(denominator)s):"
 103                             " Both arguments must be integral." % locals())
 104
 105         if denominator == 0:
 106             raise ZeroDivisionError('Rational(%s, 0)' % numerator)
 107
 108         g = _gcd(numerator, denominator)
 109         self._numerator = int(numerator // g)
 110         self._denominator = int(denominator // g)
 111
 112     @classmethod
 113     def from_float(cls, f):
 114         """Converts a float to a rational number, exactly."""
 115         if 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(*_binary_float_to_ratio(f))
 121
 122     @property
 123     def numerator(a):
 124         return a._numerator
 125
 126     @property
 127     def denominator(a):
 128         return a._denominator
 129
 130     def __repr__(self):
 131         """repr(self)"""
 132         return ('rational.Rational(%r,%r)' %
 133                 (self.numerator, self.denominator))
 134
 135     def __str__(self):
 136         """str(self)"""
 137         if self.denominator == 1:
 138             return str(self.numerator)
 139         else:
 140             return '(%s/%s)' % (self.numerator, self.denominator)
 141
 142     def _operator_fallbacks(monomorphic_operator, fallback_operator):
 143         """Generates forward and reverse operators given a purely-rational
 144         operator and a function from the operator module.
 145
 146         Use this like:
 147         __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op)
 148
 149         """
 150         def forward(a, b):
 151             if isinstance(b, RationalAbc):
 152                 # Includes ints.
 153                 return monomorphic_operator(a, b)
 154             elif isinstance(b, float):
 155                 return fallback_operator(float(a), b)
 156             elif isinstance(b, complex):
 157                 return fallback_operator(complex(a), b)
 158             else:
 159                 return NotImplemented
 160         forward.__name__ = '__' + fallback_operator.__name__ + '__'
 161         forward.__doc__ = monomorphic_operator.__doc__
 162
 163         def reverse(b, a):
 164             if isinstance(a, RationalAbc):
 165                 # Includes ints.
 166                 return monomorphic_operator(a, b)
 167             elif isinstance(a, numbers.Real):
 168                 return fallback_operator(float(a), float(b))
 169             elif isinstance(a, numbers.Complex):
 170                 return fallback_operator(complex(a), complex(b))
 171             else:
 172                 return NotImplemented
 173         reverse.__name__ = '__r' + fallback_operator.__name__ + '__'
 174         reverse.__doc__ = monomorphic_operator.__doc__
 175
 176         return forward, reverse
 177
 178     def _add(a, b):
 179         """a + b"""
 180         return Rational(a.numerator * b.denominator +
 181                         b.numerator * a.denominator,
 182                         a.denominator * b.denominator)
 183
 184     __add__, __radd__ = _operator_fallbacks(_add, operator.add)
 185
 186     def _sub(a, b):
 187         """a - b"""
 188         return Rational(a.numerator * b.denominator -
 189                         b.numerator * a.denominator,
 190                         a.denominator * b.denominator)
 191
 192     __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)
 193
 194     def _mul(a, b):
 195         """a * b"""
 196         return Rational(a.numerator * b.numerator, a.denominator * b.denominator)
 197
 198     __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)
 199
 200     def _div(a, b):
 201         """a / b"""
 202         return Rational(a.numerator * b.denominator,
 203                         a.denominator * b.numerator)
 204
 205     __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)
 206     __div__, __rdiv__ = _operator_fallbacks(_div, operator.div)
 207
 208     @classmethod
 209     def _floordiv(cls, a, b):
 210         div = a / b
 211         if isinstance(div, RationalAbc):
 212             # trunc(math.floor(div)) doesn't work if the rational is
 213             # more precise than a float because the intermediate
 214             # rounding may cross an integer boundary.
 215             return div.numerator // div.denominator
 216         else:
 217             return math.floor(div)
 218
 219     def __floordiv__(a, b):
 220         """a // b"""
 221         # Will be math.floor(a / b) in 3.0.
 222         return a._floordiv(a, b)
 223
 224     def __rfloordiv__(b, a):
 225         """a // b"""
 226         # Will be math.floor(a / b) in 3.0.
 227         return b._floordiv(a, b)
 228
 229     @classmethod
 230     def _mod(cls, a, b):
 231         div = a // b
 232         return a - b * div
 233
 234     def __mod__(a, b):
 235         """a % b"""
 236         return a._mod(a, b)
 237
 238     def __rmod__(b, a):
 239         """a % b"""
 240         return b._mod(a, b)
 241
 242     def __pow__(a, b):
 243         """a ** b
 244
 245         If b is not an integer, the result will be a float or complex
 246         since roots are generally irrational. If b is an integer, the
 247         result will be rational.
 248
 249         """
 250         if isinstance(b, RationalAbc):
 251             if b.denominator == 1:
 252                 power = b.numerator
 253                 if power >= 0:
 254                     return Rational(a.numerator ** power,
 255                                     a.denominator ** power)
 256                 else:
 257                     return Rational(a.denominator ** -power,
 258                                     a.numerator ** -power)
 259             else:
 260                 # A fractional power will generally produce an
 261                 # irrational number.
 262                 return float(a) ** float(b)
 263         else:
 264             return float(a) ** b
 265
 266     def __rpow__(b, a):
 267         """a ** b"""
 268         if b.denominator == 1 and b.numerator >= 0:
 269             # If a is an int, keep it that way if possible.
 270             return a ** b.numerator
 271
 272         if isinstance(a, RationalAbc):
 273             return Rational(a.numerator, a.denominator) ** b
 274
 275         if b.denominator == 1:
 276             return a ** b.numerator
 277
 278         return a ** float(b)
 279
 280     def __pos__(a):
 281         """+a: Coerces a subclass instance to Rational"""
 282         return Rational(a.numerator, a.denominator)
 283
 284     def __neg__(a):
 285         """-a"""
 286         return Rational(-a.numerator, a.denominator)
 287
 288     def __abs__(a):
 289         """abs(a)"""
 290         return Rational(abs(a.numerator), a.denominator)
 291
 292     def __trunc__(a):
 293         """trunc(a)"""
 294         if a.numerator < 0:
 295             return -(-a.numerator // a.denominator)
 296         else:
 297             return a.numerator // a.denominator
 298
 299     def __floor__(a):
 300         """Will be math.floor(a) in 3.0."""
 301         return a.numerator // a.denominator
 302
 303     def __ceil__(a):
 304         """Will be math.ceil(a) in 3.0."""
 305         # The negations cleverly convince floordiv to return the ceiling.
 306         return -(-a.numerator // a.denominator)
 307
 308     def __round__(self, ndigits=None):
 309         """Will be round(self, ndigits) in 3.0.
 310
 311         Rounds half toward even.
 312         """
 313         if ndigits is None:
 314             floor, remainder = divmod(self.numerator, self.denominator)
 315             if remainder * 2 < self.denominator:
 316                 return floor
 317             elif remainder * 2 > self.denominator:
 318                 return floor + 1
 319             # Deal with the half case:
 320             elif floor % 2 == 0:
 321                 return floor
 322             else:
 323                 return floor + 1
 324         shift = 10**abs(ndigits)
 325         # See _operator_fallbacks.forward to check that the results of
 326         # these operations will always be Rational and therefore have
 327         # __round__().
 328         if ndigits > 0:
 329             return Rational((self * shift).__round__(), shift)
 330         else:
 331             return Rational((self / shift).__round__() * shift)
 332
 333     def __hash__(self):
 334         """hash(self)
 335
 336         Tricky because values that are exactly representable as a
 337         float must have the same hash as that float.
 338
 339         """
 340         if self.denominator == 1:
 341             # Get integers right.
 342             return hash(self.numerator)
 343         # Expensive check, but definitely correct.
 344         if self == float(self):
 345             return hash(float(self))
 346         else:
 347             # Use tuple's hash to avoid a high collision rate on
 348             # simple fractions.
 349             return hash((self.numerator, self.denominator))
 350
 351     def __eq__(a, b):
 352         """a == b"""
 353         if isinstance(b, RationalAbc):
 354             return (a.numerator == b.numerator and
 355                     a.denominator == b.denominator)
 356         if isinstance(b, numbers.Complex) and b.imag == 0:
 357             b = b.real
 358         if isinstance(b, float):
 359             return a == a.from_float(b)
 360         else:
 361             # XXX: If b.__eq__ is implemented like this method, it may
 362             # give the wrong answer after float(a) changes a's
 363             # value. Better ways of doing this are welcome.
 364             return float(a) == b
 365
 366     def _subtractAndCompareToZero(a, b, op):
 367         """Helper function for comparison operators.
 368
 369         Subtracts b from a, exactly if possible, and compares the
 370         result with 0 using op, in such a way that the comparison
 371         won't recurse. If the difference raises a TypeError, returns
 372         NotImplemented instead.
 373
 374         """
 375         if isinstance(b, numbers.Complex) and b.imag == 0:
 376             b = b.real
 377         if isinstance(b, float):
 378             b = a.from_float(b)
 379         try:
 380             # XXX: If b <: Real but not <: RationalAbc, this is likely
 381             # to fall back to a float. If the actual values differ by
 382             # less than MIN_FLOAT, this could falsely call them equal,
 383             # which would make <= inconsistent with ==. Better ways of
 384             # doing this are welcome.
 385             diff = a - b
 386         except TypeError:
 387             return NotImplemented
 388         if isinstance(diff, RationalAbc):
 389             return op(diff.numerator, 0)
 390         return op(diff, 0)
 391
 392     def __lt__(a, b):
 393         """a < b"""
 394         return a._subtractAndCompareToZero(b, operator.lt)
 395
 396     def __gt__(a, b):
 397         """a > b"""
 398         return a._subtractAndCompareToZero(b, operator.gt)
 399
 400     def __le__(a, b):
 401         """a <= b"""
 402         return a._subtractAndCompareToZero(b, operator.le)
 403
 404     def __ge__(a, b):
 405         """a >= b"""
 406         return a._subtractAndCompareToZero(b, operator.ge)
 407
 408     def __nonzero__(a):
 409         """a != 0"""
 410         return a.numerator != 0