parameters: (x, M, L = 8)
return_statement: return _div_nearest(w*y, M)
docstring: Integer approximation to M*log(x/M), with absolute error boundable
      in terms only of x/M.
  
      Given positive integers x and M, return an integer approximation to
      M * log(x/M).  For L = 8 and 0.1 <= x/M <= 10 the difference
      between the approximation and the exact result is at most 22.  For
      L = 8 and 1.0 <= x/M <= 10.0 the difference is at most 15.  In
      both cases these are upper bounds on the error; it will usually be
      much smaller.
docstring_summary: Integer approximation to M*log(x/M), with absolute error boundable
      in terms only of x/M.
docstring_tokens: Integer approximation to M * log ( x / M ) with absolute error boundable in terms only of x / M .
function: def _ilog(x, M, L = 8):
      """Integer approximation to M*log(x/M), with absolute error boundable
      in terms only of x/M.
  
      Given positive integers x and M, return an integer approximation to
      M * log(x/M).  For L = 8 and 0.1 <= x/M <= 10 the difference
      between the approximation and the exact result is at most 22.  For
      L = 8 and 1.0 <= x/M <= 10.0 the difference is at most 15.  In
      both cases these are upper bounds on the error; it will usually be
      much smaller."""
  
      # The basic algorithm is the following: let log1p be the function
      # log1p(x) = log(1+x).  Then log(x/M) = log1p((x-M)/M).  We use
      # the reduction
      #
      #    log1p(y) = 2*log1p(y/(1+sqrt(1+y)))
      #
      # repeatedly until the argument to log1p is small (< 2**-L in
      # absolute value).  For small y we can use the Taylor series
      # expansion
      #
      #    log1p(y) ~ y - y**2/2 + y**3/3 - ... - (-y)**T/T
      #
      # truncating at T such that y**T is small enough.  The whole
      # computation is carried out in a form of fixed-point arithmetic,
      # with a real number z being represented by an integer
      # approximation to z*M.  To avoid loss of precision, the y below
      # is actually an integer approximation to 2**R*y*M, where R is the
      # number of reductions performed so far.
  
      y = x-M
      # argument reduction; R = number of reductions performed
      R = 0
      while (R <= L and long(abs(y)) << L-R >= M or
             R > L and abs(y) >> R-L >= M):
          y = _div_nearest(long(M*y) << 1,
                           M + _sqrt_nearest(M*(M+_rshift_nearest(y, R)), M))
          R += 1
  
      # Taylor series with T terms
      T = -int(-10*len(str(M))//(3*L))
      yshift = _rshift_nearest(y, R)
      w = _div_nearest(M, T)
      for k in xrange(T-1, 0, -1):
          w = _div_nearest(M, k) - _div_nearest(yshift*w, M)
  
      return _div_nearest(w*y, M)
function_tokens: def _ilog ( x , M , L = 8 ) : # The basic algorithm is the following: let log1p be the function # log1p(x) = log(1+x).  Then log(x/M) = log1p((x-M)/M).  We use # the reduction # #    log1p(y) = 2*log1p(y/(1+sqrt(1+y))) # # repeatedly until the argument to log1p is small (< 2**-L in # absolute value).  For small y we can use the Taylor series # expansion # #    log1p(y) ~ y - y**2/2 + y**3/3 - ... - (-y)**T/T # # truncating at T such that y**T is small enough.  The whole # computation is carried out in a form of fixed-point arithmetic, # with a real number z being represented by an integer # approximation to z*M.  To avoid loss of precision, the y below # is actually an integer approximation to 2**R*y*M, where R is the # number of reductions performed so far. y = x - M # argument reduction; R = number of reductions performed R = 0 while ( R <= L and long ( abs ( y ) ) << L - R >= M or R > L and abs ( y ) >> R - L >= M ) : y = _div_nearest ( long ( M * y ) << 1 , M + _sqrt_nearest ( M * ( M + _rshift_nearest ( y , R ) ) , M ) ) R += 1 # Taylor series with T terms T = - int ( - 10 * len ( str ( M ) ) // ( 3 * L ) ) yshift = _rshift_nearest ( y , R ) w = _div_nearest ( M , T ) for k in xrange ( T - 1 , 0 , - 1 ) : w = _div_nearest ( M , k ) - _div_nearest ( yshift * w , M ) return _div_nearest ( w * y , M )