ユークリッドの除去法アルゴリズム

最大公約数を求める際ユークリッドの除去法を使ったアルゴリズムを考える場合、計算量はO(log max{x,y})となる理由を教えて下さい。

簡単な擬似コードも教えてもらえるとありがたいです。

No.1 回答者： mikaemi 回答日時： 2007/09/03 23:03

数学の問題かとも思いますが^^

「ラメの定理」として知られていますね。

あるいは、もう少し精密にして、「φ=(√5+1)/2 とすると（フィボナッチ数列で出てくる数値）、互除法は、φを底にした対数関数log(min(m,n))以上の最小の整数回の除法で完了する」となるようです。

たとえば、一松信 著『代数学入門第一課』近代科学社 に載ってます。

ラメの定理（Lame's theorem）で検索したら見つかると思いますよ、たぶん^^ 英語かもしれないですが。