Ruby初心者の近岡です。

>他にもおかしな所があったら指摘して下さい。
>
>---- gcd.c ----
>
>#include "ruby.h"
>#include "/usr/local/ruby-1.6.5/bignum.c"
>
>static VALUE
>gcd(self, m, n)
>    VALUE self;
>    VALUE m;
>    VALUE n;
>{
>    int i,j;
>    if(FIXNUM_P(n) && FIX2INT(n)==0) return m;
>    if(FIXNUM_P(m) && FIX2INT(m)==0) return n;
>    switch (TYPE(m)) {
>    case T_FIXNUM:
>      i = FIX2INT(m);
>      switch (TYPE(n)) {
>      case T_FIXNUM:
>	j = FIX2INT(n);
>	return gcd(self,n,INT2FIX(i%j));
>	break;
>      case T_BIGNUM:
>	return gcd(self,m,rb_big_modulo(n, m));
>	break;
>      }
>      break;
>    case T_BIGNUM:
>	return gcd(self,n,rb_big_modulo(m, n));
>    break;
>    }
>}

Ruby初心者なので良く判らないのですが、高速化をはかるならば、
再帰呼び出しのコストも問題になるのではないでしょうか。
私だったら(C言語では)次のようにします。
# というか、自前のアセンブラ用のライブラリをC言語に焼きなおしただけです。
# rubyの拡張ライブラリにする方法はまだ判らないので省略させてください。

/*
	最大公約数を求める関数
	V.C.Harrisの二進Euclid互除法アルゴリズムを採用。

	・a=奇数、b=b'*(2のべき)のとき gcd(a,b)=gcd(a,b')
	・a=a'<<c, b=b'<<d, a',b':奇数のとき gcd(a,b)=gcd(a',b')<<min(c,d)
        を利用
*/
unsigned int gcd(unsigned int AX, unsigned int BX)
{
	unsigned int CX=0, DI=0;

	if (!(AX & BX & 1)) { /*AX,BXのいずれかが偶数のとき*/
		if (!AX) return BX;
		if (!BX) return AX;
		while(!(AX & 1)) {AX>>=1; CX++;} /* AX = AX' * (2~CX) */
		while(!(BX & 1)) {BX>>=1; DI++;} /* BX = BX' * (2~DX) */
		if (DI<CX) CX=DI;
		/*このとき gcd(old_AX,old_BX) = gcd(new_AX,new_BX)<<CX */
	} /* end if */
	/* 以下 AX, BX は奇数 */
	if (AX<BX) {DI=AX; AX=BX; BX=DI;}
	for (;;) {
		DI=AX % BX;
		if (DI&1) { DI=AX-DI; } /* 奇数−奇数は偶数 */ 
		else { if (!DI) return AX<<CX; } /* 割り切れた時 */
		/* ここでDIは 0 以外の偶数で gcd(AX,BX)=gcd(BX,DI) */
		{ DI>>=1; } while (!(DI&1)); /* 奇数になるまで2で割り続ける */
		/* BXは奇数なので、gcd(BX,old_DI)=gcd(BX,DI) */
		AX=BX; BX=DI;
	} /* end for */
}

Rubyの拡張ライブラリでは多倍長の整数を扱わなければいけないから、
再帰的なアルゴリズムの方が実用的なのかな?

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