原です。

>正木です。
>
>[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

やっぱり bitlength より ilog2(仮称)の方が使う頻度が
高そうだなあ。

>  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

計算後の桁数が半分になったとしても、div はとても重いと思うので、
x * x > self の方でいいんじゃないかな。