parameters: (self, max_denominator=1000000)
docstring: 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)
docstring_summary: Closest Fraction to self with denominator at most max_denominator.
docstring_tokens: Closest Fraction to self with denominator at most max_denominator .
function: 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
function_tokens: def limit_denominator ( self , max_denominator = 1000000 ) : # 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