原です。

>正木です。

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

より速いようです。


ところで、Google で「開平法」を調べたら、風変わりなのが、、、

/* 2^30 <= x < 2^32 について root を計算する */
unsigned long isqrt(unsigned long x)
{
    unsigned long a, b;
    a = 143257 - 202860544/(1582+(x>>22));
    a = (a + x/a)/2;
    b = (a + x/a)/2;
    return a > b ? b : a;
}

出所はなんと [ruby-list:1313] で、書いたのは私なのですが、書いた
憶えが無い。(^^; どうやら痴呆らしい。そこには「証明がある」とか
「ニュートン法を1回に減らせる」とかありますが、どなたかその記事
を持っていないですかね。日経MIXらしいのですが、私は紛失してい
まいました。