近岡です。

>原です。
>
>>正木です。
>
>>static int
>>int_sqrt(i)
>>    int i;
>>{
>>    int j, k;
>>    if (i < 0) rb_raise(rb_eTypeError,"argument is negative");
>>    if (i == 0) return 0;
>>    j = int_sqrt(i >> 2) << 1;
>>    k = j | 1;
>>    if (k * k > i) return j;
>>    return k;
>>}
>
>すばらしい!ビットシフトだけで平方根を計算できるのですね。
>
>奥村氏の「アルゴリズム事典」(技評)に載っていた、ニュートン法
>による:
>
>int isqrt_o(x)
>     unsigned int x;
>{
>    unsigned int s, t;
>    if (x == 0) return 0;
>    s = 1;
>    t = x;
>    while (s < t) {
>        s <<= 1;
>        t >>= 1;
>    }
>    do {
>        t = s;
>        s = (x / s + s) >> 1;
>    } while (s < t);
>    return t;
>}
>
>より速いようです。
>

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)))ですね。(今一つ自信がありませんが)

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

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