近岡です。

>Integer#isqrt ですが、Newton 法の初期値を更に Newton 法で求める次の
>方法が今まで考えた中では一番早いみたいです。
>
>-------
>#define rb_lshift(x,y)   rb_funcall(x,rb_intern("<<"),1,INT2FIX(y))
>#define rb_rshift(x,y)   rb_funcall(x,rb_intern(">>"),1,INT2FIX(y))
>#define rb_plus(x,y)     rb_funcall(x,'+',1,y)
>#define rb_greater(x,y)  rb_funcall(x,'>',1,y)
>
>static VALUE
>rb_int_sqrt(x)
>    VALUE x;
>{
>    int j;
>    VALUE y, z;
>    if (FIXNUM_P(x)) return INT2FIX(int_sqrt(FIX2INT(x))); 
>    if (!RBIGNUM(x)->sign)  rb_raise(rb_eRangeError,"argument is negative");
>    j = (FIX2INT(rb_bitlength(x)) - 1) >> 2;
>    z = rb_lshift(rb_plus(rb_int_sqrt(rb_rshift(x, j << 1)), Unity), j);
>    do {
>        y = z;
>	z = rb_rshift(rb_plus(y, rb_div(x,y)), 1);
>    } while(rb_greater(y, z));
>    return y;
>}
>

 平方根を求めるNewton法のうち、上記プログラムに
使われているものでは、ループ1回毎に有効桁数が約2倍になります。

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

# もしかしたら、上記プログラム中の j の値を
# 「やや小さめ」にしておく必要があるかもしれません。

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