GCDは最大公約数。計算方法としてはユークリッドの互除法が有名です。
別なやり方もあって、例えばBinary GCDアルゴリズムなんかおもしろいと思うのですが、なぜか日本語での解説が少ない……。
なら自分で書いて残しておこうかと思ったり。
Binary GCDアルゴリズムでは次の3つの定理が基本になります。
- nとmが両方とも偶数なら、GCD(n, m) = 2*GCD(n/2, m/2)
- nが偶数でmが奇数なら、GCD(n, m) = GCD(n/2, m)
同じようにnが奇数でmが偶数なら、GCD(n, m) = GCD(n, m/2) - nとmが共に奇数でn > mなら、GCD(n, m) = GCD(n - m, m)
同じようにnとmが共に奇数でn < mなら、GCD(n, m) = GCD(n, m - n)
証明は略。(面倒……
アルゴリズムの本体を文章に直して書くと次の通り。
- nとmのどちらかが奇数になるまで2で割る(回数kを記録しておく)
- 残りの側も奇数になるまで2で割る(定理2)
- 以下、n = mになるまでくり返し
- n > mのとき、
- nにn - mを代入(定理3)
- nが奇数になるまで2で割る(定理2)
- n < mのとき、
- mにm - nを代入(定理3)
- mが奇数になるまで2で割る(定理2)
- 最後にnに2kを掛けて終わり!(定理1)
互除法と比べると、特に任意精度整数(BigInteger)で除算を避けられる*1のがメリットらしいです。(それなら、CPUで除算できる普通の整数型では大差ないのかも?)
Javaで書くとこうなります。ちょっとトリッキーな部分あり。
public static int gcd(int n, int m) { // 負の数はダメ if (n < 0 || m < 0) throw new ArithmeticException(); // GCD(0, m) = m; GCD(0, 0) = 0 // GCD(n, 0) = n if (n == 0 || m == 0) return n + m; // ここから int k = Integer.numberOfTrailingZeros(n | m); n >>= Integer.numberOfTrailingZeros(n); m >>= Integer.numberOfTrailingZeros(m); while (n != m) { if (n > m) { n -= m; n >>= Integer.numberOfTrailingZeros(n); } else { m -= n; m >>= Integer.numberOfTrailingZeros(m); } } return n << k; }
(最初から最後までnumberOfTrailingZerosだらけ!)
*1:2で割るのはシフト演算で済むから。