正木です。

In [ruby-math:00935]
|近岡です。

| ですから、
|おおもとのrb_int_sqrt()内では、do 〜 while ループは欠かせませんが、
|再帰呼び出しされている側のrb_int_sqrt()内では、do 〜 while ループを
|削除して、単純に、
|  return rb_rshift(rb_plus(z, rb_div(x,z)), 1);
|とすることが可能だと思います。

下記の script(ついでなので Integer#iroot もつけておきます)
で試してみました。

n            isqrt         isqrtC
10000        0.42 sec      0.52 sec
11000        0.4           0.49
12000        0.49          0.59
13000        1.04          0.93
14000        0.65          0.81
15000        0.72          0.89
16000        0.85          1.08
17000        1.01          1.27
18000        1.79          1.6
19000        1.28          1.61
20000        1.61          2.0

一番時間がかかるのは最後の loop なので、その回数がおなじなら
isqrtC が早くなりますが、回数が増えた場合はかえって遅くなります。



------
class Integer
  def isqrt
    raise "argument is negative" if self < 0
    return 0 if self == 0
    return 1 if self < 4
    j = (bitlength + 1) >> 2
    x = ((self >> (j << 1)).isqrt + 1) << j
    while x > y = div(x)
      x = (x + y) >> 1
    end
    x
  end

  def irootB(m)
    raise "argument is negative" if self < 0
    return 0 if self == 0
    n = (self >> m).irootB(m) << 1
    n1 = n | 1
    (n1 ** m > self)? n : n1
  end

  def iroot(m)
    return irootB(m) if self < 2 ** m
    j = (bitlength + 1).div(m)
    x = ((self >> (j*m)).iroot(m) + 1) << j
    while x > y = div(x ** (m - 1))
      x += (y - x).div(m)
    end
    x
  end

  def isqrt_ini
    return 0 if self == 0
    return 1 if self < 4
    j = (bitlength + 1) >> 2
    x = ((self >> (j << 1)).isqrt_ini + 1) << j
    (x + div(x)) >> 1
  end

  def isqrtC
    raise "argument is negative" if self < 0
    return 0 if self == 0
    return 1 if self < 4
    x = isqrt_ini + 1
    while x > y = div(x)
      x = (x + y) >> 1
    end
    x
  end
end

-----