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