オンラインSICP読書女子会 #5

オンラインSICP読書女子会 #5 (1.2.5~1.2.6) 用のめも〜.

ex 1.19

練習問題 1.19: フィボナッチ数を対数的ステップ数で計算する巧妙なアルゴリズムがある。1.2.2 節の fib-iter プロセスでの状態変数 a と b の変換、a ← a + b、b ← a を思い出そう。この変換を T と呼ぶことにする。すると、1 と 0 から始めて T を繰り返し n 回適用すると Fib(n + 1) と Fib(n) というペアができることになる。言い換えれば、フィボナッチ数はペア (1, 0) に対して T n (変換 T の n 乗) を適用することで求められるということだ。ここで、(a, b) というペアを a ← bq + aq + ap と b ← bp + aq に変換するような変換族 T pq の特殊な場合 (p = 0、q = 1) として T を考えることにする。このような変換 T pq を二回適用すると、その効果は同じ形式を持つ T p ′ q ′ を一回適用するのと同じであることを示し、p と q に対する p ′ と q ′ を求めよ。こうすると、この種の変換に対する二乗を明示的に行うことができるようになり、fast-expt 手続きと同じように、T n を二乗の連続によって求められるようになる。これらをすべて組み合わせて、対数的ステップ数で動く次の手続きを完成させよ。

