Closest Fraction to self with denominator at most max_denominator. >>> Fraction('3.141592653589793').limit_denominator(10) Fraction(22, 7) >>> Fraction('3.141592653589793').limit_denominator(100) Fraction(311, 99) >>> Fraction(4321, 8765).limit_denominator(10
(self, max_denominator=1000000)
| 382 | return (self._numerator, self._denominator) |
| 383 | |
| 384 | def limit_denominator(self, max_denominator=1000000): |
| 385 | """Closest Fraction to self with denominator at most max_denominator. |
| 386 | |
| 387 | >>> Fraction('3.141592653589793').limit_denominator(10) |
| 388 | Fraction(22, 7) |
| 389 | >>> Fraction('3.141592653589793').limit_denominator(100) |
| 390 | Fraction(311, 99) |
| 391 | >>> Fraction(4321, 8765).limit_denominator(10000) |
| 392 | Fraction(4321, 8765) |
| 393 | |
| 394 | """ |
| 395 | # Algorithm notes: For any real number x, define a *best upper |
| 396 | # approximation* to x to be a rational number p/q such that: |
| 397 | # |
| 398 | # (1) p/q >= x, and |
| 399 | # (2) if p/q > r/s >= x then s > q, for any rational r/s. |
| 400 | # |
| 401 | # Define *best lower approximation* similarly. Then it can be |
| 402 | # proved that a rational number is a best upper or lower |
| 403 | # approximation to x if, and only if, it is a convergent or |
| 404 | # semiconvergent of the (unique shortest) continued fraction |
| 405 | # associated to x. |
| 406 | # |
| 407 | # To find a best rational approximation with denominator <= M, |
| 408 | # we find the best upper and lower approximations with |
| 409 | # denominator <= M and take whichever of these is closer to x. |
| 410 | # In the event of a tie, the bound with smaller denominator is |
| 411 | # chosen. If both denominators are equal (which can happen |
| 412 | # only when max_denominator == 1 and self is midway between |
| 413 | # two integers) the lower bound---i.e., the floor of self, is |
| 414 | # taken. |
| 415 | |
| 416 | if max_denominator < 1: |
| 417 | raise ValueError("max_denominator should be at least 1") |
| 418 | if self._denominator <= max_denominator: |
| 419 | return Fraction(self) |
| 420 | |
| 421 | p0, q0, p1, q1 = 0, 1, 1, 0 |
| 422 | n, d = self._numerator, self._denominator |
| 423 | while True: |
| 424 | a = n//d |
| 425 | q2 = q0+a*q1 |
| 426 | if q2 > max_denominator: |
| 427 | break |
| 428 | p0, q0, p1, q1 = p1, q1, p0+a*p1, q2 |
| 429 | n, d = d, n-a*d |
| 430 | k = (max_denominator-q0)//q1 |
| 431 | |
| 432 | # Determine which of the candidates (p0+k*p1)/(q0+k*q1) and p1/q1 is |
| 433 | # closer to self. The distance between them is 1/(q1*(q0+k*q1)), while |
| 434 | # the distance from p1/q1 to self is d/(q1*self._denominator). So we |
| 435 | # need to compare 2*(q0+k*q1) with self._denominator/d. |
| 436 | if 2*d*(q0+k*q1) <= self._denominator: |
| 437 | return Fraction._from_coprime_ints(p1, q1) |
| 438 | else: |
| 439 | return Fraction._from_coprime_ints(p0+k*p1, q0+k*q1) |
| 440 | |
| 441 | @property |