ユークリッドの互除法

Posted on Monday, September 8th, 2014 18:06:03

プログラミング100日チャレンジということで、ソートアルゴリズムをいくつか組んできました。クイックソートで再起アルゴリズムが出てきましたが、今日はもっと簡単で代表的なアルゴリズムをやります。小学生でも知っている人は知っている、ユークリッドの互除法です。明示的に記述された最古のアルゴリズムなんて言われています。

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

最大公約数(Greatest Common Divisor)を計算するためのアルゴリズムです。アルゴリズムの内容は私の下手くそな説明より、コードを見たほうが早いかもしれません。それほど単純で美しいアルゴリズムなのです。数学の面白さに魅入られましょう。

サンプル

ソースプログラム

実行結果

関数の解説

ユークリッドの互除法を自然言語で書くとこんな感じです。

1. 入力を m, n (m ≧ n) とする。
2. n = 0 なら、m を出力してアルゴリズムを終了する。
3. n を 新たな m とし、m を n で割った余りを新たに n として 2 に戻る。

上記のコードも、そのまんま3行になっています。大変分かりやすいですね。小学校の頃、分数を約分するときに考えていたことを思い出してみると分かりやすいと思います。もう少し簡単に説明しましょう。

自然数 m, n(m ≧ n) を割った剰余を r とすると、m と n との最大公約数は n と r の最大公約数と等しくなります。そのため、n を r で割った剰余、序数 r をその剰余で割った剰余…と剰余が 0 になるまで互い違いに計算を繰り返すことから “互除法” と呼ばれるわけです。

もっと簡潔に言えば、自然数 m, n(m ≧ n)に対して、m を n で割った余りを r とすると、gcd(m, n) = gcd(n, r) が成立し、これを繰り返し適用することで m と n の最大公約数が求まるということです。

多くの学生の心をへし折ってきた素因数分解によって最大公約数を求めることより、ユークリッドの互除法が好まれる理由は大きな値の最大公約数を求めることを想像すると、割り算のほうが圧倒的に計算量が少ないことが分かるでしょう。

最悪なケースは、隣り合うフィボナッチ数になっている場合です。何故なら計算量を増やすためには、余りが最も減りにくいパターンの自然数を与える必要があります。つまり、余りが(n – 1)になれば良い訳ですから 最小の m は(2n – 1) になります。

これを逆から見ていくと、(1, 1), (2, 3), (3, 5), (5, 8) と隣り合うフィボナッチ数になります。小飼弾先生に教わった内容そのままですが。

数学って面白いですね。ではでは。

Share

  • このエントリーをはてなブックマークに追加
  • Pocket
  • 0 follow us in feedly

Your Message

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です