近岡です。

通常のやり方よりも少しだけ高速なgcd()のアルゴリズムを紹介。
rubyの組込み関数の書き方がわからないので、擬似コードで失礼。

0----+----1----+----2----+----3----+----4----+----5----+----6
integer gcd(integer x, integer y)
{
    integer z,z2;
    if (x<0) x=-x; if (y<0) y=-y;
    while (y) {
        z=x%y; if ((z2=y-z)<z) z=z2;
        x=y; y=z;
    }
    return x;
}
  ｇｃｄ（ｘ、ｙ）＝ｇｃｄ（ｙ、ｘ％ｙ）
　　　　　　　　　または ｇｃｄ（ｙ、ｙ−ｘ％ｙ）
　を用いる。
　（ｘ％ｙ）と（ｙ−ｘ％ｙ）の小さい方を採用することにより、
　高速化をはかる。

0----+----1----+----2----+----3----+----4----+----5----+----6
integer gcd(integer x, integer y)
{
    integer z,c;
    if (x<0) x=-x; if (y<0) y=-y;

    if (!x) return y;
    c=0;
    while (!((x|y)&1)) { c++; x>>=1; y>>=1; }
    while (y) {
        while (!(y&1)) y>>=1; /* ｙの奇数因子を求める */
        z=x%y; if (z&1) z=y-z; /* ｚは偶数 */
        x=y; y=z;
    }
    return x<<c;
}
　今、自然数ｎに対して
　　　ｎ＝ｍ×２^ｅ（ｍは奇数）
　と表せたとき、ｍを「ｎの奇数因子odd(n)」と呼ぶことにする。

　上記プログラムは、まず、前半で
　　ｇｃｄ（ｘ、ｙ）＝odd（ｇｃｄ（ｘ／２^C、ｙ／２^C））×２^C
　　ただしｘ＝odd(ｘ)×２^C1、ｙ＝odd(ｙ)×２^C2、C=min(C1,C2)
　を用いる。

　後半では、ｙ'＝odd（ｙ）とおくと
　　odd（ｇｃｄ（ｘ，ｙ））＝ｇｃｄ（ｘ，odd（ｙ））
　　　＝ｇｃｄ（ｙ'，ｘ％ｙ'）または ｇｃｄ（ｙ'，ｙ'−ｘ％ｙ'）
　となることを用いる。

　  ｙ'は奇数なので、ｘ％ｙ'とｙ'−ｘ％ｙ'のいずれかは偶数。
　　ｘ％ｙ'が偶数のとき、odd（ｘ％ｙ'）≦ｙ'／２
　　ｙ'−ｘ％ｙ'が偶数のとき、odd（ｙ'−ｘ％ｙ'）≦ｙ'／２

 （参）V.C.Harrisの二進Euclid互除法アルゴリズムは、
　　ｇｃｄ（ｘ、ｙ）＝ｇｃｄ（odd(ｘ)、odd(ｙ)）×２^min(C1,C2)
　　　　　　    ただし、ｘ＝odd(ｘ)×２^C1、ｙ＝odd(ｙ)×２^C2
　　を用いる。

0----+----1----+----2----+----3----+----4----+----5----+----6
integer gcd(integer x, integer y)
{
    integer z,e;
    if (x<0) x=-x; if (y<0) y=-y;
    z=(x|y); e=z&(-z);
    while (y) {
        while (!(y&1)) y>>=1;
        z=x%y; if (z&1) z=y-z;
        x=y; y=z;
    }
    return x*e;
}
　
　負の整数を２の補数で表している場合、
　先のプログラムの
    while (!((x|y)&1)) { c++; x>>=1; y>>=1; }
 で求めた ｃ と、このプログラムの
    z=(x|y); e=z&(-z);
　で求めた ｅ の間には、ｅ＝２^ｃ という関係があることを用いる。
＃　多倍長の場合、実装の仕方によっては成り立たない。

0----+----1----+----2----+----3----+----4----+----5----+----6

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