【C++】スタインのアルゴリズム（バイナリGCD）で最大公約数を効率的に求める方法

スタインのアルゴリズム（Stein's Algorithm）はバイナリGCDアルゴリズムとも呼ばれ、2つの非負整数の最大公約数（GCD：Greatest Common Divisor）を求めるための手法です。従来のユークリッドの互除法が除算を繰り返すのに対し、このアルゴリズムはビットシフト・比較・減算だけで計算を進められる点が最大の特徴です。コンピュータ上では除算よりもシフト演算や減算の方が高速に処理できるため、実行速度の面で大きく有利になります。
なお、両方の引数が0の場合、最大公約数は0と定義されます（gcd(0, 0) = 0）。以下にGCD(a, b)を求める手順を示します。

アルゴリズムの手順

START
    Step-1: aとbがどちらも0の場合、gcd(0, 0) = 0 となる。
    Step-2: すべての整数は0を割り切るため、gcd(a, 0) = a、gcd(0, b) = b となる。
    Step-3: aとbがどちらも偶数の場合、2は共通の約数なので gcd(a, b) = 2*gcd(a/2, b/2) となる。2を掛ける操作はビットシフト演算子で実現できる。
    Step-4: aが偶数でbが奇数の場合、2は共通の約数ではないため gcd(a, b) = gcd(a/2, b) となる。同様に、aが奇数でbが偶数の場合は gcd(a, b) = gcd(a, b/2) となる。
    Step-5: aとbがどちらも奇数の場合、2つの奇数の差は必ず偶数になることを利用し、gcd(a, b) = gcd(|a-b|/2, b) となる。
    Step-6: a = b または a = 0 になるまで、Step-3～Step-5 を繰り返す。
END

C++による実装例

上記のアルゴリズムに基づき、2つの整数のGCDを計算するC++コードは次のように記述できます。

#include <bits/stdc++.h>
using namespace std;

int funGCD(int x, int y){
    if (x == 0)
        return y;
    if (y == 0)
        return x;
    int k;
    // 2つの数に共通する2の因子を取り除く
    for (k = 0; ((x | y) & 1) == 0; ++k){
        x >>= 1;
        y >>= 1;
    }
    // xから残りの2の因子を取り除き、奇数にする
    while ((x & 1) == 0)
        x >>= 1;
    do {
        // yから2の因子を取り除き、奇数にする
        while ((y & 1) == 0)
            y >>= 1;
        if (x > y)
            swap(x, y); // 常に x <= y となるように入れ替え
        y = (y - x);   // 2つの奇数の差は必ず偶数になる
    } while (y != 0);
    return x << k;     // 取り除いた共通因子の分だけ掛け戻す
}

int main(){
    int a = 24, b = 18;
    printf("Calculated GCD of numbers (24,18) is= %d\n", funGCD(a, b));
    return 0;
}

実行結果

このプログラムを実行すると、スタインのアルゴリズムによって、与えられた2つの数24と18の最大公約数「6」が正しく計算されます。

Calculated GCD of numbers (24,18) is= 6

スタインのアルゴリズムのメリット

• 除算が不要：ビットシフトと減算だけで処理できるため、除算命令が低速な環境（組み込みシステムなど）でも高速に動作します。
• 反復回数が少ない：各ステップで数値が半減していくため、ループ回数はおおむね O(log max(a, b)) 回に収まります。
• 実装がシンプル：条件分岐とシフト・減算の組み合わせだけで書けるため、コードが読みやすく保守もしやすくなります。