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