正木です。

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
    while x > y = div(x)
      x = (x + y) >> 1
    end
    x
  end
end

とします。
while 文に入る前の x の条件は x >= isqrt で、これは Newton 法を
１回適用すれば自動的に満たされるので isqrt_ini の６行目に + 1 を
付けていません。

このとき

n.isqrt_ini == n.isqrt || n.isqrt_ini == n.isqrt + 1

が成り立ちそうな気がします。(上記の + 1 をつけた場合は反例があります)

n <= 100000
n = m! (m < 2000)
n = m!! (m < 2000)
n = 2**m -1 (m < 5000)
n = 2**(2**m -1)-1 (m < 20)

で確認しています。

もしもこれが理論的に証明できれば、最後の loop は

    x -= 1 if x > div(x)

あるいはどちらが早いか分かりませんが

    x -= 1 if x * x > self

と書けることになります。

仮りにそうでなくても、isqrt の loop は高々１回と思ってほぼ間違いは
無さそうです。