isqrt.rb

class Integer
  def self.isqrt(n)
    return 0 if n == 0
    return 1 if n < 4
    shift = [n.bit_length / 4, 1].max
    x = Integer.isqrt(n >> (shift * 2))
    x = (x << (shift - 1)) + (n >> (shift + 1)) / x
    xx = x * x
    while xx > n
      xx -= 2 * x - 1
      x -= 1
      if xx > n
        p :unreachable?
      end
    end
    x
  end
end