正木です。

[ruby-math:00942] で書いたことは帰納法をつかって意外と簡単に
証明できました。したがって

class Integer
  def isqrt_ini
    return 0 if self < 1
    return 1 if self < 4
    return 2 if self < 9
    return 3 if self < 16
    j = (bitlength - 1) >> 2
    x = (self >> (j << 1)).isqrt_ini
    ((x<<j) + (self>>j).div(x)) >> 1
  end

  def isqrt
    raise "argument is negative" if self < 0
    return 0 if self == 0
    return 1 if self < 4

    x = isqrt_ini
    x -= 1 if x * x > self
#   x -= 1 if x > div(x)
    x
  end
end

で良いことになります。