SICP 1.2.5 Greatest Common Divisors - プログラミング再入門

引き続き整数計算の世界。

ノート

最大公約数。

第２章で有理数（分数で表せる数）の計算を実装する事になるが、約分の際にGCDが計算出来る必要がある。

ユークリッドの互除法

aをbで割った時の余りをrとした時、aとbの最大公約数はbとrの最大公約数に等しい。

と言うのが基本法則。ただ残念な事に感覚的には全くピンと来ない。

と言う訳で、Webで色々調べた結果をメモ。

二つの整数をA、B、ここではA > Bとする。
AをBで割った余りをR、商をQとするとA = BQ + Rと表せる。A > Bを仮定しているので0 ≦ R < Bが成り立つ。（確かに割る数よりも余りが大きくなる事はあり得ない）
AとBの最大公約数をCとするとAとBはそれぞれA = aC、B = bCと表せ、aとbは１以外に公約数を持たない互いに素の関係である。C=1の場合はそもそもAとBが互いに素。
これらをA = BQ + Rに代入するとaC = bCQ + R。移項してR = aC - bCQ = (a - bQ) C。式の全ての項は整数なのでCはRの約数でもある事が分かる。ただしこの式はaとbが互いに素でなくても成り立つので任意のAとBの公約数で成り立ってしまう。（二つの整数を割った余りが、その二つの整数の公約数を約数に持つ事だけでも感覚的にはピンと来ない。）
CはRの約数でもあるので、R=rCと置くと、R = (a - bQ) Cの式からr = a - bQと書ける。移項してa = bQ + r。
仮にbとrが１以外の公約数cを持つとすると、b=b'c、r=r'cと書けて、上記の式はa = b'cQ + r'c = (b'Q + r') cと書けるので、cはaの約数でもある事になる。つまりa = a'cと書ける。最初のCがAとBの最大公約数であった場合、aとbは互いに素だったので、a=a'c、b=b'cとなるcは１以外には存在しない事になる。つまりbとrが１以外の公約数を持つと言う仮定は成り立たず、bとrも互いに素である事が分かる。

まとめるとCがAとBの最大公約数の場合、A = aC、B = bCと書けて、CはRの約数でもあるのでR = rCと書ける。CはAとBの最大公約数なのでaとbは互いに素であり、その時bとrも互いに素と言う事になり、AとBの最大公約数CはBとRの最大公約数でもあると言える。

これでAとBの最大公約数を求める問題はBとRの最大公約数を求める問題に置き換えられる。この問題の置き換えを繰り返せば問題とする二つの整数はどんどん小さくなり、どこかの時点で余りが０となり最大公約数がみつかるか余りが１となって互いに素である事が分かる。

ラメの定理

ここに書いてある事は

二つの整数の最大公約数をユークリッドの互除法で計算するときのステップ数をkとすると、小さい方の整数はフィボナッチ数のk番目の数と等しいかそれより大きい。

WikipediaやWebで見られる一般的な説明では

割って余りを取るという操作を、最悪でも小さい方の十進法での桁数の約 5 倍繰り返せば、最大公約数に達する

前者を言い換えると、割る数（小さい方の整数）と同じか小さい最大のフィボナッチ数がk番目とした時、kがステップ数の最大値。
後者を言い換えると、小さい方の数の桁数の５倍がkの最大値。
この二つが全く同じ事を言っている訳ではなさそうだが、k番目のフィボナッチ数はその桁数を５倍した数よりも小さいと言う事の様。証明は難しそう。

Exercise 1.20

非正格（normal-order）と正格（applicative-order）とでremainderを呼び出す回数を比較する。
ルールとしてifの条件式は無条件にその場で値を評価する事とする。

その１）normal-orderの場合：

(gcd 206 40)

定義を展開して

(if (= 40 0)
    206
    (gcd 40 (remainder 206 40)))

if式を簡約（と言う言葉が正しいのかわからないけど）して

(gcd 40 (remainder 206 40))

再びgcdの定義を展開して

(if (= (remainder 206 40) 0)
    40
    (gcd (remainder 206 40)
         (remainder 40 (remainder 206 40))))

ifだけは即座に評価するルールなので、(remainder 206 40) = 6を計算して（１回目）、それを展開すると

(if (= 6 0)
    40
    (gcd (remainder 206 40)
         (remainder 40 (remainder 206 40))))

関数値が引数にのみ依存している事が保証出来ればここで、(if (= 6 0) 40 (gcd 6 (remainder 40 6)))まで簡約出来るのだが。
さて続き。ifの条件式の値が求まったので、まず簡約する。

(gcd (remainder 206 40)
     (remainder 40 (remainder 206 40)))

で再びgcdの定義を展開

(if (= (remainder 40 (remainder 206 40)) 0)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40)
                    (remainder 40 (remainder 206 40)))))

ifの条件式だけは評価する。(remainder 206 40) = 6（２回目）、(remainder 40 6) = 4（３回目）

