ぎるばーとのノート

もっともっと遠くへ行きたい 空が広く見える場所まで

Binary GCD

 GCDは最大公約数。計算方法としてはユークリッドの互除法が有名です。
 別なやり方もあって、例えばBinary GCDアルゴリズムなんかおもしろいと思うのですが、なぜか日本語での解説が少ない……。
 なら自分で書いて残しておこうかと思ったり。

 Binary GCDアルゴリズムでは次の3つの定理が基本になります。

  1. nとmが両方とも偶数なら、GCD(n, m) = 2*GCD(n/2, m/2)
  2. nが偶数でmが奇数なら、GCD(n, m) = GCD(n/2, m)
    同じようにnが奇数でmが偶数なら、GCD(n, m) = GCD(n, m/2)
  3. nとmが共に奇数でn > mなら、GCD(n, m) = GCD(n - m, m)
    同じようにnとmが共に奇数でn < mなら、GCD(n, m) = GCD(n, m - n)

 証明は略。(面倒……

 アルゴリズムの本体を文章に直して書くと次の通り。

  1. nとmのどちらかが奇数になるまで2で割る(回数kを記録しておく)
  2. 残りの側も奇数になるまで2で割る(定理2)
  3. 以下、n = mになるまでくり返し
    • n > mのとき、
    1. nにn - mを代入(定理3)
    2. nが奇数になるまで2で割る(定理2)
    • n < mのとき、
    1. mにm - nを代入(定理3)
    2. mが奇数になるまで2で割る(定理2)
  4. 最後に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で割るのはシフト演算で済むから。