問題1.10

(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(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))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
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 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16) ; 2^16
; 中略
65536

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)
65536

fは2n、gは2ⁿ、hは2↑↑n。

問題1.9

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

(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

となり、再帰的プロセス。

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

(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

となり、反復的プロセス。

問題1.8

(defun good-enough? (guess x)
  (< (abs (- (expt guess 3) x)) 0.001))

(defun improve (guess x)
  (/ (+ (/ x (expt guess 2)) (* guess 2)) 3))

(defun cbrt-iter (guess x)
  (if (good-enough? guess x)
      guess
      (cbrt-iter (improve guess x) x)))

(defun cbrt (x)
  (cbrt-iter 1.0 x))

二乗や三乗を求める関数の定義は自明なので、exptで。

問題1.7

小さい数について。

CL-USER> (mysqrt 0.0001)
0.032308448
CL-USER> (* (mysqrt 0.0001) (mysqrt 0.0001))
0.0010438358

となり、good-enough?での許容値より小さい数には上手く動作しない。

大きい数について。

CL-USER> (mysqrt 1.0e20)

; デバッガへ
FLOATING-POINT-OVERFLOW detected
   [Condition of type FLOATING-POINT-OVERFLOW]

CL-USER> (trace good-enough?)
NIL
CL-USER> (mysqrt 1.0d29)
0> Calling (GOOD-ENOUGH? 1.0 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 5.0D+28 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.5D+28 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.25D+28 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 6.25D+27 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.125D+27 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.5625D+27 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 7.8125D+26 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.90625D+26 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.953125D+26 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 9.765625D+25 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 4.8828125D+25 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.44140625D+25 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.220703125D+25 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 6.103515625D+24 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.0517578125D+24 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.52587890625D+24 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 7.62939453125D+23 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.814697265625D+23 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.9073486328125D+23 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 9.5367431640625D+22 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 4.76837158203125D+22 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.384185791015625D+22 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.1920928955078126D+22 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 5.960464477539067D+21 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.980232238769542D+21 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.4901161193847878D+21 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 7.450580596924274D+20 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.725290298462808D+20 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.8626451492327463D+20 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 9.313225746190575D+19 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 4.656612873148975D+19 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.3283064366818615D+19 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.1641532185556791D+19 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 5.820766097073363D+18 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.910383057126616D+18 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.4551915457431772D+18 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 7.275958072313265D+17 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.637979723351356D+17 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.8189912360648666D+17 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 9.094983668087334D+16 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 4.547546809403519D+16 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.2738833540922676D+16 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.137161565194354D+16 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 5.690204738559249D+15 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 2.8538893993246385D+15 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 1.444464649808892D+15 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 7.568472253152072D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 4.444871434833608D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.347327645857288D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.167392710266006D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.162281790337874D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.162277660171076D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.162277660168379D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.162277660168379D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
0> Calling (GOOD-ENOUGH? 3.162277660168379D+14 1.0D+29) 
<0 GOOD-ENOUGH? returned NIL
; 以下無限ループ

桁溢れを起こしたり、精度の問題で処理が終わらなかったりする。

もうひとつの戦略を実装するコードは、

(defun sqrt-iter (guess prev-guess x)
  (if (good-enough? guess prev-guess)
      guess
      (sqrt-iter (improve guess x) guess x)))

(defun improve (guess x)
  (average guess (/ x guess)))

(defun average (x y)
  (/ (+ x y) 2))

(defun good-enough? (guess prev-guess)
  (< (abs (- 1.0 (/ guess prev-guess))) 0.001))

(defun mysqrt (x)
  (sqrt-iter 1.0 x x))

結果は、

CL-USER> (mysqrt 0.0001)
0.01
CL-USER> (mysqrt 1.0d29)
3.162277660171076D+14

小さな数でも大きな数でも正常に動作する。good-enough?のアルゴリズムの変更によって、桁溢れも起こらない。

問題1.6

new-ifは手続きなので、predicateの結果に関わらず、then-clauseとelse-clauseが評価される。そのため、new-ifによって定義されたsqrt-iterでは、else-clauseにあたるsqrt-iterの呼び出しが、good-enough?の結果に関わらずに評価されてしまい、それによって評価が終了しない。

問題1.1

• 10
• 12
• 8
• 3
• 6
• 実装依存
• 実装依存
• 19
• nil
• 4
• 16
• 6
• 16

問題1.2

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
   (* 3 (- 6 2) (- 2 7)))

問題1.3

(defun f (x y z)
  (if (< x y)  
      (if (< x z)
          (+ (* y y) (* z z))
          (+ (* x x) (* y y)))
      (if (< y z)
          (+ (* x x) (* z z))
          (+ (* x x) (* y y)))))

問題1.4

bが正の場合、手続き+を引数aとbに作用させ、そうでない場合、手続き-を引数aとbに作用させる。

問題1.5

作用的順序で評価する解釈系の場合、testを作用させる前に引数の(p)が評価されるが、pの定義により評価が終了しない。

正規順序で評価する解釈系の場合、testが簡約され、その結果ifが評価されるが、ifの評価規則により0が評価され、結果は0になる。(p)は評価されない。

動機

積んでいたSICPを読むにあたって、練習問題の回答を記録しておきたかったのと、読んで思ったことを書き留めておきたかったので、ブログ形式で残しておこうという試み。Common Lisp勉強中につき、敢えてCommon Lispで。