(define (fib-1.19 n)
    (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
    (cond
        ((= count 0) b)
        ((even? count)
            (fib-iter
                a
                b
                (+ (* p p) (* q q)) ; p’ を計算する
                (+ (* 2 p q) (* q q)) ; q’ を計算する
                (/ count 2)))
        (else
            (fib-iter
                (+ (* b q) (* a q) (* a p))
                (+ (* b p) (* a q))
                p
                q
                (- count 1)))))

じぶんの回答.

; T_pq :: (元の漸化式)
;   a <- bq + aq + ap
;   b <- bp + aq
;
; T_pq x0 :: (i=0 の場合)
;   (a0, b0)
;
; T_pq x1 :: (i=1 の場合)
;   a1 <- b0q + a0q + a0p
;   b1 <- b0p + a0q
;
; T_pq x2 :: (i=2 の場合, がんばって展開＆再構成)
;
;   a2 <- b1q + a1q + a1p
;       = (b0p + a0q)q + (b0q + a0q + a0p)q + (b0q + a0q + a0p)p
;       = b0pq + a0qq + b0qq + a0qq + a0pq + b0pq + a0pq + a0pp
;       = b0(pq + qq + pq) + a0(qq + qq + pq + pq + pp)
;       = b0(2pq + qq) + a0(pp + 2pq + 2qq)
;       = b0(2pq + qq) + a0(2pq + qq) + a0(pp + qq)
;   a2.p' = pp + qq
;   a2.q' = 2pq + qq
;
;   b2 <- b1p + a1q
;       = (b0p + a0q)p + (b0q + a0q + a0p)q
;       = b0pp + a0pq + b0qq + a0qq + a0pq
;       = b0(pp + qq) + a0(pq + qq + pq)
;       = b0(pp + qq) + a0(2pq + qq)
;   b2.p' = pp + qq
;   b2.q' = 2pq + qq

a(i=2) を展開した場合でも b(i=2) を展開した場合でも,
p' と q' がちゃんと同じになるのがなんだかふしぎ〜.

算出した p' と q' の値を使って, 問題文中にあった式の空欄を埋めて完成.

(define (fib-1.19 n)
    (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
    (cond
        ((= count 0) b)
        ((even? count)
            (fib-iter
                a
                b
                (+ (* p p) (* q q)) ; p’ を計算する
                (+ (* 2 p q) (* q q)) ; q’ を計算する
                (/ count 2)))
        (else
            (fib-iter
                (+ (* b q) (* a q) (* a p))
                (+ (* b p) (* a q))
                p
                q
                (- count 1)))))

検算〜.

; gosh> (fib-1.19 0)
; 0
; gosh> (fib-1.19 1)
; 1
; gosh> (fib-1.19 2)
; 1
; gosh> (fib-1.19 3)
; 2
; gosh> (fib-1.19 4)
; 3
; gosh> (fib-1.19 5)
; 5
; gosh> (fib-1.19 6)
; 8
; gosh> (fib-1.19 7)
; 13
; gosh> (fib-1.19 8)
; 21
; gosh> (fib-1.19 9)
; 34
; gosh> (fib-1.19 10)
; 55

; gosh> (fib-1.19 11)
; 89
; gosh> (fib-1.19 12)
; 144
; gosh> (fib-1.19 13)
; 233
; gosh> (fib-1.19 14)
; 377
; gosh> (fib-1.19 15)
; 610
; gosh> (fib-1.19 16)
; 987
; gosh> (fib-1.19 17)
; 1597
; gosh> (fib-1.19 18)
; 2584
; gosh> (fib-1.19 19)
; 4181
; gosh> (fib-1.19 20)
; 6765

ex 1.20

練習問題 1.20: ある手続きが生成するプロセスは、もちろん、インタプリタの規則によって異なる。例として、上で説明した反復 gcd 手続きについて考える。この手続きを、1.1.5 節で考察した正規順序評価によって解釈するとする (if に対する正規順序評価規則は練習問題 1.5に記述されている)。置換法を (正規順序に対して) 使って、(gcd 206 40) を評価する際に生成されるプロセスを図示し、実際に実行される remainder 演算を示せ。 (gcd 206 40) の正規順序評価では、 remainder 演算は何回実行されるだろうか。適用順序評価ではどうだろうか。説明せよ。

使う式:

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

正規順序評価規則の場合

; [入力]
(gcd 206 40)

; [step 1]
; a1=206, b1=40. <env:none>
(if (= b1 0)
    a1
    (gcd b1 (remainder a1 b1)))
; <eval b1> <env:a1=206, b1=40>
b1
40
; pred ==> false.
else-clause
(gcd b1 (remainder a1 b1))

; [step 2]
; a2=b1, b2=(remainder a1 b1) <env:a1=206, b1=40>
(if (= b2 0)
    a2
    (gcd b2 (remainder a2 b2)))
; <eval b2> <env:a1=206, b1=40; a2=b1, b2=(remainder a1 b1)>
b2
(remainder a1 b1)
(remainder 206 40)
; REMAINDER 1 回目.
6 ; <env:a1=206, b1=40, a2=b1, b2=6>
; pred = false
else-clause
(gcd b2 (remainder a2 b2))

; [step 3]
; a3=b2, b3=(remainder a2 b2) <env:a1=206, b1=40, a2=b1, b2=6>
(if (= b3 0)
    a3
    (gcd b3 (remainder a3 b3)))
; <eval b3> <env:a1=206, b1=40; a2=b1, b2=6; a3=b2, b3=(remainder a2 b2)>
b3
(remainder a2 b2)
(remainder b1 6)
(remainder 40 6) ; <env:a1=206, b1=40; a2=40, b2=6; a3=b2, b3=(remainder a2 b2)>
; REMAINDER 2 回目.
4 ; <env:a1=206, b1=40; a2=40, b2=6; a3=b2, b3=4>
; pred = false
else-clause
(gcd b3 (remainder a3 b3))

; [step 4]
; a4=b3, b4=(remainder a3 b3) <env:a1=206, b1=40; a2=40, b2=6; a3=b2, b3=4>
(if (= b4 0)
    a4
    (gcd b4 (remainder a4 b4)))
; <eval b4> <env:a1=206, b1=40; a2=40, b2=6; a3=b2, b3=4; a4=b3, b4=(remainder a3 b3)>
b4
(remainder a3 b3)
(remainder b2 4)
(remainder 6 4) ; <env:a1=206, b1=40; a2=40, b2=6; a3=6, b3=4; a4=b3, b4=(remainder a3 b3)>
; REMAINDER 3 回目.
2 ; <env:a1=206, b1=40; a2=40, b2=6; a3=6, b3=4; a4=b3, b4=2>
; pred = false
else-clause
(gcd b4 (remainder a4 b4))

; [step 5]
; a5=b4, b5=(remainder a4 b4) <env:a1=206, b1=40; a2=40, b2=6; a3=6, b3=4; a4=b3, b4=2>
(if (= b5 0)
    a5
    (gcd b5 (remainder a5 b5)))
; <eval b5> <env:a1=206, b1=40; a2=40, b2=6; a3=6, b3=4; a4=b3, b4=b3; a5=b4, b5=(remainder a4 b4)>
b5
(remainder a4 b4)
(remainder b3 2)
(remainder 4 2) ; <env:a1=206, b1=40; a2=40, b2=6; a3=6, b3=4; a4=2, b4=2; a5=b4, b5=(remainder a4 b4)>
; REMAINDER 4 回目.
0 ; <env:a1=206, b1=40; a2=40, b2=6; a3=6, b3=4; a4=2, b4=2; a5=b4, b5=0>
; pred = true
then-clause
a5
; <eval a5> <env:a1=206, b1=40; a2=40, b2=6; a3=6, b3=4; a4=2, b4=2; a5=b4, b5=0>
a5
b4
2 ; answer.

; remainder 演算は合計4回.

適用順序評価規則の場合

; [入力]
(gcd 206 40)

; [step 1]
; a1=206, b1=40. <env:none>
(if (= b1 0)
    a1
    (gcd b1 (remainder a1 b1)))
; <eval b1> <env:a1=206, b1=40>
b1
40
; pred ==> false.
else-clause
(gcd b1 (remainder a1 b1))
(gcd 40 (remainder 206 40))
; REMAINDER 1 回目.
(gcd 40 6)

; [step 2]
; a2=40, b2=6
(if (= b2 0)
    a2
    (gcd b2 (remainder a2 b2)))
; <eval b2> <env:a2=40, b2=6>
b2
6
; pred ==> false.
else-clause
(gcd b2 (remainder a2 b2))
(gcd 6 (remainder  40 6))
; REMAINDER 2 回目.
(gcd 6 4)

; [step 3]
; a3=6 b3=4
(if (= b3 0)
    a3
    (gcd b3 (remainder a3 b3)))
; <eval b3> <env:a3=6, b3=4>
b3
4
; pred ==> false.
else-clause
(gcd b3 (remainder a3 b3))
(gcd 4 (remainder  6 4))
; REMAINDER 3 回目.
(gcd 4 2)

; [step 4]
; a4=4 b4=2
(if (= b4 0)
    a4
    (gcd b4 (remainder a4 b4)))
; <eval b4> <env:a4=4, b4=2>
b4
2
; pred ==> false.
else-clause
(gcd b4 (remainder a4 b4))
(gcd 2 (remainder  4 2))
; REMAINDER 4 回目.
(gcd 2 0)

; [step 5]
; a5=2 b5=0
(if (= b5 0)
    a5
    (gcd b5 (remainder a5 b5)))
; <eval b5> <env:a5=2, b5=0>
b5
0
; pred ==> true
then-clause
a5
; <eval a5> <env:a5=2, b5=0>
a5
2 ; answer.

; こちらの場合でも remainder 演算は合計4回.

それぞれの特徴

正規順序評価規則の場合は展開処理が先に実行されて, 展開の後に特殊形式 if の条件句で remainder の評価が実行される.
gcd → if → remainder → gcd ... の順にぐるぐる反復される

適用順序評価規則の場合は引数の評価が先に実行されて, 引数の値が確定してから関数部分が展開される.
こちらは gcd → remainder → if → gcd ... の順にぐるぐる.

if と remainder の順序は入れ替わっているけれど, 最終的に remainder が評価される回数はどちらの場合でも同じ.