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