code: def improved_i_sqrt(n):
      
      assert n >= 0
      if n == 0:
          return 0
      i = n.bit_length() >> 1    # i = floor( (1 + floor(log_2(n))) / 2 )
      m = 1 << i    # m = 2^i
      #
      # Fact: (2^(i + 1))^2 > n, so m has at least as many bits
      # as the floor of the square root of n.
      #
      # Proof: (2^(i+1))^2 = 2^(2i + 2) >= 2^(floor(log_2(n)) + 2)
      # >= 2^(ceil(log_2(n) + 1) >= 2^(log_2(n) + 1) > 2^(log_2(n)) = n. QED.
      #
      while (m << i) > n: # (m<<i) = m*(2^i) = m*m
          m >>= 1
          i -= 1
      d = n - (m << i) # d = n-m^2
      for k in range(i-1, -1, -1):
          j = 1 << k
          new_diff = d - (((m<<1) | j) << k) # n-(m+2^k)^2 = n-m^2-2*m*2^k-2^(2k)
          if new_diff >= 0:
              d = new_diff
              m |= j
      return m
docs: taken from
      http://stackoverflow.com/questions/15390807/integer-square-root-in-python
      Thanks, mathmandan