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

AOJ ALDS1_1_Bで最大公約数を求める問題が出た。
最大公約数を求める有名なアルゴリズムとしてユークリッドの互除法というものがある。

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

非負整数a,bについて、その最大公約数をgcd(a,b)とする。

a ≥ bであるとき、gcd(a,b) = gcd(b,a%b)である。
(a%bはaをbで割った時の剰余)

これを用いて、次のようにして最大公約数を求めることができる。
1.　a%bを計算する。
2.　a%bが0ならばbを最大公約数として出力して終了する。
3.　aにbを代入し、bにa%bを代入したうえで、1 に戻る。

実装

これを関数unsigned euclidean_gcd(unsigned a,unsigned b)として実装した。
ただし、aとbはともに0ではないものとする。
引数はどちらが大きくても問題ないように実装する。

最初に書いた実装

unsigned euclidean_gcd(unsigned a, unsigned b) {
  while(1) {
    if(a < b) swap(a, b);
    if(!b) break;
    a %= b;
  }
  return a;
}

2つの変数x,yを交換する操作をswap(x,y)とした。
求めたいものは求まるのだが、アルゴリズムがはっきり見えないし、無限ループがあらわになっていて好きになれない。

より好みな実装

unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

アルゴリズム通りで、あらわな無限ループもない。
追記(2018/7/23) まともに動かないコードを乗せていたことに今更気づいたので修正。ついでにswapを使わないようにした。