原です。

>いけがみです。
>
>原さん:
> > 実際にちょっと実験してみたところ、なんと互除法の方が速いみ
> > たいです。極端な場合、例えば N = 2**20 で N.gcd(N) をさせて
> > みると、単純な互除法の方が 10 倍ほど速くなりました。ただし
> > N = 2**20-1 ではほぼ同じでした。
>
> > これは Integer#% が十分速いことと、ビット演算は速いのだが、
> > スクリプト中の while が遅いことが原因ではないでしょうか。
>
>あてずっぽなので、信用してほしくないのですが、
>現在の Bignum の bit 演算および参照を繰り返すことは高価な操作ではないかなあ
>と思います。

今読み返したら、私の N.gcd(N) のテストってのは、極端すぎてあまり
いい例ではなかったですね。一般の N.gcd(M) で、N, M が Fixnum の範
囲でも数割から倍の違いがあるみたいです。

#私の文章って「速い」と「早い」がランダムに散らばってるなあ。