計算機プログラムの構造と解釈(SICP)

• 1.45

(define (pow x y) 
  (define (pow-iter x y p)
    (if (<= y 0)
        p
        (pow-iter x (- y 1) (* p x))))
  (pow-iter x y 1))

(define (avarage x y) (/ (+ x y) 2.0))

(define (fixed-point f first-guess)
  (define tolerance 0.0000000001)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (square-root x)
  (fixed-point (lambda (y) (avarage y (/ x y)))
               1.0))
;(square-root 9)
;-> 3.0

(define (cube-root x)
  (fixed-point (lambda (y) (avarage y (/ x (pow y 2))))
               1.0))
;(cube-root 27)
;-> 3.0

(define (4-root x)
  (fixed-point (lambda (y) (avarage y (avarage y (/ x (pow y 3)))))
               1.0))
;(4-root 81)
;-> 3.0

(define (5-root x)
  (fixed-point (lambda (y) (avarage y (avarage y (/ x (pow y 4)))))
               1.0))

(define (6-root x)
  (fixed-point (lambda (y) (avarage y (avarage y (/ x (pow y 5)))))
               1.0))

(define (7-root x)
  (fixed-point (lambda (y) (avarage y (avarage y (/ x (pow y 6)))))
               1.0))

;ここから、もうひとつ平均緩和が必要になる。
(define (8-root x)
  (fixed-point (lambda (y) (avarage y (avarage y (avarage y (/ x (pow y 7))))))
               1.0))

;実験の結果、次は16となり、その次は32となった。
;よって、n乗根計算において、平均緩和が必要な数xは、

;nより大きく、もっともnに近い、2のy乗の数があるとき
;x=y-1 であらわせる。

;以上を手続きにすると、
(define (avarage-req-num n)
  (define (avarage-req-num-iter y)
    (if (< n (pow 2 y))
        y
        (avarage-req-num-iter (+ y 1))))
  (- (avarage-req-num-iter 2) 1))
;となる。(nをいれてxがかえる)

;以上から、n乗根計算の手続きが実装できる。
(define (compose f g)
  (lambda (x) (f (g x))))

(define (repeated f n)
  (define (repeated-iter f n p)
    (if (<= n 0)
        p
        (repeated-iter f (- n 1) (compose p f))))
  (repeated-iter f n (lambda (x) x)))

(define (n-root x n)
  (fixed-point (lambda (y)
                 (define (avarage-y z) (/ (+ z y) 2.0))
                 ((repeated avarage-y (avarage-req-num n)) (/ x (pow y (- n 1)))))
               1.0))


;(n-root (pow 2 2) 2)
;-> 2.0

;(n-root (pow 2 32) 32)
;-> 2.0

;(n-root (pow 2 11) 11)
;-> 1.9999999999814446

;(n-root (pow 2 45) 45)
;-> 1.999999999987137

;(n-root (pow 2 63) 63)
;-> 1.9999999999518796

;(n-root (pow 2 64) 64)
;-> 2.0

;(n-root (pow 2 100) 100)
;-> 2.000000000032972

;(n-root (pow 2 121) 121)
;-> 1.999999999956268

;(n-root (pow 2 128) 128)
;-> 2.0

;ある程度正確に動いているようである。

;(repeated f n)がかえす関数が引数ひとつ限定につくられていたので、
;(avarage y (avarage y (avarage y (x))))
;のような関数連鎖をつくることができなかった。
;また、yが不確定なので(n-root)内ではクロージャーをつくることもできなかった。
;そこで、(fixed-point)に渡す関数のなかで(avarage-y z)を定義した
;(fixed-point)にわたされたlambdaが評価された時点で、(avarage-y z)がつくられ、
;その時点でのyの値が閉包される。こんな書き方がゆるされるのか
;と思ったが普通にとおった。すごい。

• 1.46

(define (iterative-improve f g)
  (lambda (first-guess)
    (define (try guess)
      (let ((next (g guess)))
        (if (f guess next)
            next
            (try next))))
    (try first-guess)))

(define (fixed-point f first-guess)
  ((iterative-improve
    (lambda (v1 v2) (< (abs (- v1 v2)) 0.0000000001))
    f)
   first-guess))

(define (avarage x y) (/ (+ x y) 2))
(define (sqrt x)
  (fixed-point (lambda (y) (avarage y (/ x y)))
               1.0))

; (sqrt 2)
; 1.414213562373095

;できた。

;でも実は予想に反して動いている。
;(iterative-improve f g)の中のlambdaの中で
;(try guess)を定義しているため、(try guess)の定義が評価されるのは
;lambdaが動く時点と考え、fとgのクロージャーがうまくうごかないかと思ったが、
;予想に反してこのままうごいた。クロージャーの挙動はいまいちつかめていない。

;1章 最後の問題なのに歯応えがあまりない。

• これでやっと2章にいける!