SICP § 1.2.5 最大公約数 （Euclidのアルゴリズム）

Euclidのアルゴリズム

最大公約数について。

２つの整数 a, b の最大公約数を求める場合、普通は両方の数を素因数分解して、
共通因子を取り出して乗算するけど、もっと効率のいい、すげーアルゴリズムがあるみたい。

このアルゴリズムは、

「a を b で割った剰余を r とすると、
　a と b の公約数は b と r の公約数とまったく同じである」

という考え方に基づいているとのこと。


どういう事かというと、最大公約数を求める関数を GCD とすると、

GCD(a, b) = GCD(b, r)

具体的には、

GCD(206, 40) = GCD(40, 6)   ・・・ 6 = 206 % 40
             = GCD(6, 4)
             = GCD(4, 2)
             = GCD(2, 0)
             = 2

で、204 と 40 の最大公約数は 2 になるそうだ。
お～って思ったんだけど、
な～んかどっかで聞いたような話なんだが、どこで聞いたか思い出せない。。

Schemeで実装するとこんな感じ。
remainder関数は２つの引数の剰余を求める関数です。

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

ほほう。


－