SICPを読む2

Programming Scheme SICP

おもいがけず休日だったのでSICPの練習問題を解く。問題1.7から1.11まで。はいはい末尾再帰末尾再帰。反復的プロセスですね。このペースだといつやり終えるんだろうか。
問題1.7

(define (square x) (* x x))
(define (sqrt-iter guess x)
  (if (good-enough? guess x)
    guess
    (sqrt-iter (improve guess x) x)))
(define (improve guess x)
  (average guess (/ x guess)))
(define (average x y) (/ (+ x y) 2))
(define (sqrt x) (sqrt-iter 1.0 x))

(define (good-enough? guess x)
  (= guess (improve guess x)))
; good-enough?
(sqrt 2.0)
; 1.414213562373095
(sqrt 100)
; 10.0
(sqrt 1000)
; 31.622776601683793
(sqrt 14024194)
; 3744.889050425927

a_n = a_{n+1}になるまでやっていただきます。

元々組み込まれてるsqrtだと、

(sqrt 2.0)
; 1.4142135623730951
(sqrt 100)
; 10.0
(sqrt 1000)
; 31.622776601683793
(sqrt 14024194)
; 3744.889050425927

(sqrt 2.0)で一桁多いですね。なんか近似の式がちょっと違うのかな？
まあでもだいたいよし。

問題1.8

(define (cbrt x)
  (define (iter guess x)
    (if (good-enough? guess x)
      guess
      (iter (improve guess x) x)))
  (define (improve guess x)
    (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))
  (define (good-enough? guess x)
    (= guess (improve guess x)))
  (iter 1.0 x))
; cbrt
(cbrt 27.0)
; 3.0
(cbrt 6)
; 1.8171205928321397
(cbrt 1000)
; 10.0
(cbrt 100)

あ、止まらねえ。これはあれか。真の立方根の値の前後で小さい振動を続けるんだろうな。
じゃあやっぱり

(define (cbrt x)
  (define (iter guess x)
    (if (good-enough? guess x)
      guess
      (iter (improve guess x) x)))
  (define (improve guess x)
    (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))
  (define (good-enough? guess x)
    (< (abs (- (cube guess) x)) (/ guess 1000000)))
  (define (cube x) (* x x x))
  (iter 1.0 x))
(cbrt 27.0)
; 3.0000000000000977
(cbrt 6)
; 1.817120681877066
(cbrt 1000)
; 10.000000000000002
(cbrt 100)
; 4.64158883361313

こんなもんだろか。うーん、(cbrt 100)とかの評価をできるようになったのはいいけれど。「振動してる」ってのを自覚させられればいいのですが。

1.2 手続きとその生成するプロセス

うーん末尾再帰が素敵ってことがよくわかってきますね。

問題1.9
線形再帰プロセス

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

これは以下のように計算されていきますね。

(+ 3 2)
(inc (+ (dec 3) 2))
(inc (inc (+ (dec 2) 2)))
(inc (inc (inc (+ (dec 1) 2))))
(inc (inc (inc 2)))
(inc (inc 3))
(inc 4)
5

こちらが線形反復プロセス

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

こちらは以下のとおり。

(+ 3 2)
(+ (dec 3) (inc 2))
(+ (dec 2) (inc 3))
(+ (dec 1) (inc 4))
5

プロセスはこっちの方がコンパクトですね。

問題1.10
アッカーマン関数。なんだそれ聞いたことはある気がする。

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

(or (= x 0) (= y 0) (= y 1))の時に終了。他はなんか再帰。

(A 1 10)
; (A 0 (A 1 9))
; (A 0 (A 0 (A 1 8)))
; ...
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
; (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
; ...
; 1024
 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1)))))))))) ;テスト
; 1024
(A 2 4)
; (A 1 (A 2 3))
; (A 1 (A 1 (A 2 2)))
; (A 1 (A 1 (A 1 (A 2 1))))
; (A 1 (A 1 (A 1 2)))
; (A 1 (A 1 (A 0 (A 1 1)))
; (A 1 (A 1 (A 0 2))
; (A 1 (A 1 4))
; ...
; (A 1 (A 0 8))
; (A 1 16)
; ...
; 65536
(A 3 3)
; (A 2 (A 3 2))
; (A 2 (A 2 (A 3 1)))
; (A 2 (A 2 2))
; (A 2 4)
; 65536

わかるよーなわかんねーよーな。いやよくわからんかな。

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))

2n
2^n
a_{n+1}=2^{a_n}
5n^2
だね。

問題1.11
f(n)=f(n-1)+2f(n-2)+3f(n-3)。

再帰的プロセス

(define (f n)
  (if (< n 3)
    n
    (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
; f
(f 4)
; 11
(f 10)
; 1892

反復的プロセス

(define (f n)
  (define (iter v1 v2 v3 nown n)
    (if (= nown n)
      (g v1 v2 v3)
      (iter v2 v3 (g v1 v2 v3) (+ 1 nown) n)))
  (define (g v1 v2 v3) (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3)))))
  (if (< n 3) n (iter 0 1 2 3 n)))
; f
(f 4)
; 11
(f 10)
; 1892

できたー。って、なんか滅茶苦茶遅いんですけど。ああ、gの定義がむちゃだ。なんでfとか呼ぶよ。

(define (f n)
  (define (iter v1 v2 v3 nown n)
    (if (= nown n)
      (g v1 v2 v3)
      (iter v2 v3 (g v1 v2 v3) (+ 1 nown) n)))
  (define (g v1 v2 v3) (+ v3 (* 2 v2) (* 3 v1)))
  (if (< n 3) n (iter 0 1 2 3 n)))
; f
(f 4)
; 11
(f 10)
; 1892

うひょー。
うひょーじゃねえよ。nownとかあるのも超だせえ。ああそうだ、計算式の中にnが関係してこないんだから、

(define (f n)
  (define (iter v1 v2 v3 n)
    (if (= n 3)
      (g v1 v2 v3)
      (iter v2 v3 (g v1 v2 v3) (- n 1))))
  (define (g v1 v2 v3) (+ v3 (* 2 v2) (* 3 v1)))
  (if (< n 3) n (iter 0 1 2 n)))

これでいいのね。nownとかださいけど、別にそういう書き方でもいい気がしてきた。

test