楓 software:: 日常の備忘録

« CPU拡張命令とコア数 | メイン | 色温度の導出 »

2008年02月06日

日常の備忘録:: 最大公約数 - ユークリッドの互除法

Tweet    @jin1016をフォロー

最大公約数求める方法として、ユークリッドの互除法がある。
ユークリッドの互除法を見ると、ブレントが改善した方法が書いてある。
で、ブレント版を探したけど見つけられなかったので書いてみた。
以下のような感じ。

// 最大公約数 ( Greatest Common Divisor ) を求める // ユークリッドの互除法による実装 inline long gcd(long m, long n) {   while( n != 0 ) {     long temp = m % n;     m = n;     n = temp;   }   return m; } // 最大公約数 ( Greatest Common Divisor ) を求める // ユークリッドの互除法のブレント改良版 inline long gcd_brent(long m, long n) {   // まずは2の倍数を取り除く   long  c = 0;   while( ((m|n) & 1) == 0 ) {     m >>= 1;     n >>= 1;     c++;   }   // 2の倍数は取り除いたことから、偶数は最大公約数の共通因子とはなり得ないので   // 2で割って奇数にする   while( (m&1) == 0 ) m >>= 1;   while( (n&1) == 0 ) n >>= 1;   while( m != n ) {     if( m > n ) {       m-=n;       // 奇数同士の引き算は偶数になるので1度は必ず2で割れる       do { m >>= 1; } while( (m&1) == 0 );     } else {       n-=m;       // 奇数同士の引き算は偶数になるので1度は必ず2で割れる       do { n >>= 1; } while( (n&1) == 0 );     }   }   return n << c; }

10万までの組み合わせで確認したところ、ユークリッドの互除法と結果が一致することは確認した。
桁数が大きい場合は特に効果的と書いていたので、測ってみた。

・1～1万までの組み合わせ
Core 2 Duo E6750の結果
　ブレント版 4300 msec ぐらい ( 100 % )
　オリジナル 3150 msec ぐらい ( 73 % )
Athlon 64 X2 3800+ の結果
　ブレント版 5780 msec ぐらい ( 100 % )
　オリジナル 8140 msec ぐらい ( 141 % )

・100万～101万の組み合わせ
Core 2 Duo E6750の結果
　ブレント版 7500 msec ぐらい ( 100 % )
　オリジナル 3930 msec ぐらい ( 52 % )
Athlon 64 X2 3800+ の結果
　ブレント版 9730 msec ぐらい ( 100 % )
　オリジナル 9930 msec ぐらい ( 102 % )

Core 2 Duo の場合は、普通のユークリッド互除法のほうが両方速い。
剰余算が速いのか。
Athlon 64 の場合は、ブレント版の方が早いけど、桁数が大きくなるとかなり差が縮まっている。

なんか、普通のユークリッド互除法使ったほうがいいんじゃないの？
ブレント版は、ビット演算と足し算、引き算しか使ってないので、割り算とかが苦手なCPUだと効果的かも。
でも、それは今は昔か……

ブレント版は、もっと改善できるんだろうか？
ソースコードが悪いのかもしれない。

追記:
ブレント版は分岐予測に失敗する可能性が高くて遅いかもしれないとか。

投稿者 Takenori : 2008年02月06日 23:55

コメント

投稿者 通りすがり : 2009年03月23日 18:00

comments powered by Disqus