こんにちは、テック好きの皆さん！今日は、ちょっと面白いアルゴリズムの話をしましょう。
最大公約数（GCD）の計算といえば、みんながよく知る「ユークリッドのアルゴリズム」が定番ですよね。でも、もっと効率的でクールな方法があるんです。それが「Steinのアルゴリズム（ビットGCDアルゴリズム）」。これ、割り算を使わずにビット演算で最大公約数を求める方法なんです。
GCDをビットで求める？何が嬉しいの？
通常のユークリッド法では、割り算や剰余（mod）演算が中心になります。しかし、割り算は計算コストが高いことが知られています。特に低レベルのシステムや、数が巨大な場合は割り算を避けたいところ。
そこで登場するのが、ビット演算を使ったGCD計算。ビット演算は軽量で、プロセッサが非常に効率よく処理できるので、速度面でメリットが大きいんです。
さらに、アルゴリズムとしての美しさもポイント。ビット演算を駆使して数学的な問題を解くのは、プログラマにとってちょっとしたロマンですよね。
Steinのアルゴリズムとは？
Steinのアルゴリズム（またはビットGCDアルゴリズム）は、以下のアイデアに基づいています。
- 偶数の共通因数を取り除く
偶数同士のGCDは必ず2で割れるので、両方の数を2で割り、共通因数「2」を数えておきます。 - 奇数に揃える
片方が偶数の場合、偶数を2で割って奇数にします。 - 引き算で差を取る
奇数同士の場合、大きい方から小さい方を引きます。この操作を繰り返して、値を徐々に小さくしていきます。 - 2の因数を元に戻す
最後に、最初に取り除いた「2」をGCDに掛け算して答えを出します。
これを繰り返すことで、割り算なしでGCDを求めることができるのです。
Python実装
では、このアルゴリズムをPythonで実装してみましょう。
def gcd_stein(a: int, b: int) -> int:
# ベースケース：どちらかがゼロならもう片方がGCD
if a == 0:
return b
if b == 0:
return a
# ステップ1: 共通因数2をカウント
shift = 0
while ((a | b) & 1) == 0: # a と b が両方偶数の間
a >>= 1
b >>= 1
shift += 1
# ステップ2: a を奇数にする
while (a & 1) == 0:
a >>= 1
# ステップ3: メインループ
while b != 0:
# b を奇数にする
while (b & 1) == 0:
b >>= 1
# 大小比較して差を計算
if a > b:
a, b = b, a # a と b をスワップ
b = b - a # b を更新
# ステップ4: 共通因数2を元に戻す
return a << shift
実行例
アルゴリズムがどう動くのか、いくつかの例を試してみましょう。
print(gcd_stein(48, 18)) # 出力: 6
print(gcd_stein(101, 103)) # 出力: 1
print(gcd_stein(56, 98)) # 出力: 14
コードの解説
偶数の共通因数をカウント
while ((a | b) & 1) == 0:
a >>= 1
b >>= 1
shift += 1
ここで、両方の値が偶数である間は2で割り続けます。最終的に取り除いた2の個数は shift に保存。
奇数化
while (a & 1) == 0:
a >>= 1
a が偶数なら奇数になるまで右シフト。
大小比較と引き算
if a > b:
a, b = b, a
b = b - a
aと bを比較して引き算。これを繰り返します。
結果を復元
return a << shift最後に、最初に取り除いた2を掛けて（左シフトして）答えを出します。
なぜビット演算で速くなる？
- 割り算を使わない：割り算はCPUにとって重い処理。
- シフト演算は高速：
>>や<<はプロセッサで効率よく実行される。 - 繰り返しの計算がシンプル：引き算とビット操作の組み合わせだけで計算を進められる。
特に、数値が非常に大きい場合や、計算リソースが限られた環境（埋め込みシステムなど）では、この効率性が大きな差になります。
まとめ：ビットで数学を操る楽しさ
Steinのアルゴリズムは、ただ効率的なだけでなく、プログラマにとって「美しい」と感じられるアルゴリズムの1つです。通常のGCD計算よりも高速でありながら、割り算を一切使わないという発想の転換が素晴らしい。
皆さんもぜひ、自分のプロジェクトや勉強の一環で試してみてください。アルゴリズムを理解する楽しさと、ビット演算の魅力にハマること間違いなしです！
