けいじゅ@日本ラショナルソフトウェアです.

In [ruby-math :00663 ] the message: "[ruby-math:00663] Re: gcd in
rational.rb ", on Apr/04 13:18(JST) Shin-ichiro HARA writes:

>原です。

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

ために作ってみただけですね. そんなものをmathnの先頭においておくのは何な
んですね.

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

たぶん, [ruby-dev:5415]で稲葉さんが出していたものを採用したみたいです.

>実際にちょっと実験してみたところ、なんと互除法の方が速いみ
>たいです。極端な場合、例えば 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 にも同じコードを入れて
>おいたらどうでしょうか?

了解しました. rational.rb(のみに)入れておきます. J.Steinのほうはgcd2にさ
せて頂きます(^^;;;

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

ですね. これはRationalクラスと独立のものなんで, 入れて頂きたいですね. す
でに, 幾つかC版も出ていますし.

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

私も希望はしているんですが...

__
..............................石塚 圭樹@日本ラショナルソフトウェア...
----------------------------------->> e-mail: keiju / rational.com <<---