近岡です。

通常のやり方よりも少しだけ高速な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;
}
  gcd(x、y)=gcd(y、x%y)
         または gcd(y、y−x%y)
 を用いる。
 (x%y)と(y−x%y)の小さい方を採用することにより、
 高速化をはかる。

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; /* yの奇数因子を求める */
        z=x%y; if (z&1) z=y-z; /* zは偶数 */
        x=y; y=z;
    }
    return x<<c;
}
 今、自然数nに対して
   n=m×2^e(mは奇数)
 と表せたとき、mを「nの奇数因子odd(n)」と呼ぶことにする。

 上記プログラムは、まず、前半で
  gcd(x、y)=odd(gcd(x/2^C、y/2^C))×2^C
  ただしx=odd(x)×2^C1、y=odd(y)×2^C2、C=min(C1,C2)
 を用いる。

 後半では、y'=odd(y)とおくと
  odd(gcd(x,y))=gcd(x,odd(y))
   =gcd(y',x%y')または gcd(y',y'−x%y')
 となることを用いる。

   y'は奇数なので、x%y'とy'−x%y'のいずれかは偶数。
  x%y'が偶数のとき、odd(x%y')≦y'/2
  y'−x%y'が偶数のとき、odd(y'−x%y')≦y'/2

 (参)V.C.Harrisの二進Euclid互除法アルゴリズムは、
  gcd(x、y)=gcd(odd(x)、odd(y))×2^min(C1,C2)
          ただし、x=odd(x)×2^C1、y=odd(y)×2^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;
}
 
 負の整数を2の補数で表している場合、
 先のプログラムの
    while (!((x|y)&1)) { c++; x>>=1; y>>=1; }
 で求めた c と、このプログラムの
    z=(x|y); e=z&(-z);
 で求めた e の間には、e=2^c という関係があることを用いる。
# 多倍長の場合、実装の仕方によっては成り立たない。

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

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