原です。

>正木です。

>|組み込みのメソッドにするなら、可能なら再帰関数は使わない方が
>|いいみたいです。
>
>rb_gcd で再帰を使ったものと使わないもので速度を比べてみたことがあります。
>
>再帰の回数が最も多くなる Fibonacci 数で
>
>Fibonacci[n].gcd(Fibonacci[n-1])
>
>を n = 80000 位まで計算させてみましたが有意の差はありませんでした。

あれー!そうですか。実際にやってみないと分からないものですね。

>ただ再帰回数が有界でない再帰関数を使うのは SystemStackError の可能性
>があって望ましくないので、[ruby-math:00911] での rb_gcd は再帰的には
>なっていません。

そうですね。


>|power は
>|
>|     if (m == 0) return 1;
>|     n = int_pow(i, m/2);
>|     return (i & 1) ? (n * n * i) : (n * n);
>|
>|みたいなのが速いです。bignum.c の該当部分は
>
>これも、充分早いものをさらに早くしてもしょうがない、と思って出来るだけ
>単純なものにしていますが、

いや、これは O(n) と O(lon(n)) の差だから大きいんじゃないでしょう
かね。実際 power がどうも遅いプログラムがあって、それを2分割法に
なおしたら、ずいぶん速くなりましたよ。


それから、ビットサイズですけど、私の最近の研究:-)では、

static VALUE
bitsize(x)
    VALUE x;
{
    long len, v, i;
    BDIGIT u;

    switch (TYPE(x)) {
    case T_BIGNUM:
        len = RBIGNUM(x)->len;
        u = BDIGITS(x)[len - 1];
        if (u == 0) return INT2FIX(1);
        for (i = BITSPERDIG - 1; (((BDIGIT)1 << i) & u) == 0; i--) ;
        return LONG2FIX((len - 1) * BITSPERDIG + i + 1);
    case T_FIXNUM:
        v = FIX2INT(x);
        if (v == 0) return INT2FIX(1);
        for (i = SIZEOF_INT * CHAR_BIT - 2; ((1 << i) & v) == 0; i--) ;
        return LONG2FIX(i + 1);
    default:
        rb_bug;
    }
}

で行けそうな気がしますが、どうでしょうか。

でも、これは松本さんが書いちゃうのが早いかな。