正木です。

In  [ruby-math:00916]

|原です。


|組み込みのメソッドにするなら、可能なら再帰関数は使わない方が
|いいみたいです。

rb_gcd で再帰を使ったものと使わないもので速度を比べてみたことがあります。

再帰の回数が最も多くなる Fibonacci 数で

Fibonacci[n].gcd(Fibonacci[n-1])

を n = 80000 位まで計算させてみましたが有意の差はありませんでした。

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

int_gcd の場合、再帰回数は高々 50 回(32 bit) 乃至 100 回(64 bit)程度
なので 問題はないと考えています。
勿論、再帰関数を使わないものに書き換えることに反対しているわけでは
ありません。

|同じ値に対して繰り返し同じ関数(FIXNUM_P)を呼ばないようにすべき。

static VALUE
rb_gcd(x, y)
    VALUE x, y;
{
    VALUE z;

    if (FIXNUM_P(y)) {
        if (FIXNUM_P(x)) return INT2FIX(int_gcd(FIX2INT(x), FIX2INT(y)));
	if (FIX2INT(y) == 0) return rb_big_abs(x);
	return rb_gcd(y, rb_big_modulo(x, y));
    }
    y = rb_big_abs(y);
    while (!FIXNUM_P(y)) {
        z = rb_big_modulo(x, y);
	x = y;
	y = z;
    }
    return rb_gcd(x, y);
}

に訂正します。

|power は
|
|     if (m == 0) return 1;
|     n = int_pow(i, m/2);
|     return (i & 1) ? (n * n * i) : (n * n);
|
|みたいなのが速いです。bignum.c の該当部分は

これも、充分早いものをさらに早くしてもしょうがない、と思って出来るだけ
単純なものにしていますが、早くて困ることもないので

static int
int_pow(i, m)
    int i, m;
{
    int j;
    if (m == 0) return 1;
    j = int_pow(i, m >> 1);
    return (m & 1) ?  (j * j * i) : (j * j);  
}

に変更します。

|TypeError ではなくて RangeError かな。

他のもすべて直しておきます。

|この話、今回はなんとかまとめてしまいたいですね。

同感です。