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