(if (= 4 0)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40)
                    (remainder 40 (remainder 206 40)))))

if式を簡約して、

(gcd (remainder 40 (remainder 206 40))
     (remainder (remainder 206 40)
                (remainder 40 (remainder 206 40))))

再びgcdの定義を展開

(if (= (remainder (remainder 206 40)
                (remainder 40 (remainder 206 40)))
       0)
    (remainder 40 (remainder 206 40))
    (gdc (remainder (remainder 206 40)
                    (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))))

ifの条件式だけは評価する：

(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))。
最初のremainderの第１引数(remainder 206 40) = 6を展開（４回目）して(remainder 6 (remainder 40 (remainder 206 40)))。
最後の(remainder 206 40) = 6を展開（５回目）して(remainder 6 (remainder 40 6))。
最後の(remainder 40 6) = 4を展開（６回目）して(remainder 6 4)。
(remainer 6 4) = 2を展開（７回目）する。

(if (= 2 0)
    (remainder 40 (remainder 206 40))
    (gdc (remainder (remainder 206 40)
                    (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))))

if式を簡約して

(gdc (remainder (remainder 206 40)
                (remainder 40 (remainder 206 40)))
     (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40)))))

またgcdの定義を展開

(if (= (remainder (remainder 40 (remainder 206 40))
                  (remainder (remainder 206 40)
                             (remainder 40 (remainder 206 40))))
       0)
    (remainder (remainder 206 40)
               (remainder 40 (remainder 206 40)))
    (gdc (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))
         (remainder (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40)))
                    (remainder (remainder 40 (remainder 206 40))
                               (remainder (remainder 206 40)
                                          (remainder 40 (remainder 206 40)))))))

ifの条件式だけは評価する。

(remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))。
３番目の(remainder 206 40) = 6を展開（８回目）して(remainder (remainder 40 6) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))。
２番目の(remainder 40 6) = 4を展開（９回目）して(remainder 4 (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))。
最後の(remainder 206 40) = 6を展開（１０回目）して(remainder 4 (remainder (remainder 206 40) (remainder 40 6)))。
最後の(remainder 40 6) = 4を展開（１１回目）して(remainder 4 (remainder (remainder 206 40) 4))。
最後の(remainder 206 40) = 6を展開（１２回目）して(remainder 4 (remainder 6 4))。
最後の(remainder 6 4) = 2を展開（１３回目）して(remainder 4 2)。
(remainder 4 2)= 0を展開（１４回目）する。

(if (= 0 0)
    (remainder (remainder 206 40)
               (remainder 40 (remainder 206 40)))
    (gdc (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))
         (remainder (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40)))
                    (remainder (remainder 40 (remainder 206 40))
                               (remainder (remainder 206 40)
                                          (remainder 40 (remainder 206 40)))))))

if式を簡約して

(remainder (remainder 206 40)
           (remainder 40 (remainder 206 40)))

ここで漸くgcdの展開が終わり、ここからはremainderを展開する事になる。けど、ここにはその定義は無いのでremainderの定義の中から展開される物として、

最初の(remainder 206 40) = 6を展開（１５回目）して(remainder 6 (remainder 40 (remainder 206 40)))。
最後の(remainder 206 40) = 6を展開（１６回目）して(remainder 6 (remainder 40 6))。
最後の(remainder 40 6) = 4を展開（１７回目）して(remainder 6 4)。
最後に(remainder 6 4) = 2を展開（１８回目）

纏めると、normal-orderでremainderを評価して展開する回数は１８回。でも実際には(remainder 206 40)と(remainder 40 6)と(remainder 6 4)と(remainder 4 2)の４種類しか計算していない。

その２）adaptive-orderの場合：

(gcd 206 40)

引数はこれ以上評価する必要がないので、gcdの定義を展開

(if (= 40 0)
    206
    (gcd 40 (remainder 206 40)))

if式を評価する

(gcd 40 (remainder 206 40))

ここで(remainder 206 40) = 6を展開（１回目）。

(gcd 40 6)

gcdの定義を展開

(if (= 6 0)
    40
    (gcd 6 (remainder 40 6)))

if式を評価して

(gcd 6 (remainder 40 6))

ここで(remainder 40 6) = 4を展開（２回目）。

(gcd 6 4)

gcdの定義を展開

(if (= 4 0)
    6
    (gcd 4 (remainder 6 4)))

if式を評価して

(gcd 4 (remainder 6 4))

ここで(remainder 6 4) = 2を展開（３回目）。

(gcd 4 2)

gcdの定義を展開

(if (= 2 0)
    4
    (gcd 2 (remainder 4 2)))

if式を評価して

(gcd 2 (remainder 4 2))

ここで(remainder 4 2) = 0を展開（４回目）。

(gcd 2 0)

gcdの定義を展開

(if (= 0 0)
    2
    (gcd 0 (remainder 2 0)))

if式を評価して

applicative-orderでremainderを評価して展開する回数は４回。