いけがみです。

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

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

あてずっぽなので、信用してほしくないのですが、
現在の Bignum の bit 演算および参照を繰り返すことは高価な操作ではないかなあ
と思います。

Bignum は安定して動くようになったら、次は高速に動いてほしいです。:)
--
池上 大介
Daisuke IKEGAMI <daisu-ik / is.aist-nara.ac.jp>
奈良先端科学技術大学院大学 情報科学研究科
情報処理学専攻 情報基礎学講座 関研究室