正木です。

|近岡です。
|2進数での開平法は、2分法で平方根を求めることと同じ。
|ループの回数は求める桁数に比例しますから、
|整数iの平方根の整数部分を求める場合の
|実行時間のオーダーはO(log(i))ですね。

|ニュートン法で平方根を求める上記の方法では、

|整数iの平方根の整数部分を求める場合のオーダーは、
|O(log(log(i)))ですね。(今一つ自信がありませんが)

|両者のオーダーを比べた場合は後者の方が有利に見えますが、
|整数iが大きくないときは逆転現象が起きるのでしょうね。


Newton 法との比較は一応した積もりだったのですが、改めて
調べ直して見ました。
下記のような Newton 法 によるものと [ruby-math:00907] のもの
とで Factorial[n].isqrt の計算時間を比べてみました。
結果は 次の通りです。

n        Newton 法    2進数開平法    Factorial[n].bitsize
1000     0.07 sec          1.11 sec       8530
1500     0.11 sec     4.28 sec       13669
2000     0.14 sec          11.3 sec       19053
2500     0.29 sec          24.09 sec      24620
10000    4.61 sec          ????           118459

(Fact[10000].bitsize #=> 118459  1.43 sec)

大きな数に対しては Newton 法の方が圧倒的に早いことがわかりました。
[ruby-math:00907] の rb_int_sqrt の code は撤回して以下のものに
変更します。


---------
#define Zero             INT2FIX(0)
#define Unity            INT2FIX(1)
#define rb_lshift(x,y)   rb_funcall(x,rb_intern("<<"),1,y)
#define rb_rshift(x,y)   rb_funcall(x,rb_intern(">>"),1,y)
#define rb_plus(x,y)     rb_funcall(x,'+',1,y)
#define rb_div(x,y)      rb_funcall(x,rb_intern("div"),1,y)
#define rb_greater(x,y)  rb_funcall(x,'>',1,y)


static VALUE
rb_int_sqrt(x)
    VALUE x;
{
    VALUE y, z;
    if (FIXNUM_P(x)) return INT2FIX(int_sqrt(FIX2INT(x))); 
    if (!RBIGNUM(x)->sign)  rb_raise(rb_eTypeError,"argument is negative");
    z = rb_lshift(Unity, rb_rshift(rb_plus(rb_bitsize(x), Unity), Unity));
    do {
        y = z;
	z = rb_rshift(rb_plus(y, rb_div(x,y)), Unity);
    } while(rb_greater(y, z));
    return y;
}
---------