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>. 

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'] 

14 

15 

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 

22 

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) 

36 

37 

38class Fraction(numbers.Rational): 

39 """This class implements rational numbers. 

40 

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. 

45 

46 Fractions can also be constructed from: 

47 

48 - numeric strings similar to those accepted by the 

49 float constructor (for example, '-2.3' or '1e10') 

50 

51 - strings of the form '123/456' 

52 

53 - float and Decimal instances 

54 

55 - other Rational instances (including integers) 

56 

57 """ 

58 

59 __slots__ = ('_numerator', '_denominator') 

60 

61 # We're immutable, so use __new__ not __init__ 

62 def __new__(cls, numerator=0, denominator=None, *, _normalize=True): 

63 """Constructs a Rational. 

64 

65 Takes a string like '3/2' or '1.5', another Rational instance, a 

66 numerator/denominator pair, or a float. 

67 

68 Examples 

69 -------- 

70 

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) 

91 

92 """ 

93 self = super(Fraction, cls).__new__(cls) 

94 

95 if denominator is None: 

96 if type(numerator) is int: 

97 self._numerator = numerator 

98 self._denominator = 1 

99 return self 

100 

101 elif isinstance(numerator, numbers.Rational): 

102 self._numerator = numerator.numerator 

103 self._denominator = numerator.denominator 

104 return self 

105 

106 elif isinstance(numerator, (float, Decimal)): 

107 # Exact conversion 

108 self._numerator, self._denominator = numerator.as_integer_ratio() 

109 return self 

110 

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 

137 

138 else: 

139 raise TypeError("argument should be a string " 

140 "or a Rational instance") 

141 

142 elif type(numerator) is int is type(denominator): 

143 pass # *very* normal case 

144 

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") 

154 

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 

166 

167 @classmethod 

168 def from_float(cls, f): 

169 """Converts a finite float to a rational number, exactly. 

170 

171 Beware that Fraction.from_float(0.3) != Fraction(3, 10). 

172 

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()) 

180 

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()) 

192 

193 def as_integer_ratio(self): 

194 """Return the integer ratio as a tuple. 

195 

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) 

200 

201 def limit_denominator(self, max_denominator=1000000): 

202 """Closest Fraction to self with denominator at most max_denominator. 

203 

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) 

210 

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. 

232 

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) 

237 

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 

247 

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 

255 

256 @property 

257 def numerator(a): 

258 return a._numerator 

259 

260 @property 

261 def denominator(a): 

262 return a._denominator 

263 

264 def __repr__(self): 

265 """repr(self)""" 

266 return '%s(%s, %s)' % (self.__class__.__name__, 

267 self._numerator, self._denominator) 

268 

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) 

275 

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. 

279 

280 Use this like: 

281 __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op) 

282 

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: 

288 

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 

304 

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 

317 

318 

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': 

325 

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. 

340 

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: 

344 

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. 

354 

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__ 

367 

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__ 

380 

381 return forward, reverse 

382 

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) 

388 

389 __add__, __radd__ = _operator_fallbacks(_add, operator.add) 

390 

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) 

396 

397 __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub) 

398 

399 def _mul(a, b): 

400 """a * b""" 

401 return Fraction(a.numerator * b.numerator, a.denominator * b.denominator) 

402 

403 __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul) 

404 

405 def _div(a, b): 

406 """a / b""" 

407 return Fraction(a.numerator * b.denominator, 

408 a.denominator * b.numerator) 

409 

410 __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv) 

411 

412 def _floordiv(a, b): 

413 """a // b""" 

414 return (a.numerator * b.denominator) // (a.denominator * b.numerator) 

415 

416 __floordiv__, __rfloordiv__ = _operator_fallbacks(_floordiv, operator.floordiv) 

417 

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) 

423 

424 __divmod__, __rdivmod__ = _operator_fallbacks(_divmod, divmod) 

425 

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) 

430 

431 __mod__, __rmod__ = _operator_fallbacks(_mod, operator.mod) 

432 

433 def __pow__(a, b): 

434 """a ** b 

435 

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. 

439 

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 

462 

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 

468 

469 if isinstance(a, numbers.Rational): 

470 return Fraction(a.numerator, a.denominator) ** b 

471 

472 if b._denominator == 1: 

473 return a ** b._numerator 

474 

475 return a ** float(b) 

476 

477 def __pos__(a): 

478 """+a: Coerces a subclass instance to Fraction""" 

479 return Fraction(a._numerator, a._denominator, _normalize=False) 

480 

481 def __neg__(a): 

482 """-a""" 

483 return Fraction(-a._numerator, a._denominator, _normalize=False) 

484 

485 def __abs__(a): 

486 """abs(a)""" 

487 return Fraction(abs(a._numerator), a._denominator, _normalize=False) 

488 

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 

495 

496 def __floor__(a): 

497 """math.floor(a)""" 

498 return a.numerator // a.denominator 

499 

500 def __ceil__(a): 

501 """math.ceil(a)""" 

502 # The negations cleverly convince floordiv to return the ceiling. 

503 return -(-a.numerator // a.denominator) 

504 

505 def __round__(self, ndigits=None): 

506 """round(self, ndigits) 

507 

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) 

529 

530 def __hash__(self): 

531 """hash(self)""" 

532 

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'). 

537 

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 

562 

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 

583 

584 def _richcmp(self, other, op): 

585 """Helper for comparison operators, for internal use only. 

586 

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. 

592 

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 

605 

606 def __lt__(a, b): 

607 """a < b""" 

608 return a._richcmp(b, operator.lt) 

609 

610 def __gt__(a, b): 

611 """a > b""" 

612 return a._richcmp(b, operator.gt) 

613 

614 def __le__(a, b): 

615 """a <= b""" 

616 return a._richcmp(b, operator.le) 

617 

618 def __ge__(a, b): 

619 """a >= b""" 

620 return a._richcmp(b, operator.ge) 

621 

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) 

627 

628 # support for pickling, copy, and deepcopy 

629 

630 def __reduce__(self): 

631 return (self.__class__, (str(self),)) 

632 

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) 

637 

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)