class_docstr: This class implements rational numbers.
  
  In the two-argument form of the constructor, Fraction(8, 6) will
  produce a rational number equivalent to 4/3. Both arguments must
  be Rational. The numerator defaults to 0 and the denominator
  defaults to 1 so that Fraction(3) == 3 and Fraction() == 0.
  
  Fractions can also be constructed from:
  
    - numeric strings similar to those accepted by the
      float constructor (for example, '-2.3' or '1e10')
  
    - strings of the form '123/456'
  
    - float and Decimal instances
  
    - other Rational instances (including integers)
class_docstr_tok: ["This","class","implements","rational","numbers",".","In","the","two-argument","form","of","the","constructor",",","Fraction","(","8",",","6",")","will","produce","a","rational","number","equivalent","to","4\/3",".","Both","arguments","must","be","Rational",".","The","numerator","defaults","to","0","and","the","denominator","defaults","to","1","so","that","Fraction","(","3",")","==","3","and","Fraction","(",")","==","0",".","Fractions","can","also","be","constructed","from",":","-","numeric","strings","similar","to","those","accepted","by","the","float","constructor","(","for","example",",","'-2.3","'","or","'1e10","'",")","-","strings","of","the","form","'123\/456'","-","float","and","Decimal","instances","-","other","Rational","instances","(","including","integers",")"]
docstr: 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(10000)
  Fraction(4321, 8765)
docstr_tok: ["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","(","10000",")","Fraction","(","4321",",","8765",")"]
code: def limit_denominator(self, max_denominator=1000000):
      """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(10000)
      Fraction(4321, 8765)
  
      """
      # Algorithm notes: For any real number x, define a *best upper
      # approximation* to x to be a rational number p/q such that:
      #
      #   (1) p/q >= x, and
      #   (2) if p/q > r/s >= x then s > q, for any rational r/s.
      #
      # Define *best lower approximation* similarly.  Then it can be
      # proved that a rational number is a best upper or lower
      # approximation to x if, and only if, it is a convergent or
      # semiconvergent of the (unique shortest) continued fraction
      # associated to x.
      #
      # To find a best rational approximation with denominator <= M,
      # we find the best upper and lower approximations with
      # denominator <= M and take whichever of these is closer to x.
      # In the event of a tie, the bound with smaller denominator is
      # chosen.  If both denominators are equal (which can happen
      # only when max_denominator == 1 and self is midway between
      # two integers) the lower bound---i.e., the floor of self, is
      # taken.
  
      if max_denominator < 1:
          raise ValueError("max_denominator should be at least 1")
      if self._denominator <= max_denominator:
          return Fraction(self)
  
      p0, q0, p1, q1 = 0, 1, 1, 0
      n, d = self._numerator, self._denominator
      while True:
          a = n // d
          q2 = q0 + a * q1
          if q2 > max_denominator:
              break
          p0, q0, p1, q1 = p1, q1, p0 + a * p1, q2
          n, d = d, n - a * d
  
      k = (max_denominator - q0) // q1
      bound1 = Fraction(p0 + k * p1, q0 + k * q1)
      bound2 = Fraction(p1, q1)
      if abs(bound2 - self) <= abs(bound1 - self):
          return bound2
      else:
          return bound1
  
imports: from decimal import Decimal
  import math
  import numbers
  import operator
  import re
  import sys
label_desc: Use image node_id 5 for calling the Fraction obj's underlying member method code with example usage: obj.limit_denominator(max_denominator) and returns: Fraction, bound2, bound1