近岡です。

>| ですから、
>|おおもとのrb_int_sqrt()内では、do 〜 while ループは欠かせませんが、
>|再帰呼び出しされている側のrb_int_sqrt()内では、do 〜 while ループを
>|削除して、単純に、
>|  return rb_rshift(rb_plus(z, rb_div(x,z)), 1);
>|とすることが可能だと思います。
>
>下記の script(ついでなので Integer#iroot もつけておきます)
>で試してみました。
>一番時間がかかるのは最後の loop なので、その回数がおなじなら
>isqrtC が早くなりますが、回数が増えた場合はかえって遅くなります。

それは予想外でした。無駄骨を折らせて失礼しました。

ただ、気になるのは、[ruby-math:00933]では、

>    j = (FIX2INT(rb_bitlength(x)) - 1) >> 2;

となっているところが、[ruby-math:00936]のisqrt_iniでは

>    j = (bitlength + 1) >> 2

となっているところです。
そこで、小手先の手段で速さを追い求めてみました。

再帰呼び出しされる側で、ニュートン法の式を1回ですます場合、
jは、小さめにとった方が良いので、以下のプログラムでは、
     j = (bitlength - 1) >> 2
としています。それ以外にも、若干いじっているところがあります。

  def isqrtD_ini
    return 0 if self == 0
    if self < 16 
        j = bitlength >> 1
        x = ((1<<j)+(self>>j))>>1
        while x > y=div(x)
          x = (x + y)>>1
        end
        x + 1  # 大き目の値を返す
    else
      j = (bitlength - 1) >> 2
      x = ((self >> (j << 1)).isqrtD_ini)
      ((x<<j) + (self>>j).div(x)) >> 1
    end
  end
 
  def isqrtD
    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)).isqrtD_ini
    x= ((x<<j) + (self>>j).div(x))>>1
    while x > y = div(x)
      x = (x + y) >> 1
    end
    x
  end

実験してみると、大きな自然数に対しては効果がありました。

# 実行時間で比較したのではなく、
# 割り算の回数をカウントしました。
#
# 手元の環境では 1000!を計算するとメモリが不足するので
# フィボナッチ数列で実験しました。
#
# 最後のループの回数を1000桁程度の自然数の場合に比較して見ると、
# isqrtD の方がisqrtよりも多くなる割合は約10%ほど。
# 約9割の確率で、ほんの少しだけ速く、
# 約1割の確率で、遅くなると考えて良いのではないでしょうか。
#
# もっとも、自然数が約15ビット以内でおさまる場合、
# ほぼ100%の割合で、isqrtD の方が遅くなります。

0----+----1----+----2----+----3----+----4----+----5----+----6
近岡 宣吉  Chikaoka, Nobuyoshi
富山県立高岡西高等学校(数楽科)
 E-mail : chikaoka-nobuyoshi / tym.ed.jp