ยปCore Development>Code coverage>Lib/fractions.py

Python code coverage for Lib/fractions.py

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