猫型エンジニアのブログ

プログラム/ネットワーク系の技術関連をまとめたページです 

問題1.18~問題1.20

問題1.18

(define (double x) (+ x x))

(define (halve x)
  (cond ((even? x) (/ x 2))
        (else 0)))

(define (even? x)
  (= (remainder x 2) 0))

(define (new-times a b )
  (times-iter a b b 0))

(define (times-iter a b counter product)
  (cond ((= counter 0 product)
        ((even? counter) (+ product (double (times-iter a b (halve counter) 0))))
        (else (times-iter a b (- counter 1) (+ a product))))))

問題1.19

 見た目はすごく難しそうですが、単なる行列の掛け算の問題でした。繰り返される計算結果をあらかじめプログラムの中に組み込んでいくことで計算量を減らしています。

(define (fib 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))
                   (+ (* 2 p q) (* q q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

問題1.20

 特殊形式ifの評価は問題1.5において以下のように定められている。

特殊形式ifの評価規則は, 解釈系が正規順序と作用的順序のどちらを使うかに無関係に同じとする: 述語式を最初に評価し, その結果が帰結式と代替式のいずれを評価するかを決める

 
 正規順序評価では以下のようにremainder演算は18回実行される。
 書き下すのにすごい時間がかかりました。しかし、本当にコンピュータは内部では単純な計算しかやっていないというのは知識では知っていましたが、それを体で経験しました。とてもためになる問題でした。

;gcdを展開すると
;(if (= b 0)
;    a
;    (gcd b (remainder a b))) ...☆
;ただし、gcdを展開する際にはremainderの評価は行わない。

(gcd 206 40)

;a = 206
;b = 40

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

(if #f
    206    
    (gcd 40 (remainder 206 40)))

(gcd 40 (remainder 206 40))


;a = 40
;b = (remainder 206 40)として再度☆で展開する

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

(if #f
    40
    (gcd  (remainder 206 40) (remainder 40  (remainder 206 40))))

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

;a = (remainder 206 40) 
;b = (remainder 40  (remainder 206 40))として再度☆で展開する 

(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 #f
    (remainder 206 40)
    (gcd (remainder 40  (remainder 206 40)) (remainder (remainder 206 40) (remainder 40  (remainder 206 40)))))

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

;a = (remainder 40  (remainder 206 40)) 
;b = (remainder (remainder 206 40) (remainder 40  (remainder 206 40)))として再度☆で展開する 

(if (= (remainder (remainder 206 40) (remainder 40  (remainder 206 40))) 0)
    (remainder 40  (remainder 206 40))
    (gcd (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 #f
    (remainder 40  (remainder 206 40))
    (gcd (remainder (remainder 206 40) (remainder 40  (remainder 206 40))) (remainder (remainder 40  (remainder 206 40)) (remainder (remainder 206 40) (remainder 40  (remainder 206 40))))))

;a = (remainder (remainder 206 40) (remainder 40  (remainder 206 40))) 
;b = (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)))) 0)
    (remainder (remainder 206 40) (remainder 40  (remainder 206 40)))
    (gcd (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)))))))

 作用的順序評価の場合は、以下のように4回になります。

;(if (= b 0)
;    a
;   (gcd b (remainder a b)))を利用してgcdの展開を行う
;ただしgcdの展開をするよりも前に、引数のremainderを評価する

(gcd 206 40)

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

(gcd 40 (remainder 206 40))

(gcd 40 6)

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

(gcd 6 (remainder 40 6))

(gcd 6 4)

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

(gcd 4 (remainder 6 4))

(gcd 4 2)

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

(gcd 2 (remainder 4 2))

(gcd 2 0)

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

2