正木です。

Integer#isqrt ですが、Newton 法の初期値を更に Newton 法で求める次の
方法が今まで考えた中では一番早いみたいです。

n           Factorial[n].isqrt の計算時間 - Factorial[n] の計算時間
5000            0.06 sec
10000           0.45 sec
20000           1.75 sec
(i686, 1.6G)

-------
#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;
}

------