Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/fractions.py: 26%
270 statements
« prev ^ index » next coverage.py v7.0.1, created at 2022-12-25 06:11 +0000
1# Originally contributed by Sjoerd Mullender.
2# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>.
4"""Fraction, infinite-precision, real numbers."""
6from decimal import Decimal
7import math
8import numbers
9import operator
10import re
11import sys
13__all__ = ['Fraction', 'gcd']
17def gcd(a, b):
18 """Calculate the Greatest Common Divisor of a and b.
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)
32def _gcd(a, b):
33 # Supports non-integers for backward compatibility.
34 while b:
35 a, b = b, a%b
36 return a
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
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)
60class Fraction(numbers.Rational):
61 """This class implements rational numbers.
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.
68 Fractions can also be constructed from:
70 - numeric strings similar to those accepted by the
71 float constructor (for example, '-2.3' or '1e10')
73 - strings of the form '123/456'
75 - float and Decimal instances
77 - other Rational instances (including integers)
79 """
81 __slots__ = ('_numerator', '_denominator')
83 # We're immutable, so use __new__ not __init__
84 def __new__(cls, numerator=0, denominator=None, *, _normalize=True):
85 """Constructs a Rational.
87 Takes a string like '3/2' or '1.5', another Rational instance, a
88 numerator/denominator pair, or a float.
90 Examples
91 --------
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)
114 """
115 self = super(Fraction, cls).__new__(cls)
117 if denominator is None:
118 if type(numerator) is int:
119 self._numerator = numerator
120 self._denominator = 1
121 return self
123 elif isinstance(numerator, numbers.Rational):
124 self._numerator = numerator.numerator
125 self._denominator = numerator.denominator
126 return self
128 elif isinstance(numerator, (float, Decimal)):
129 # Exact conversion
130 self._numerator, self._denominator = numerator.as_integer_ratio()
131 return self
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
160 else:
161 raise TypeError("argument should be a string "
162 "or a Rational instance")
164 elif type(numerator) is int is type(denominator):
165 pass # *very* normal case
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")
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
193 @classmethod
194 def from_float(cls, f):
195 """Converts a finite float to a rational number, exactly.
197 Beware that Fraction.from_float(0.3) != Fraction(3, 10).
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())
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())
219 def as_integer_ratio(self):
220 """Return the integer ratio as a tuple.
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)
227 def limit_denominator(self, max_denominator=1000000):
228 """Closest Fraction to self with denominator at most max_denominator.
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)
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.
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)
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
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
282 @property
283 def numerator(a):
284 return a._numerator
286 @property
287 def denominator(a):
288 return a._denominator
290 def __repr__(self):
291 """repr(self)"""
292 return '%s(%s, %s)' % (self.__class__.__name__,
293 self._numerator, self._denominator)
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)
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.
306 Use this like:
307 __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op)
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:
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
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
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':
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.
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:
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.
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__
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__
407 return forward, reverse
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)
415 __add__, __radd__ = _operator_fallbacks(_add, operator.add)
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)
423 __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)
425 def _mul(a, b):
426 """a * b"""
427 return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)
429 __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)
431 def _div(a, b):
432 """a / b"""
433 return Fraction(a.numerator * b.denominator,
434 a.denominator * b.numerator)
436 __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)
438 def _floordiv(a, b):
439 """a // b"""
440 return (a.numerator * b.denominator) // (a.denominator * b.numerator)
442 __floordiv__, __rfloordiv__ = _operator_fallbacks(_floordiv, operator.floordiv)
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)
450 __divmod__, __rdivmod__ = _operator_fallbacks(_divmod, divmod)
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)
457 __mod__, __rmod__ = _operator_fallbacks(_mod, operator.mod)
459 def __pow__(a, b):
460 """a ** b
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.
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
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
495 if isinstance(a, numbers.Rational):
496 return Fraction(a.numerator, a.denominator) ** b
498 if b._denominator == 1:
499 return a ** b._numerator
501 return a ** float(b)
503 def __pos__(a):
504 """+a: Coerces a subclass instance to Fraction"""
505 return Fraction(a._numerator, a._denominator, _normalize=False)
507 def __neg__(a):
508 """-a"""
509 return Fraction(-a._numerator, a._denominator, _normalize=False)
511 def __abs__(a):
512 """abs(a)"""
513 return Fraction(abs(a._numerator), a._denominator, _normalize=False)
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
522 def __floor__(a):
523 """math.floor(a)"""
524 return a.numerator // a.denominator
526 def __ceil__(a):
527 """math.ceil(a)"""
528 # The negations cleverly convince floordiv to return the ceiling.
529 return -(-a.numerator // a.denominator)
531 def __round__(self, ndigits=None):
532 """round(self, ndigits)
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)
556 def __hash__(self):
557 """hash(self)"""
559 # XXX since this method is expensive, consider caching the result
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').
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
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
599 def _richcmp(self, other, op):
600 """Helper for comparison operators, for internal use only.
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.
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
621 def __lt__(a, b):
622 """a < b"""
623 return a._richcmp(b, operator.lt)
625 def __gt__(a, b):
626 """a > b"""
627 return a._richcmp(b, operator.gt)
629 def __le__(a, b):
630 """a <= b"""
631 return a._richcmp(b, operator.le)
633 def __ge__(a, b):
634 """a >= b"""
635 return a._richcmp(b, operator.ge)
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)
643 # support for pickling, copy, and deepcopy
645 def __reduce__(self):
646 return (self.__class__, (str(self),))
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)
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)