1# Originally contributed by Sjoerd Mullender. 2# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>. 3 4"""Fraction, infinite-precision, rational numbers.""" 5 6from decimal import Decimal 7import functools 8import math 9import numbers 10import operator 11import re 12import sys 13 14__all__ = ['Fraction'] 15 16 17# Constants related to the hash implementation; hash(x) is based 18# on the reduction of x modulo the prime _PyHASH_MODULUS. 19_PyHASH_MODULUS = sys.hash_info.modulus 20# Value to be used for rationals that reduce to infinity modulo 21# _PyHASH_MODULUS. 22_PyHASH_INF = sys.hash_info.inf 23 24@functools.lru_cache(maxsize = 1 << 14) 25def _hash_algorithm(numerator, denominator): 26 27 # To make sure that the hash of a Fraction agrees with the hash 28 # of a numerically equal integer, float or Decimal instance, we 29 # follow the rules for numeric hashes outlined in the 30 # documentation. (See library docs, 'Built-in Types'). 31 32 try: 33 dinv = pow(denominator, -1, _PyHASH_MODULUS) 34 except ValueError: 35 # ValueError means there is no modular inverse. 36 hash_ = _PyHASH_INF 37 else: 38 # The general algorithm now specifies that the absolute value of 39 # the hash is 40 # (|N| * dinv) % P 41 # where N is self._numerator and P is _PyHASH_MODULUS. That's 42 # optimized here in two ways: first, for a non-negative int i, 43 # hash(i) == i % P, but the int hash implementation doesn't need 44 # to divide, and is faster than doing % P explicitly. So we do 45 # hash(|N| * dinv) 46 # instead. Second, N is unbounded, so its product with dinv may 47 # be arbitrarily expensive to compute. The final answer is the 48 # same if we use the bounded |N| % P instead, which can again 49 # be done with an int hash() call. If 0 <= i < P, hash(i) == i, 50 # so this nested hash() call wastes a bit of time making a 51 # redundant copy when |N| < P, but can save an arbitrarily large 52 # amount of computation for large |N|. 53 hash_ = hash(hash(abs(numerator)) * dinv) 54 result = hash_ if numerator >= 0 else -hash_ 55 return -2 if result == -1 else result 56 57_RATIONAL_FORMAT = re.compile(r""" 58 \A\s* # optional whitespace at the start, 59 (?P<sign>[-+]?) # an optional sign, then 60 (?=\d|\.\d) # lookahead for digit or .digit 61 (?P<num>\d*|\d+(_\d+)*) # numerator (possibly empty) 62 (?: # followed by 63 (?:\s*/\s*(?P<denom>\d+(_\d+)*))? # an optional denominator 64 | # or 65 (?:\.(?P<decimal>\d*|\d+(_\d+)*))? # an optional fractional part 66 (?:E(?P<exp>[-+]?\d+(_\d+)*))? # and optional exponent 67 ) 68 \s*\Z # and optional whitespace to finish 69""", re.VERBOSE | re.IGNORECASE) 70 71 72# Helpers for formatting 73 74def _round_to_exponent(n, d, exponent, no_neg_zero=False): 75 """Round a rational number to the nearest multiple of a given power of 10. 76 77 Rounds the rational number n/d to the nearest integer multiple of 78 10**exponent, rounding to the nearest even integer multiple in the case of 79 a tie. Returns a pair (sign: bool, significand: int) representing the 80 rounded value (-1)**sign * significand * 10**exponent. 81 82 If no_neg_zero is true, then the returned sign will always be False when 83 the significand is zero. Otherwise, the sign reflects the sign of the 84 input. 85 86 d must be positive, but n and d need not be relatively prime. 87 """ 88 if exponent >= 0: 89 d *= 10**exponent 90 else: 91 n *= 10**-exponent 92 93 # The divmod quotient is correct for round-ties-towards-positive-infinity; 94 # In the case of a tie, we zero out the least significant bit of q. 95 q, r = divmod(n + (d >> 1), d) 96 if r == 0 and d & 1 == 0: 97 q &= -2 98 99 sign = q < 0 if no_neg_zero else n < 0 100 return sign, abs(q) 101 102 103def _round_to_figures(n, d, figures): 104 """Round a rational number to a given number of significant figures. 105 106 Rounds the rational number n/d to the given number of significant figures 107 using the round-ties-to-even rule, and returns a triple 108 (sign: bool, significand: int, exponent: int) representing the rounded 109 value (-1)**sign * significand * 10**exponent. 110 111 In the special case where n = 0, returns a significand of zero and 112 an exponent of 1 - figures, for compatibility with formatting. 113 Otherwise, the returned significand satisfies 114 10**(figures - 1) <= significand < 10**figures. 115 116 d must be positive, but n and d need not be relatively prime. 117 figures must be positive. 118 """ 119 # Special case for n == 0. 120 if n == 0: 121 return False, 0, 1 - figures 122 123 # Find integer m satisfying 10**(m - 1) <= abs(n)/d <= 10**m. (If abs(n)/d 124 # is a power of 10, either of the two possible values for m is fine.) 125 str_n, str_d = str(abs(n)), str(d) 126 m = len(str_n) - len(str_d) + (str_d <= str_n) 127 128 # Round to a multiple of 10**(m - figures). The significand we get 129 # satisfies 10**(figures - 1) <= significand <= 10**figures. 130 exponent = m - figures 131 sign, significand = _round_to_exponent(n, d, exponent) 132 133 # Adjust in the case where significand == 10**figures, to ensure that 134 # 10**(figures - 1) <= significand < 10**figures. 135 if len(str(significand)) == figures + 1: 136 significand //= 10 137 exponent += 1 138 139 return sign, significand, exponent 140 141 142# Pattern for matching non-float-style format specifications. 143_GENERAL_FORMAT_SPECIFICATION_MATCHER = re.compile(r""" 144 (?: 145 (?P<fill>.)? 146 (?P<align>[<>=^]) 147 )? 148 (?P<sign>[-+ ]?) 149 # Alt flag forces a slash and denominator in the output, even for 150 # integer-valued Fraction objects. 151 (?P<alt>\#)? 152 # We don't implement the zeropad flag since there's no single obvious way 153 # to interpret it. 154 (?P<minimumwidth>0|[1-9][0-9]*)? 155 (?P<thousands_sep>[,_])? 156""", re.DOTALL | re.VERBOSE).fullmatch 157 158 159# Pattern for matching float-style format specifications; 160# supports 'e', 'E', 'f', 'F', 'g', 'G' and '%' presentation types. 161_FLOAT_FORMAT_SPECIFICATION_MATCHER = re.compile(r""" 162 (?: 163 (?P<fill>.)? 164 (?P<align>[<>=^]) 165 )? 166 (?P<sign>[-+ ]?) 167 (?P<no_neg_zero>z)? 168 (?P<alt>\#)? 169 # A '0' that's *not* followed by another digit is parsed as a minimum width 170 # rather than a zeropad flag. 171 (?P<zeropad>0(?=[0-9]))? 172 (?P<minimumwidth>0|[1-9][0-9]*)? 173 (?P<thousands_sep>[,_])? 174 (?:\.(?P<precision>0|[1-9][0-9]*))? 175 (?P<presentation_type>[eEfFgG%]) 176""", re.DOTALL | re.VERBOSE).fullmatch 177 178 179class Fraction(numbers.Rational): 180 """This class implements rational numbers. 181 182 In the two-argument form of the constructor, Fraction(8, 6) will 183 produce a rational number equivalent to 4/3. Both arguments must 184 be Rational. The numerator defaults to 0 and the denominator 185 defaults to 1 so that Fraction(3) == 3 and Fraction() == 0. 186 187 Fractions can also be constructed from: 188 189 - numeric strings similar to those accepted by the 190 float constructor (for example, '-2.3' or '1e10') 191 192 - strings of the form '123/456' 193 194 - float and Decimal instances 195 196 - other Rational instances (including integers) 197 198 """ 199 200 __slots__ = ('_numerator', '_denominator') 201 202 # We're immutable, so use __new__ not __init__ 203 def __new__(cls, numerator=0, denominator=None): 204 """Constructs a Rational. 205 206 Takes a string like '3/2' or '1.5', another Rational instance, a 207 numerator/denominator pair, or a float. 208 209 Examples 210 -------- 211 212 >>> Fraction(10, -8) 213 Fraction(-5, 4) 214 >>> Fraction(Fraction(1, 7), 5) 215 Fraction(1, 35) 216 >>> Fraction(Fraction(1, 7), Fraction(2, 3)) 217 Fraction(3, 14) 218 >>> Fraction('314') 219 Fraction(314, 1) 220 >>> Fraction('-35/4') 221 Fraction(-35, 4) 222 >>> Fraction('3.1415') # conversion from numeric string 223 Fraction(6283, 2000) 224 >>> Fraction('-47e-2') # string may include a decimal exponent 225 Fraction(-47, 100) 226 >>> Fraction(1.47) # direct construction from float (exact conversion) 227 Fraction(6620291452234629, 4503599627370496) 228 >>> Fraction(2.25) 229 Fraction(9, 4) 230 >>> Fraction(Decimal('1.47')) 231 Fraction(147, 100) 232 233 """ 234 self = super(Fraction, cls).__new__(cls) 235 236 if denominator is None: 237 if type(numerator) is int: 238 self._numerator = numerator 239 self._denominator = 1 240 return self 241 242 elif isinstance(numerator, numbers.Rational): 243 self._numerator = numerator.numerator 244 self._denominator = numerator.denominator 245 return self 246 247 elif isinstance(numerator, (float, Decimal)): 248 # Exact conversion 249 self._numerator, self._denominator = numerator.as_integer_ratio() 250 return self 251 252 elif isinstance(numerator, str): 253 # Handle construction from strings. 254 m = _RATIONAL_FORMAT.match(numerator) 255 if m is None: 256 raise ValueError('Invalid literal for Fraction: %r' % 257 numerator) 258 numerator = int(m.group('num') or '0') 259 denom = m.group('denom') 260 if denom: 261 denominator = int(denom) 262 else: 263 denominator = 1 264 decimal = m.group('decimal') 265 if decimal: 266 decimal = decimal.replace('_', '') 267 scale = 10**len(decimal) 268 numerator = numerator * scale + int(decimal) 269 denominator *= scale 270 exp = m.group('exp') 271 if exp: 272 exp = int(exp) 273 if exp >= 0: 274 numerator *= 10**exp 275 else: 276 denominator *= 10**-exp 277 if m.group('sign') == '-': 278 numerator = -numerator 279 280 else: 281 raise TypeError("argument should be a string " 282 "or a Rational instance") 283 284 elif type(numerator) is int is type(denominator): 285 pass # *very* normal case 286 287 elif (isinstance(numerator, numbers.Rational) and 288 isinstance(denominator, numbers.Rational)): 289 numerator, denominator = ( 290 numerator.numerator * denominator.denominator, 291 denominator.numerator * numerator.denominator 292 ) 293 else: 294 raise TypeError("both arguments should be " 295 "Rational instances") 296 297 if denominator == 0: 298 raise ZeroDivisionError('Fraction(%s, 0)' % numerator) 299 g = math.gcd(numerator, denominator) 300 if denominator < 0: 301 g = -g 302 numerator //= g 303 denominator //= g 304 self._numerator = numerator 305 self._denominator = denominator 306 return self 307 308 @classmethod 309 def from_float(cls, f): 310 """Converts a finite float to a rational number, exactly. 311 312 Beware that Fraction.from_float(0.3) != Fraction(3, 10). 313 314 """ 315 if isinstance(f, numbers.Integral): 316 return cls(f) 317 elif not isinstance(f, float): 318 raise TypeError("%s.from_float() only takes floats, not %r (%s)" % 319 (cls.__name__, f, type(f).__name__)) 320 return cls._from_coprime_ints(*f.as_integer_ratio()) 321 322 @classmethod 323 def from_decimal(cls, dec): 324 """Converts a finite Decimal instance to a rational number, exactly.""" 325 from decimal import Decimal 326 if isinstance(dec, numbers.Integral): 327 dec = Decimal(int(dec)) 328 elif not isinstance(dec, Decimal): 329 raise TypeError( 330 "%s.from_decimal() only takes Decimals, not %r (%s)" % 331 (cls.__name__, dec, type(dec).__name__)) 332 return cls._from_coprime_ints(*dec.as_integer_ratio()) 333 334 @classmethod 335 def _from_coprime_ints(cls, numerator, denominator, /): 336 """Convert a pair of ints to a rational number, for internal use. 337 338 The ratio of integers should be in lowest terms and the denominator 339 should be positive. 340 """ 341 obj = super(Fraction, cls).__new__(cls) 342 obj._numerator = numerator 343 obj._denominator = denominator 344 return obj 345 346 def is_integer(self): 347 """Return True if the Fraction is an integer.""" 348 return self._denominator == 1 349 350 def as_integer_ratio(self): 351 """Return a pair of integers, whose ratio is equal to the original Fraction. 352 353 The ratio is in lowest terms and has a positive denominator. 354 """ 355 return (self._numerator, self._denominator) 356 357 def limit_denominator(self, max_denominator=1000000): 358 """Closest Fraction to self with denominator at most max_denominator. 359 360 >>> Fraction('3.141592653589793').limit_denominator(10) 361 Fraction(22, 7) 362 >>> Fraction('3.141592653589793').limit_denominator(100) 363 Fraction(311, 99) 364 >>> Fraction(4321, 8765).limit_denominator(10000) 365 Fraction(4321, 8765) 366 367 """ 368 # Algorithm notes: For any real number x, define a *best upper 369 # approximation* to x to be a rational number p/q such that: 370 # 371 # (1) p/q >= x, and 372 # (2) if p/q > r/s >= x then s > q, for any rational r/s. 373 # 374 # Define *best lower approximation* similarly. Then it can be 375 # proved that a rational number is a best upper or lower 376 # approximation to x if, and only if, it is a convergent or 377 # semiconvergent of the (unique shortest) continued fraction 378 # associated to x. 379 # 380 # To find a best rational approximation with denominator <= M, 381 # we find the best upper and lower approximations with 382 # denominator <= M and take whichever of these is closer to x. 383 # In the event of a tie, the bound with smaller denominator is 384 # chosen. If both denominators are equal (which can happen 385 # only when max_denominator == 1 and self is midway between 386 # two integers) the lower bound---i.e., the floor of self, is 387 # taken. 388 389 if max_denominator < 1: 390 raise ValueError("max_denominator should be at least 1") 391 if self._denominator <= max_denominator: 392 return Fraction(self) 393 394 p0, q0, p1, q1 = 0, 1, 1, 0 395 n, d = self._numerator, self._denominator 396 while True: 397 a = n//d 398 q2 = q0+a*q1 399 if q2 > max_denominator: 400 break 401 p0, q0, p1, q1 = p1, q1, p0+a*p1, q2 402 n, d = d, n-a*d 403 k = (max_denominator-q0)//q1 404 405 # Determine which of the candidates (p0+k*p1)/(q0+k*q1) and p1/q1 is 406 # closer to self. The distance between them is 1/(q1*(q0+k*q1)), while 407 # the distance from p1/q1 to self is d/(q1*self._denominator). So we 408 # need to compare 2*(q0+k*q1) with self._denominator/d. 409 if 2*d*(q0+k*q1) <= self._denominator: 410 return Fraction._from_coprime_ints(p1, q1) 411 else: 412 return Fraction._from_coprime_ints(p0+k*p1, q0+k*q1) 413 414 @property 415 def numerator(a): 416 return a._numerator 417 418 @property 419 def denominator(a): 420 return a._denominator 421 422 def __repr__(self): 423 """repr(self)""" 424 return '%s(%s, %s)' % (self.__class__.__name__, 425 self._numerator, self._denominator) 426 427 def __str__(self): 428 """str(self)""" 429 if self._denominator == 1: 430 return str(self._numerator) 431 else: 432 return '%s/%s' % (self._numerator, self._denominator) 433 434 def _format_general(self, match): 435 """Helper method for __format__. 436 437 Handles fill, alignment, signs, and thousands separators in the 438 case of no presentation type. 439 """ 440 # Validate and parse the format specifier. 441 fill = match["fill"] or " " 442 align = match["align"] or ">" 443 pos_sign = "" if match["sign"] == "-" else match["sign"] 444 alternate_form = bool(match["alt"]) 445 minimumwidth = int(match["minimumwidth"] or "0") 446 thousands_sep = match["thousands_sep"] or '' 447 448 # Determine the body and sign representation. 449 n, d = self._numerator, self._denominator 450 if d > 1 or alternate_form: 451 body = f"{abs(n):{thousands_sep}}/{d:{thousands_sep}}" 452 else: 453 body = f"{abs(n):{thousands_sep}}" 454 sign = '-' if n < 0 else pos_sign 455 456 # Pad with fill character if necessary and return. 457 padding = fill * (minimumwidth - len(sign) - len(body)) 458 if align == ">": 459 return padding + sign + body 460 elif align == "<": 461 return sign + body + padding 462 elif align == "^": 463 half = len(padding) // 2 464 return padding[:half] + sign + body + padding[half:] 465 else: # align == "=" 466 return sign + padding + body 467 468 def _format_float_style(self, match): 469 """Helper method for __format__; handles float presentation types.""" 470 fill = match["fill"] or " " 471 align = match["align"] or ">" 472 pos_sign = "" if match["sign"] == "-" else match["sign"] 473 no_neg_zero = bool(match["no_neg_zero"]) 474 alternate_form = bool(match["alt"]) 475 zeropad = bool(match["zeropad"]) 476 minimumwidth = int(match["minimumwidth"] or "0") 477 thousands_sep = match["thousands_sep"] 478 precision = int(match["precision"] or "6") 479 presentation_type = match["presentation_type"] 480 trim_zeros = presentation_type in "gG" and not alternate_form 481 trim_point = not alternate_form 482 exponent_indicator = "E" if presentation_type in "EFG" else "e" 483 484 # Round to get the digits we need, figure out where to place the point, 485 # and decide whether to use scientific notation. 'point_pos' is the 486 # relative to the _end_ of the digit string: that is, it's the number 487 # of digits that should follow the point. 488 if presentation_type in "fF%": 489 exponent = -precision 490 if presentation_type == "%": 491 exponent -= 2 492 negative, significand = _round_to_exponent( 493 self._numerator, self._denominator, exponent, no_neg_zero) 494 scientific = False 495 point_pos = precision 496 else: # presentation_type in "eEgG" 497 figures = ( 498 max(precision, 1) 499 if presentation_type in "gG" 500 else precision + 1 501 ) 502 negative, significand, exponent = _round_to_figures( 503 self._numerator, self._denominator, figures) 504 scientific = ( 505 presentation_type in "eE" 506 or exponent > 0 507 or exponent + figures <= -4 508 ) 509 point_pos = figures - 1 if scientific else -exponent 510 511 # Get the suffix - the part following the digits, if any. 512 if presentation_type == "%": 513 suffix = "%" 514 elif scientific: 515 suffix = f"{exponent_indicator}{exponent + point_pos:+03d}" 516 else: 517 suffix = "" 518 519 # String of output digits, padded sufficiently with zeros on the left 520 # so that we'll have at least one digit before the decimal point. 521 digits = f"{significand:0{point_pos + 1}d}" 522 523 # Before padding, the output has the form f"{sign}{leading}{trailing}", 524 # where `leading` includes thousands separators if necessary and 525 # `trailing` includes the decimal separator where appropriate. 526 sign = "-" if negative else pos_sign 527 leading = digits[: len(digits) - point_pos] 528 frac_part = digits[len(digits) - point_pos :] 529 if trim_zeros: 530 frac_part = frac_part.rstrip("0") 531 separator = "" if trim_point and not frac_part else "." 532 trailing = separator + frac_part + suffix 533 534 # Do zero padding if required. 535 if zeropad: 536 min_leading = minimumwidth - len(sign) - len(trailing) 537 # When adding thousands separators, they'll be added to the 538 # zero-padded portion too, so we need to compensate. 539 leading = leading.zfill( 540 3 * min_leading // 4 + 1 if thousands_sep else min_leading 541 ) 542 543 # Insert thousands separators if required. 544 if thousands_sep: 545 first_pos = 1 + (len(leading) - 1) % 3 546 leading = leading[:first_pos] + "".join( 547 thousands_sep + leading[pos : pos + 3] 548 for pos in range(first_pos, len(leading), 3) 549 ) 550 551 # We now have a sign and a body. Pad with fill character if necessary 552 # and return. 553 body = leading + trailing 554 padding = fill * (minimumwidth - len(sign) - len(body)) 555 if align == ">": 556 return padding + sign + body 557 elif align == "<": 558 return sign + body + padding 559 elif align == "^": 560 half = len(padding) // 2 561 return padding[:half] + sign + body + padding[half:] 562 else: # align == "=" 563 return sign + padding + body 564 565 def __format__(self, format_spec, /): 566 """Format this fraction according to the given format specification.""" 567 568 if match := _GENERAL_FORMAT_SPECIFICATION_MATCHER(format_spec): 569 return self._format_general(match) 570 571 if match := _FLOAT_FORMAT_SPECIFICATION_MATCHER(format_spec): 572 # Refuse the temptation to guess if both alignment _and_ 573 # zero padding are specified. 574 if match["align"] is None or match["zeropad"] is None: 575 return self._format_float_style(match) 576 577 raise ValueError( 578 f"Invalid format specifier {format_spec!r} " 579 f"for object of type {type(self).__name__!r}" 580 ) 581 582 def _operator_fallbacks(monomorphic_operator, fallback_operator, 583 handle_complex=True): 584 """Generates forward and reverse operators given a purely-rational 585 operator and a function from the operator module. 586 587 Use this like: 588 __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op) 589 590 In general, we want to implement the arithmetic operations so 591 that mixed-mode operations either call an implementation whose 592 author knew about the types of both arguments, or convert both 593 to the nearest built in type and do the operation there. In 594 Fraction, that means that we define __add__ and __radd__ as: 595 596 def __add__(self, other): 597 # Both types have numerators/denominator attributes, 598 # so do the operation directly 599 if isinstance(other, (int, Fraction)): 600 return Fraction(self.numerator * other.denominator + 601 other.numerator * self.denominator, 602 self.denominator * other.denominator) 603 # float and complex don't have those operations, but we 604 # know about those types, so special case them. 605 elif isinstance(other, float): 606 return float(self) + other 607 elif isinstance(other, complex): 608 return complex(self) + other 609 # Let the other type take over. 610 return NotImplemented 611 612 def __radd__(self, other): 613 # radd handles more types than add because there's 614 # nothing left to fall back to. 615 if isinstance(other, numbers.Rational): 616 return Fraction(self.numerator * other.denominator + 617 other.numerator * self.denominator, 618 self.denominator * other.denominator) 619 elif isinstance(other, Real): 620 return float(other) + float(self) 621 elif isinstance(other, Complex): 622 return complex(other) + complex(self) 623 return NotImplemented 624 625 626 There are 5 different cases for a mixed-type addition on 627 Fraction. I'll refer to all of the above code that doesn't 628 refer to Fraction, float, or complex as "boilerplate". 'r' 629 will be an instance of Fraction, which is a subtype of 630 Rational (r : Fraction <: Rational), and b : B <: 631 Complex. The first three involve 'r + b': 632 633 1. If B <: Fraction, int, float, or complex, we handle 634 that specially, and all is well. 635 2. If Fraction falls back to the boilerplate code, and it 636 were to return a value from __add__, we'd miss the 637 possibility that B defines a more intelligent __radd__, 638 so the boilerplate should return NotImplemented from 639 __add__. In particular, we don't handle Rational 640 here, even though we could get an exact answer, in case 641 the other type wants to do something special. 642 3. If B <: Fraction, Python tries B.__radd__ before 643 Fraction.__add__. This is ok, because it was 644 implemented with knowledge of Fraction, so it can 645 handle those instances before delegating to Real or 646 Complex. 647 648 The next two situations describe 'b + r'. We assume that b 649 didn't know about Fraction in its implementation, and that it 650 uses similar boilerplate code: 651 652 4. If B <: Rational, then __radd_ converts both to the 653 builtin rational type (hey look, that's us) and 654 proceeds. 655 5. Otherwise, __radd__ tries to find the nearest common 656 base ABC, and fall back to its builtin type. Since this 657 class doesn't subclass a concrete type, there's no 658 implementation to fall back to, so we need to try as 659 hard as possible to return an actual value, or the user 660 will get a TypeError. 661 662 """ 663 def forward(a, b): 664 if isinstance(b, Fraction): 665 return monomorphic_operator(a, b) 666 elif isinstance(b, int): 667 return monomorphic_operator(a, Fraction(b)) 668 elif isinstance(b, float): 669 return fallback_operator(float(a), b) 670 elif handle_complex and isinstance(b, complex): 671 return fallback_operator(complex(a), b) 672 else: 673 return NotImplemented 674 forward.__name__ = '__' + fallback_operator.__name__ + '__' 675 forward.__doc__ = monomorphic_operator.__doc__ 676 677 def reverse(b, a): 678 if isinstance(a, numbers.Rational): 679 # Includes ints. 680 return monomorphic_operator(Fraction(a), b) 681 elif isinstance(a, numbers.Real): 682 return fallback_operator(float(a), float(b)) 683 elif handle_complex and isinstance(a, numbers.Complex): 684 return fallback_operator(complex(a), complex(b)) 685 else: 686 return NotImplemented 687 reverse.__name__ = '__r' + fallback_operator.__name__ + '__' 688 reverse.__doc__ = monomorphic_operator.__doc__ 689 690 return forward, reverse 691 692 # Rational arithmetic algorithms: Knuth, TAOCP, Volume 2, 4.5.1. 693 # 694 # Assume input fractions a and b are normalized. 695 # 696 # 1) Consider addition/subtraction. 697 # 698 # Let g = gcd(da, db). Then 699 # 700 # na nb na*db ± nb*da 701 # a ± b == -- ± -- == ------------- == 702 # da db da*db 703 # 704 # na*(db//g) ± nb*(da//g) t 705 # == ----------------------- == - 706 # (da*db)//g d 707 # 708 # Now, if g > 1, we're working with smaller integers. 709 # 710 # Note, that t, (da//g) and (db//g) are pairwise coprime. 711 # 712 # Indeed, (da//g) and (db//g) share no common factors (they were 713 # removed) and da is coprime with na (since input fractions are 714 # normalized), hence (da//g) and na are coprime. By symmetry, 715 # (db//g) and nb are coprime too. Then, 716 # 717 # gcd(t, da//g) == gcd(na*(db//g), da//g) == 1 718 # gcd(t, db//g) == gcd(nb*(da//g), db//g) == 1 719 # 720 # Above allows us optimize reduction of the result to lowest 721 # terms. Indeed, 722 # 723 # g2 = gcd(t, d) == gcd(t, (da//g)*(db//g)*g) == gcd(t, g) 724 # 725 # t//g2 t//g2 726 # a ± b == ----------------------- == ---------------- 727 # (da//g)*(db//g)*(g//g2) (da//g)*(db//g2) 728 # 729 # is a normalized fraction. This is useful because the unnormalized 730 # denominator d could be much larger than g. 731 # 732 # We should special-case g == 1 (and g2 == 1), since 60.8% of 733 # randomly-chosen integers are coprime: 734 # https://en.wikipedia.org/wiki/Coprime_integers#Probability_of_coprimality 735 # Note, that g2 == 1 always for fractions, obtained from floats: here 736 # g is a power of 2 and the unnormalized numerator t is an odd integer. 737 # 738 # 2) Consider multiplication 739 # 740 # Let g1 = gcd(na, db) and g2 = gcd(nb, da), then 741 # 742 # na*nb na*nb (na//g1)*(nb//g2) 743 # a*b == ----- == ----- == ----------------- 744 # da*db db*da (db//g1)*(da//g2) 745 # 746 # Note, that after divisions we're multiplying smaller integers. 747 # 748 # Also, the resulting fraction is normalized, because each of 749 # two factors in the numerator is coprime to each of the two factors 750 # in the denominator. 751 # 752 # Indeed, pick (na//g1). It's coprime with (da//g2), because input 753 # fractions are normalized. It's also coprime with (db//g1), because 754 # common factors are removed by g1 == gcd(na, db). 755 # 756 # As for addition/subtraction, we should special-case g1 == 1 757 # and g2 == 1 for same reason. That happens also for multiplying 758 # rationals, obtained from floats. 759 760 def _add(a, b): 761 """a + b""" 762 na, da = a._numerator, a._denominator 763 nb, db = b._numerator, b._denominator 764 g = math.gcd(da, db) 765 if g == 1: 766 return Fraction._from_coprime_ints(na * db + da * nb, da * db) 767 s = da // g 768 t = na * (db // g) + nb * s 769 g2 = math.gcd(t, g) 770 if g2 == 1: 771 return Fraction._from_coprime_ints(t, s * db) 772 return Fraction._from_coprime_ints(t // g2, s * (db // g2)) 773 774 __add__, __radd__ = _operator_fallbacks(_add, operator.add) 775 776 def _sub(a, b): 777 """a - b""" 778 na, da = a._numerator, a._denominator 779 nb, db = b._numerator, b._denominator 780 g = math.gcd(da, db) 781 if g == 1: 782 return Fraction._from_coprime_ints(na * db - da * nb, da * db) 783 s = da // g 784 t = na * (db // g) - nb * s 785 g2 = math.gcd(t, g) 786 if g2 == 1: 787 return Fraction._from_coprime_ints(t, s * db) 788 return Fraction._from_coprime_ints(t // g2, s * (db // g2)) 789 790 __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub) 791 792 def _mul(a, b): 793 """a * b""" 794 na, da = a._numerator, a._denominator 795 nb, db = b._numerator, b._denominator 796 g1 = math.gcd(na, db) 797 if g1 > 1: 798 na //= g1 799 db //= g1 800 g2 = math.gcd(nb, da) 801 if g2 > 1: 802 nb //= g2 803 da //= g2 804 return Fraction._from_coprime_ints(na * nb, db * da) 805 806 __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul) 807 808 def _div(a, b): 809 """a / b""" 810 # Same as _mul(), with inversed b. 811 nb, db = b._numerator, b._denominator 812 if nb == 0: 813 raise ZeroDivisionError('Fraction(%s, 0)' % db) 814 na, da = a._numerator, a._denominator 815 g1 = math.gcd(na, nb) 816 if g1 > 1: 817 na //= g1 818 nb //= g1 819 g2 = math.gcd(db, da) 820 if g2 > 1: 821 da //= g2 822 db //= g2 823 n, d = na * db, nb * da 824 if d < 0: 825 n, d = -n, -d 826 return Fraction._from_coprime_ints(n, d) 827 828 __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv) 829 830 def _floordiv(a, b): 831 """a // b""" 832 return (a.numerator * b.denominator) // (a.denominator * b.numerator) 833 834 __floordiv__, __rfloordiv__ = _operator_fallbacks(_floordiv, operator.floordiv, False) 835 836 def _divmod(a, b): 837 """(a // b, a % b)""" 838 da, db = a.denominator, b.denominator 839 div, n_mod = divmod(a.numerator * db, da * b.numerator) 840 return div, Fraction(n_mod, da * db) 841 842 __divmod__, __rdivmod__ = _operator_fallbacks(_divmod, divmod, False) 843 844 def _mod(a, b): 845 """a % b""" 846 da, db = a.denominator, b.denominator 847 return Fraction((a.numerator * db) % (b.numerator * da), da * db) 848 849 __mod__, __rmod__ = _operator_fallbacks(_mod, operator.mod, False) 850 851 def __pow__(a, b): 852 """a ** b 853 854 If b is not an integer, the result will be a float or complex 855 since roots are generally irrational. If b is an integer, the 856 result will be rational. 857 858 """ 859 if isinstance(b, numbers.Rational): 860 if b.denominator == 1: 861 power = b.numerator 862 if power >= 0: 863 return Fraction._from_coprime_ints(a._numerator ** power, 864 a._denominator ** power) 865 elif a._numerator > 0: 866 return Fraction._from_coprime_ints(a._denominator ** -power, 867 a._numerator ** -power) 868 elif a._numerator == 0: 869 raise ZeroDivisionError('Fraction(%s, 0)' % 870 a._denominator ** -power) 871 else: 872 return Fraction._from_coprime_ints((-a._denominator) ** -power, 873 (-a._numerator) ** -power) 874 else: 875 # A fractional power will generally produce an 876 # irrational number. 877 return float(a) ** float(b) 878 elif isinstance(b, (float, complex)): 879 return float(a) ** b 880 else: 881 return NotImplemented 882 883 def __rpow__(b, a): 884 """a ** b""" 885 if b._denominator == 1 and b._numerator >= 0: 886 # If a is an int, keep it that way if possible. 887 return a ** b._numerator 888 889 if isinstance(a, numbers.Rational): 890 return Fraction(a.numerator, a.denominator) ** b 891 892 if b._denominator == 1: 893 return a ** b._numerator 894 895 return a ** float(b) 896 897 def __pos__(a): 898 """+a: Coerces a subclass instance to Fraction""" 899 return Fraction._from_coprime_ints(a._numerator, a._denominator) 900 901 def __neg__(a): 902 """-a""" 903 return Fraction._from_coprime_ints(-a._numerator, a._denominator) 904 905 def __abs__(a): 906 """abs(a)""" 907 return Fraction._from_coprime_ints(abs(a._numerator), a._denominator) 908 909 def __int__(a, _index=operator.index): 910 """int(a)""" 911 if a._numerator < 0: 912 return _index(-(-a._numerator // a._denominator)) 913 else: 914 return _index(a._numerator // a._denominator) 915 916 def __trunc__(a): 917 """math.trunc(a)""" 918 if a._numerator < 0: 919 return -(-a._numerator // a._denominator) 920 else: 921 return a._numerator // a._denominator 922 923 def __floor__(a): 924 """math.floor(a)""" 925 return a._numerator // a._denominator 926 927 def __ceil__(a): 928 """math.ceil(a)""" 929 # The negations cleverly convince floordiv to return the ceiling. 930 return -(-a._numerator // a._denominator) 931 932 def __round__(self, ndigits=None): 933 """round(self, ndigits) 934 935 Rounds half toward even. 936 """ 937 if ndigits is None: 938 d = self._denominator 939 floor, remainder = divmod(self._numerator, d) 940 if remainder * 2 < d: 941 return floor 942 elif remainder * 2 > d: 943 return floor + 1 944 # Deal with the half case: 945 elif floor % 2 == 0: 946 return floor 947 else: 948 return floor + 1 949 shift = 10**abs(ndigits) 950 # See _operator_fallbacks.forward to check that the results of 951 # these operations will always be Fraction and therefore have 952 # round(). 953 if ndigits > 0: 954 return Fraction(round(self * shift), shift) 955 else: 956 return Fraction(round(self / shift) * shift) 957 958 def __hash__(self): 959 """hash(self)""" 960 return _hash_algorithm(self._numerator, self._denominator) 961 962 def __eq__(a, b): 963 """a == b""" 964 if type(b) is int: 965 return a._numerator == b and a._denominator == 1 966 if isinstance(b, numbers.Rational): 967 return (a._numerator == b.numerator and 968 a._denominator == b.denominator) 969 if isinstance(b, numbers.Complex) and b.imag == 0: 970 b = b.real 971 if isinstance(b, float): 972 if math.isnan(b) or math.isinf(b): 973 # comparisons with an infinity or nan should behave in 974 # the same way for any finite a, so treat a as zero. 975 return 0.0 == b 976 else: 977 return a == a.from_float(b) 978 else: 979 # Since a doesn't know how to compare with b, let's give b 980 # a chance to compare itself with a. 981 return NotImplemented 982 983 def _richcmp(self, other, op): 984 """Helper for comparison operators, for internal use only. 985 986 Implement comparison between a Rational instance `self`, and 987 either another Rational instance or a float `other`. If 988 `other` is not a Rational instance or a float, return 989 NotImplemented. `op` should be one of the six standard 990 comparison operators. 991 992 """ 993 # convert other to a Rational instance where reasonable. 994 if isinstance(other, numbers.Rational): 995 return op(self._numerator * other.denominator, 996 self._denominator * other.numerator) 997 if isinstance(other, float): 998 if math.isnan(other) or math.isinf(other): 999 return op(0.0, other) 1000 else: 1001 return op(self, self.from_float(other)) 1002 else: 1003 return NotImplemented 1004 1005 def __lt__(a, b): 1006 """a < b""" 1007 return a._richcmp(b, operator.lt) 1008 1009 def __gt__(a, b): 1010 """a > b""" 1011 return a._richcmp(b, operator.gt) 1012 1013 def __le__(a, b): 1014 """a <= b""" 1015 return a._richcmp(b, operator.le) 1016 1017 def __ge__(a, b): 1018 """a >= b""" 1019 return a._richcmp(b, operator.ge) 1020 1021 def __bool__(a): 1022 """a != 0""" 1023 # bpo-39274: Use bool() because (a._numerator != 0) can return an 1024 # object which is not a bool. 1025 return bool(a._numerator) 1026 1027 # support for pickling, copy, and deepcopy 1028 1029 def __reduce__(self): 1030 return (self.__class__, (self._numerator, self._denominator)) 1031 1032 def __copy__(self): 1033 if type(self) == Fraction: 1034 return self # I'm immutable; therefore I am my own clone 1035 return self.__class__(self._numerator, self._denominator) 1036 1037 def __deepcopy__(self, memo): 1038 if type(self) == Fraction: 1039 return self # My components are also immutable 1040 return self.__class__(self._numerator, self._denominator) 1041