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