近岡です。

>>2進数での開平法は、2分法で平方根を求めることと同じ。
>>ループの回数は求める桁数に比例しますから、
>>整数iの平方根の整数部分を求める場合の
>>実行時間のオーダーはO(log(i))ですね。
>>
>>ニュートン法で平方根を求める上記の方法では、
>>    while (s < t) { s <<= 1; t >>= 1; }
>>
>>    do { t = s; s = (x / s + s) >> 1; } while (s < t);
>>の2つのループがあります。
>>実行時間のほとんどをしめると思われる2つ目のループの回数は
>>求める桁数の対数にほぼ比例しますから、
>>整数iの平方根の整数部分を求める場合のオーダーは、
>>O(log(log(i)))ですね。(今一つ自信がありませんが)
>
>前半と後半を合わせると
>
> O(log(i)) + O(log(log(i))) = O(log(i))
>
>となるのでは。
>

おっしゃられる通りです (^ ^;

さらに、厳密なことを言えば、ループ1回あたりの実行時間も
もちろん考慮しなければいけませんね。これがさっぱり判りません。

rubyの多倍長演算ではどのような実装がなされているのか知りませんが、
以下では高速乗算法などを使わないもっとも素朴な実装法であると
仮定してみます。
# 高速乗算法のオーダーを見積りが苦手なもので … (^ ^;
そうすると、
[ruby-math:00907]のプログラムではオーダーが
	O(log(i)^2×log(i))=O(log(i)^3)、
ニュートン法ではオーダーが
	O(log(i)×log(i))+O(log(i)^2×log(log(i)))=O(log(i)^2×log(log(i)))
になります。

以下、その根拠を書き並べて見ます。
こういったことは、苦手なので間違いがあればご指摘下さい。
# できたらrubyの多倍長演算でどのような実装が
# されているかを考慮したものならば嬉しいです。

ニュートン法の後半のループの中で一番時間が取られるのが割り算です。
素朴な実装法では桁数の2乗に比例すると考えて良いでしょう。
(オーダーはループ1回当たりO(log(i)^2))

ニュートン法の前半のループでは、ビットずらしだけです。
1回当たりの実行時間は桁数に比例すると考えて良いでしょう。
さらに、正木さんのbitsizeをもちいれば、
前半のループは不要になります。

[ruby-math:00907]のプログラムでは、
再帰呼び出しによるループの中に、整数を2乗する部分があります。
もっとも”素朴な”実装法では、この実行時間は桁数の2乗に
比例すると考えられます。(オーダーはO(log(i)^2))

# 整数の2乗の部分をビットずらしと加法のみで実現すると、
# オーダーがO(log(i))で実現できるのでは???
#
# 例えば、rb_int_sqrt(x)の中の((n<<1)+1)の2乗を求めている
#>    else {
#>        n = rb_big_lshift(y,INT2FIX(1));
#>	m = rb_big_or(n,INT2FIX(1));
#>	m2 = rb_big_mul(m,m);
#>    }
# の部分は、すでに前回のループで n*n を求めているのですから、
# これを変数 n2 として保存してあれば、
#   m2=((n2+n)<<2) + 1
# と、加法2回とビットずらし1回ですむのでは???

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