1# Originally contributed by Sjoerd Mullender. 2# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>. 3 4"""Fraction, infinite-precision, real numbers.""" 5 6from decimal import Decimal 7import math 8import numbers 9import operator 10import re 11import sys 12 13__all__ = ['Fraction', 'gcd'] 14 15 16 17def 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 32def _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 60class 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 as_integer_ratio(self): 220 """Return the integer ratio as a tuple. 221 222 Return a tuple of two integers, whose ratio is equal to the 223 Fraction and with a positive denominator. 224 """ 225 return (self._numerator, self._denominator) 226 227 def limit_denominator(self, max_denominator=1000000): 228 """Closest Fraction to self with denominator at most max_denominator. 229 230 >>> Fraction('3.141592653589793').limit_denominator(10) 231 Fraction(22, 7) 232 >>> Fraction('3.141592653589793').limit_denominator(100) 233 Fraction(311, 99) 234 >>> Fraction(4321, 8765).limit_denominator(10000) 235 Fraction(4321, 8765) 236 237 """ 238 # Algorithm notes: For any real number x, define a *best upper 239 # approximation* to x to be a rational number p/q such that: 240 # 241 # (1) p/q >= x, and 242 # (2) if p/q > r/s >= x then s > q, for any rational r/s. 243 # 244 # Define *best lower approximation* similarly. Then it can be 245 # proved that a rational number is a best upper or lower 246 # approximation to x if, and only if, it is a convergent or 247 # semiconvergent of the (unique shortest) continued fraction 248 # associated to x. 249 # 250 # To find a best rational approximation with denominator <= M, 251 # we find the best upper and lower approximations with 252 # denominator <= M and take whichever of these is closer to x. 253 # In the event of a tie, the bound with smaller denominator is 254 # chosen. If both denominators are equal (which can happen 255 # only when max_denominator == 1 and self is midway between 256 # two integers) the lower bound---i.e., the floor of self, is 257 # taken. 258 259 if max_denominator < 1: 260 raise ValueError("max_denominator should be at least 1") 261 if self._denominator <= max_denominator: 262 return Fraction(self) 263 264 p0, q0, p1, q1 = 0, 1, 1, 0 265 n, d = self._numerator, self._denominator 266 while True: 267 a = n//d 268 q2 = q0+a*q1 269 if q2 > max_denominator: 270 break 271 p0, q0, p1, q1 = p1, q1, p0+a*p1, q2 272 n, d = d, n-a*d 273 274 k = (max_denominator-q0)//q1 275 bound1 = Fraction(p0+k*p1, q0+k*q1) 276 bound2 = Fraction(p1, q1) 277 if abs(bound2 - self) <= abs(bound1-self): 278 return bound2 279 else: 280 return bound1 281 282 @property 283 def numerator(a): 284 return a._numerator 285 286 @property 287 def denominator(a): 288 return a._denominator 289 290 def __repr__(self): 291 """repr(self)""" 292 return '%s(%s, %s)' % (self.__class__.__name__, 293 self._numerator, self._denominator) 294 295 def __str__(self): 296 """str(self)""" 297 if self._denominator == 1: 298 return str(self._numerator) 299 else: 300 return '%s/%s' % (self._numerator, self._denominator) 301 302 def _operator_fallbacks(monomorphic_operator, fallback_operator): 303 """Generates forward and reverse operators given a purely-rational 304 operator and a function from the operator module. 305 306 Use this like: 307 __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op) 308 309 In general, we want to implement the arithmetic operations so 310 that mixed-mode operations either call an implementation whose 311 author knew about the types of both arguments, or convert both 312 to the nearest built in type and do the operation there. In 313 Fraction, that means that we define __add__ and __radd__ as: 314 315 def __add__(self, other): 316 # Both types have numerators/denominator attributes, 317 # so do the operation directly 318 if isinstance(other, (int, Fraction)): 319 return Fraction(self.numerator * other.denominator + 320 other.numerator * self.denominator, 321 self.denominator * other.denominator) 322 # float and complex don't have those operations, but we 323 # know about those types, so special case them. 324 elif isinstance(other, float): 325 return float(self) + other 326 elif isinstance(other, complex): 327 return complex(self) + other 328 # Let the other type take over. 329 return NotImplemented 330 331 def __radd__(self, other): 332 # radd handles more types than add because there's 333 # nothing left to fall back to. 334 if isinstance(other, numbers.Rational): 335 return Fraction(self.numerator * other.denominator + 336 other.numerator * self.denominator, 337 self.denominator * other.denominator) 338 elif isinstance(other, Real): 339 return float(other) + float(self) 340 elif isinstance(other, Complex): 341 return complex(other) + complex(self) 342 return NotImplemented 343 344 345 There are 5 different cases for a mixed-type addition on 346 Fraction. I'll refer to all of the above code that doesn't 347 refer to Fraction, float, or complex as "boilerplate". 'r' 348 will be an instance of Fraction, which is a subtype of 349 Rational (r : Fraction <: Rational), and b : B <: 350 Complex. The first three involve 'r + b': 351 352 1. If B <: Fraction, int, float, or complex, we handle 353 that specially, and all is well. 354 2. If Fraction falls back to the boilerplate code, and it 355 were to return a value from __add__, we'd miss the 356 possibility that B defines a more intelligent __radd__, 357 so the boilerplate should return NotImplemented from 358 __add__. In particular, we don't handle Rational 359 here, even though we could get an exact answer, in case 360 the other type wants to do something special. 361 3. If B <: Fraction, Python tries B.__radd__ before 362 Fraction.__add__. This is ok, because it was 363 implemented with knowledge of Fraction, so it can 364 handle those instances before delegating to Real or 365 Complex. 366 367 The next two situations describe 'b + r'. We assume that b 368 didn't know about Fraction in its implementation, and that it 369 uses similar boilerplate code: 370 371 4. If B <: Rational, then __radd_ converts both to the 372 builtin rational type (hey look, that's us) and 373 proceeds. 374 5. Otherwise, __radd__ tries to find the nearest common 375 base ABC, and fall back to its builtin type. Since this 376 class doesn't subclass a concrete type, there's no 377 implementation to fall back to, so we need to try as 378 hard as possible to return an actual value, or the user 379 will get a TypeError. 380 381 """ 382 def forward(a, b): 383 if isinstance(b, (int, Fraction)): 384 return monomorphic_operator(a, b) 385 elif isinstance(b, float): 386 return fallback_operator(float(a), b) 387 elif isinstance(b, complex): 388 return fallback_operator(complex(a), b) 389 else: 390 return NotImplemented 391 forward.__name__ = '__' + fallback_operator.__name__ + '__' 392 forward.__doc__ = monomorphic_operator.__doc__ 393 394 def reverse(b, a): 395 if isinstance(a, numbers.Rational): 396 # Includes ints. 397 return monomorphic_operator(a, b) 398 elif isinstance(a, numbers.Real): 399 return fallback_operator(float(a), float(b)) 400 elif isinstance(a, numbers.Complex): 401 return fallback_operator(complex(a), complex(b)) 402 else: 403 return NotImplemented 404 reverse.__name__ = '__r' + fallback_operator.__name__ + '__' 405 reverse.__doc__ = monomorphic_operator.__doc__ 406 407 return forward, reverse 408 409 def _add(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 __add__, __radd__ = _operator_fallbacks(_add, operator.add) 416 417 def _sub(a, b): 418 """a - b""" 419 da, db = a.denominator, b.denominator 420 return Fraction(a.numerator * db - b.numerator * da, 421 da * db) 422 423 __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub) 424 425 def _mul(a, b): 426 """a * b""" 427 return Fraction(a.numerator * b.numerator, a.denominator * b.denominator) 428 429 __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul) 430 431 def _div(a, b): 432 """a / b""" 433 return Fraction(a.numerator * b.denominator, 434 a.denominator * b.numerator) 435 436 __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv) 437 438 def _floordiv(a, b): 439 """a // b""" 440 return (a.numerator * b.denominator) // (a.denominator * b.numerator) 441 442 __floordiv__, __rfloordiv__ = _operator_fallbacks(_floordiv, operator.floordiv) 443 444 def _divmod(a, b): 445 """(a // b, a % b)""" 446 da, db = a.denominator, b.denominator 447 div, n_mod = divmod(a.numerator * db, da * b.numerator) 448 return div, Fraction(n_mod, da * db) 449 450 __divmod__, __rdivmod__ = _operator_fallbacks(_divmod, divmod) 451 452 def _mod(a, b): 453 """a % b""" 454 da, db = a.denominator, b.denominator 455 return Fraction((a.numerator * db) % (b.numerator * da), da * db) 456 457 __mod__, __rmod__ = _operator_fallbacks(_mod, operator.mod) 458 459 def __pow__(a, b): 460 """a ** b 461 462 If b is not an integer, the result will be a float or complex 463 since roots are generally irrational. If b is an integer, the 464 result will be rational. 465 466 """ 467 if isinstance(b, numbers.Rational): 468 if b.denominator == 1: 469 power = b.numerator 470 if power >= 0: 471 return Fraction(a._numerator ** power, 472 a._denominator ** power, 473 _normalize=False) 474 elif a._numerator >= 0: 475 return Fraction(a._denominator ** -power, 476 a._numerator ** -power, 477 _normalize=False) 478 else: 479 return Fraction((-a._denominator) ** -power, 480 (-a._numerator) ** -power, 481 _normalize=False) 482 else: 483 # A fractional power will generally produce an 484 # irrational number. 485 return float(a) ** float(b) 486 else: 487 return float(a) ** b 488 489 def __rpow__(b, a): 490 """a ** b""" 491 if b._denominator == 1 and b._numerator >= 0: 492 # If a is an int, keep it that way if possible. 493 return a ** b._numerator 494 495 if isinstance(a, numbers.Rational): 496 return Fraction(a.numerator, a.denominator) ** b 497 498 if b._denominator == 1: 499 return a ** b._numerator 500 501 return a ** float(b) 502 503 def __pos__(a): 504 """+a: Coerces a subclass instance to Fraction""" 505 return Fraction(a._numerator, a._denominator, _normalize=False) 506 507 def __neg__(a): 508 """-a""" 509 return Fraction(-a._numerator, a._denominator, _normalize=False) 510 511 def __abs__(a): 512 """abs(a)""" 513 return Fraction(abs(a._numerator), a._denominator, _normalize=False) 514 515 def __trunc__(a): 516 """trunc(a)""" 517 if a._numerator < 0: 518 return -(-a._numerator // a._denominator) 519 else: 520 return a._numerator // a._denominator 521 522 def __floor__(a): 523 """math.floor(a)""" 524 return a.numerator // a.denominator 525 526 def __ceil__(a): 527 """math.ceil(a)""" 528 # The negations cleverly convince floordiv to return the ceiling. 529 return -(-a.numerator // a.denominator) 530 531 def __round__(self, ndigits=None): 532 """round(self, ndigits) 533 534 Rounds half toward even. 535 """ 536 if ndigits is None: 537 floor, remainder = divmod(self.numerator, self.denominator) 538 if remainder * 2 < self.denominator: 539 return floor 540 elif remainder * 2 > self.denominator: 541 return floor + 1 542 # Deal with the half case: 543 elif floor % 2 == 0: 544 return floor 545 else: 546 return floor + 1 547 shift = 10**abs(ndigits) 548 # See _operator_fallbacks.forward to check that the results of 549 # these operations will always be Fraction and therefore have 550 # round(). 551 if ndigits > 0: 552 return Fraction(round(self * shift), shift) 553 else: 554 return Fraction(round(self / shift) * shift) 555 556 def __hash__(self): 557 """hash(self)""" 558 559 # XXX since this method is expensive, consider caching the result 560 561 # In order to make sure that the hash of a Fraction agrees 562 # with the hash of a numerically equal integer, float or 563 # Decimal instance, we follow the rules for numeric hashes 564 # outlined in the documentation. (See library docs, 'Built-in 565 # Types'). 566 567 # dinv is the inverse of self._denominator modulo the prime 568 # _PyHASH_MODULUS, or 0 if self._denominator is divisible by 569 # _PyHASH_MODULUS. 570 dinv = pow(self._denominator, _PyHASH_MODULUS - 2, _PyHASH_MODULUS) 571 if not dinv: 572 hash_ = _PyHASH_INF 573 else: 574 hash_ = abs(self._numerator) * dinv % _PyHASH_MODULUS 575 result = hash_ if self >= 0 else -hash_ 576 return -2 if result == -1 else result 577 578 def __eq__(a, b): 579 """a == b""" 580 if type(b) is int: 581 return a._numerator == b and a._denominator == 1 582 if isinstance(b, numbers.Rational): 583 return (a._numerator == b.numerator and 584 a._denominator == b.denominator) 585 if isinstance(b, numbers.Complex) and b.imag == 0: 586 b = b.real 587 if isinstance(b, float): 588 if math.isnan(b) or math.isinf(b): 589 # comparisons with an infinity or nan should behave in 590 # the same way for any finite a, so treat a as zero. 591 return 0.0 == b 592 else: 593 return a == a.from_float(b) 594 else: 595 # Since a doesn't know how to compare with b, let's give b 596 # a chance to compare itself with a. 597 return NotImplemented 598 599 def _richcmp(self, other, op): 600 """Helper for comparison operators, for internal use only. 601 602 Implement comparison between a Rational instance `self`, and 603 either another Rational instance or a float `other`. If 604 `other` is not a Rational instance or a float, return 605 NotImplemented. `op` should be one of the six standard 606 comparison operators. 607 608 """ 609 # convert other to a Rational instance where reasonable. 610 if isinstance(other, numbers.Rational): 611 return op(self._numerator * other.denominator, 612 self._denominator * other.numerator) 613 if isinstance(other, float): 614 if math.isnan(other) or math.isinf(other): 615 return op(0.0, other) 616 else: 617 return op(self, self.from_float(other)) 618 else: 619 return NotImplemented 620 621 def __lt__(a, b): 622 """a < b""" 623 return a._richcmp(b, operator.lt) 624 625 def __gt__(a, b): 626 """a > b""" 627 return a._richcmp(b, operator.gt) 628 629 def __le__(a, b): 630 """a <= b""" 631 return a._richcmp(b, operator.le) 632 633 def __ge__(a, b): 634 """a >= b""" 635 return a._richcmp(b, operator.ge) 636 637 def __bool__(a): 638 """a != 0""" 639 # bpo-39274: Use bool() because (a._numerator != 0) can return an 640 # object which is not a bool. 641 return bool(a._numerator) 642 643 # support for pickling, copy, and deepcopy 644 645 def __reduce__(self): 646 return (self.__class__, (str(self),)) 647 648 def __copy__(self): 649 if type(self) == Fraction: 650 return self # I'm immutable; therefore I am my own clone 651 return self.__class__(self._numerator, self._denominator) 652 653 def __deepcopy__(self, memo): 654 if type(self) == Fraction: 655 return self # My components are also immutable 656 return self.__class__(self._numerator, self._denominator) 657