今回は、ユークリッドの互除法を取り上げます。

ユークリッドの互除法とは何か。小学校の時に実は習っているはずですが、忘れている方は思い出してみてください。最大公約数(Greatest Common Divisor)を確実に計算する方法です。古代から有名なこのアルゴリズムは、かつては"The Algorithm"といえばこれをさすほど有名なアルゴリズムです。

それは、コードではなく普通の言葉でも簡単に書くことが出来ます。gcd(m, n)を出すには、

  1. mをnで割り、余りがrだとする
  2. 余りrが0なら、nがGCD。
  3. そうでなければ、nとrのGCDを求める

互い違いに割っていくので、互除法というわけです。

function gcd(m, n){
  if (m < n)  return gcd(n, m); // 常に m > n にしておく
  var r = m % n;                // 余りrが....
  if (r == 0) return n;         // 0 なら n がGCD
  return gcd(n, r);             // でなければnとrのGCD
}
gcd( , ) =

以外なところで使われるGCD

この最大公約数、実にさまざまなところで使われています。小学生でも使うのは、分数を約分する時。分子と分母を割るのは、最大公約数です。

コンピューターや電卓の「馬鹿さ加減」を揶揄するのに、1 / 3 * 3が1ではなく0.999...になるというのがありますが、これは精度に制限がある小数で計算しているからであって、コンピューターでも工夫すればこれがきっかり1になるように作れます。その場合は、小数ではなく分数で数値を保存しておけばよく、この場合四則演算に関しては、(整数の精度が無制限なら)かならず厳密な値を求めることができます。私も以前まさにそれを行うためのMath.Rationalを作ったのでよろしければご覧下さい。もちろんここでもGCDが使われています。

変わったところでは、In-Place Merge Sort (後述予定)の中でGCDが使われています。なぜGCDが必要なのかはちょっとした頭の体操です。興味のある方は検索してみてください。

最悪のケースの美しさ

ここで、どんな場合に互除法が最も苦戦するかを考えてみましょう。余りで割ることを繰り返しているのですから、この余りがなるべく減らないような整数の対を用意すればいいことになります。m > n な自然数mを自然数nで割った余りの最大値はn-1ですから、「余りを最大にする最小のm」は、n + n - 1 = 2n - 1です。これが常に繰り返される場合、互除法の繰り返し数も最大になるわけです。

今度は、その互除法を逆から追って見ましょう。まずn = 1の場合。これだとmもまた1になります。n = 2 では?mは3。以下、nとmの対は(3,5),(5,8),(8,13)....と増えていきます。どこかで見た数ではありませんか?

そうです。フィボナッチ数です。互除法が最も苦戦するのは、数の対が隣り合うフィボナッチ数になっている時なのです。互除法での繰り返しは、(F(n+1), F(n))の組み合わせの時に、n回となります。

こうした以外なつながりを見つけるのも、アルゴリズムの楽しみの一つです。

Dan the Indivisible