原です。

>近岡です。

>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_sub と名付けます。

>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;
>}

これを gcd_Harris と名付けます。

これは、今標準添付されている rationa.rb の Stien のアルゴリズムに
よく似ていますね。

  def gcd(n)
    m = self.abs
    n = n.abs

    return n if m == 0
    return m if n == 0

    b = 0
    while n[0] == 0 && m[0] == 0
      b += 1; n >>= 1; m >>= 1
    end
    m >>= 1 while m[0] == 0
    n >>= 1 while n[0] == 0
    while m != n
      m, n = n, m if n > m
      m -= n; m >>= 1 while m[0] == 0
    end
    m << b
  end

こっちを gcd_Stein と名付けますね。

>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;
>}

これを gcd_comp と名付けます。BIGNUM の内部構造は int と違うので、
速くはならないですが、演算はコンパチなので一応動きます。


で、結果は cygwin 上で PentiumIII 800M で次のようになりました。
数値は各セクションでの相対的な意味はありません。

* Fibonacci FIXNUM
                          user     system      total        real
gcd0                  0.801000   0.010000   0.811000 (  0.804000)
gcd_Stein             0.490000   0.000000   0.490000 (  0.500000)
gcd_sub               0.631000   0.000000   0.631000 (  0.632000)
gcd_Harris            0.531000   0.000000   0.531000 (  0.535000)
gcd_comp              0.531000   0.000000   0.531000 (  0.536000)

* Random FIXNUM
                          user     system      total        real
gcd0                  0.711000   0.010000   0.721000 (  0.744000)
gcd_Stein             0.601000   0.000000   0.601000 (  0.603000)
gcd_sub               0.681000   0.000000   0.681000 (  0.688000)
gcd_Harris            0.671000   0.000000   0.671000 (  0.671000)
gcd_comp              0.661000   0.000000   0.661000 (  0.662000)

* Fibonacci BIGNUM
                          user     system      total        real
gcd0                  0.811000   0.000000   0.811000 (  0.817000)
gcd_Stein             1.282000   0.000000   1.282000 (  1.281000)
gcd_sub               0.611000   0.000000   0.611000 (  0.609000)
gcd_Harris            0.761000   0.000000   0.761000 (  0.768000)
gcd_comp              0.751000   0.000000   0.751000 (  0.771000)

* Random BIGNUM
                          user     system      total        real
gcd0                  0.641000   0.000000   0.641000 (  0.645000)
gcd_Stein             2.073000   0.000000   2.073000 (  2.066000)
gcd_sub               0.651000   0.000000   0.651000 (  0.650000)
gcd_Harris            1.261000   0.000000   1.261000 (  1.283000)
gcd_comp              1.282000   0.000000   1.282000 (  1.292000)

ここで gcd0 とは普通のユークリッドの互除法の素朴な実装です。
結論から言えば int では gcd_Stein が速く、全般に gcd_sub 
が優秀みたいです。

大急ぎで作ったテストプログラムは

  http://blade.nagaokaut.ac.jp/~sinara/ruby/gcdchk/

です。皆さんのところではどうでしょうか。