ユークリッドの互除法

超有名な最大公約数を求めるアルゴリズム。 その理論はともかく、rubyで書くなら 

def gcd(a, b)
  while true
    if a > b
      a %= b
      return b if a == 0
    else
      b %= a
      return a if b == 0
    end
  end
end


さらに短く 
def gcd(a, b)
  while true
    if a > b
      return b if (a %= b) == 0
    else
      return a if (b %= a) == 0
    end
  end
end


大きい数で小さい数を割った値を求めても時間が余計にかかるだけで計算に影響はないだろうから、さらに短く。 

def gcd(a, b)
  while true
    return b if (a %= b) == 0
    return a if (b %= a) == 0
  end
end


こんなもんですかね？Cなら 

int gcd(int a, int b)
{
    while(1){
	if(!(a %= b))
	    return b;
	if(!(b %= a))
	    return a;
    }
}


それにしても紀元前にこのアルゴリズムを考えたユークリッドはすごいわ
Posted by issei

カテゴリ: 数学

コメント一覧

アルゴリズムには直接関係ないところで、while true および while (1) がやっぱり気持悪いです。 もちろんこれらはの定数式はコンパイル言語でかつ最適化がきちんと働くのであれば、コンパイル時点で静的に評価されて条件判断ではなくなるのはわかるのですが...。 ということで、C ならば for(;;) 派です :-) 短く書くなら本体一行で。 int gcd(int a, int b) { return (a%=b)?gcd(b,a):b; }
ふたつき
再起はスタックを食いつぶすからもっと危険だと思いますが……
kawa
その環境でどう使われるか、そしてどれくらいスタックを消費するかを予測できていれば問題ないのでは。
ただ
実用で書くなら初段に引数の正整数チェック入れますので1行じゃ書きません。 私のコードもIsamiさんのコードもbに0を入れた時点で :-) というのはともかく計算量の評価は必要、というのには同意します。 ということで、問題なのですが、int が 64 bit 符号なし整数のときに繰り返し回数(再帰段数)の最大値を評価しなさい :-)
ふたつき
どこまで短く出来るかだけにこだわってるだけだから、実用性は無視でよろしいかとｗ で冷静に考えれば a = a % b を計算した後は必ず a<bなのだから続けて b = b % a を計算しちゃえばいいですね。そういう意味でa>bの大小を比較するのは無意味で、最初の一回目の計算が無駄になるかならないかくらいのデメリットしかない。 参考までにループ回数はもちろん入力数によりけりですが、ログスケール。なので32bit同士くらいなら、一瞬。 でかい数、例えば、 3^1000+1と 4^1000+1の最大公約数を求めるとしても135回です。
Isami
最大数の証明 初期値a0, b0に関して、 a0 > b0 とします。 a1 = a0 % b0 (a1 < b0 < a0) この演算後a0はどの程度小さくなるかを考えます。 a0 = b0/2のときはアルゴリズムは終了。 a0 < b0/2とすれば明らかに a1 < a0/2 a1 > b0/2とすれば a1 = a0 % b0 = (a0 - b0) < a0/2 いずれにしろ a1はa0の半分以下になります。つまり64bit intなら最悪でも64回で終了です。
Isami
上記より最悪の場合を構成するには、アルゴリズムを逆に適用して初期値 a(0) = 1, a(1) = 1 より a(k) = a(k-2) + a(k-1) を順次計算してやればいいのかな。(フィボナッチ数ですね) これによれば、符号なし64bit intでワーストケースは a = 7540113804746346429 b = 12200160415121876738 で90回前後の再帰で計算可能です。(境界条件のとこで数えるの面倒なので前後としときます:-)) a%=bとb%=aを一回のループとして45回くらい。
ふたつき
なるほど。そこでフィボナッチですか。 鋭いですね～
Isami