原です。

>はじめまして。花谷と申します。
>
>rational.rbやmathn.rbの中にあるgcdなのですが、
>計算方法が複雑そうに見えるのですが、

mathn.rb のってのは、Integer#gcd2 ですね。これは因数分解
してから GCD を求めるもので、明らかに遅いです。多分、石
塚さんが理論的興味から作られたもので、その名前からしても、
普段ツールとして使われる事は念頭にないと思います。

rational.rb の Integer#gcd のアルゴリズムは、私もここで初
めて見たのですが、こんな方法があるのかと感動しました。調べ
てみると、これは J.Stein が 1961 年に発見したもので、数値
演算ライブラリやハードウェアにもよるが、互除法より2割ぐら
い速いそうです。(クヌース「準数値算法」)

実際にちょっと実験してみたところ、なんと互除法の方が速いみ
たいです。極端な場合、例えば N = 2**20 で N.gcd(N) をさせて
みると、単純な互除法の方が 10 倍ほど速くなりました。ただし
N = 2**20-1 ではほぼ同じでした。

これは Integer#% が十分速いことと、ビット演算は速いのだが、
スクリプト中の while が遅いことが原因ではないでしょうか。

因みに rational.rb の Integer#gcd2 は、花谷さんのと全く同じ
互除法アルゴリズムですが、花谷さんの方が2割ぐらい速いよう
です。その差は

ratinal.rb: void, a = a.divmod(b)
花谷      : m %= n

にあるので、多分前者が一時的に Array オブジェクトを生成する
のが無駄になっているのでしょう。

更に花谷さんのコードで、

       m, n = n, m

となっているところを

       tmp = m; m = n; n = tmp

としたほうが、また2割ぐらい早くなるようです。

結論を言うと、rational.rb の gcd は

   def gcd(n)
     m = abs
     while n != 0
       m %= n
       tmp = m; m = n; n = tmp
     end
     m.abs
   end

とすべきである。ついでに、mathn.rb にも同じコードを入れて
おいたらどうでしょうか?

ちょっと横道にそれますが、上の gcd の while ループの前に
tmp = nil を入れてもほとんど早さは変わりませんね。遅くな
るときもあります。Ruby はそういう最適化をするようになった
んでしょうか。

さらに要望ですが、Integer#gcd は、Ruby で数学を扱おうとす
ると、非常によく呼ばれる関数なので、是非組み込みにしてく
ださい。(その時は J.Stein のアルゴリズムの方が速い可能性
があります。)それによって幾つかのプログラムが劇的に早くな
る可能性があります。

ついでですが、早くクラス Rational を組み込みにしていただき
たいです。既に正木さんのコード([ruby-math:00639])とか、提
出されてますよね。懸案ではあるのですが。