バイナリユークリッドの互除法の実装

投稿日：2022/12/17 更新日:2023/03/20

数学

バイナリユークリッドの互除法とは

ユークリッドの互除法では剰余演算%を使いますが、これは他の演算に比べ重たいです。

そこで、コンピュータが２進数で処理していることを利用して、シフト演算やビット演算で高速化する手法です。

アルゴリズム

非負整数 $a, b$ の最大公約数を求める関数gcdです。

$a = 0$ の場合 $b$ を返す。
$a$ も $b$ も偶数の場合 → $2*\gcd(a/2, b/2)$ を返す。
$a$ のみ偶数の場合 → $\gcd(a/2, b)$ を返す。
$b$ のみ偶数の場合 → $\gcd(a, b/2)$ を返す。
$a$ も $b$ も奇数の場合 → $\gcd(|a-b|/2, \min(a, b))$ を返す。

$a > b$ の時、 $\gcd(a, b) = \gcd(a-b, b)$ が成り立つことを利用しています。

実装

偶奇の判定は&1で、2で割るのは>>1で処理しています。

int gcd(int a, int b){
    if(a == 0)return b;
    if((a&1) == 0 && (b&1) == 0){
        return 2 * gcd(a>>1, b>>1);
    }
    if((a&1) == 0){
        return gcd(a>>1, b);
    }
    if((b&1) == 0){
        return gcd(a, b>>1);
    }
    return gcd(abs(a-b)>>1, min(a, b));
}

非再帰化

template<typename T>
T gcd(T a, T b){
    if(a == 0)return b;
    if(b == 0)return a;

    T s = a;
    T t = b;
    int cnt = 0;
    while(a != 0){
        if(s&1 == 0 && t&1 == 0){
            cnt++;
            a = s>>1;
            b = t>>1;
        }else if(s&1 == 0){
            a = s>>1;
        }else if(t&1 == 0){
            b = t>>1;
        }else{
            a = abs(s-t)>>1;
            b = min(s, t);
        }
    }
    return b << cnt;
}