宿題

前回やったところも一緒に

1.1 省略
1.2 字が潰れてるから省略
1.3

(define (sum-of-squares a b)
  (+ (* a a) (* b b)))

(define (f a b c)
  (if (< a b)
      (if (< c a)
          (sum-of-squares a b)
          (sum-of-squares b c))
      (if (< b c)
          (sum-of-squares c a)
          (sum-of-squares a b))))

1.4 a-plus-abs-b
1.5 applicative-order eval だと，test の引数(p) を先に評価するので，p を無限に再帰する．
normal-order eval だと，p を1回展開して終わり．
1.6 1.5と同じ
1.7 比較する数(今回は，1e-3)よりも元の値の桁がある程度小さければ(ex. 1e-15)ば，
計算を早く切り上げ過ぎる可能性がある．
逆に，元の値が大きければ(ex. 1e15)，表現できる値の誤差により収束しなくなる可能性がある．
課題の場合，小さい数に対しては同様の問題がある．
大きい数に対しては，早めに打ち切ることが可能になる．

(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 (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

(define (sqrt-iter2 guess x)
  (if (good-enough?2 guess (improve guess x))
      guess
      (sqrt-iter2 (improve guess x)
                 x)))

(define (good-enough?2 guess guess-next)
  (< (abs (- guess guess-next)) 0.001))

(define (sqrt2 x)
  (sqrt-iter2 1.0 x))

(define (sqrt-print x)
  (format #t "sqrt2 ~s = ~s\n" x (sqrt2 x))
  (format #t "sqrt  ~s = ~s\n" x (sqrt x))
  )

(let ((x 4))     (sqrt-print x))
(let ((x 1e-15)) (sqrt-print x))
(let ((x 1e15))  (sqrt-print x))

メモ

• ``fully expand and then reduce'' evaluation method is known as normal-order evaluation
• ``evaluate the arguments and then apply'' method that the interpreter actually uses, which is called applicative-order evaluation
• wikipedia:コンピュータの数値表現
• wikipedia:ニュートン法

1.8

(define (square x)
  (* x x))

(define (cube x)
  (* x x x))

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

(define (improve guess x)
  (/ (+ (/ x (square guess)) (* 2 guess)) 3))

(define (good-enough? guess x)
  (< (abs (- (cube guess) x)) 0.001))

(define (cbrt x)
  (cbrt-iter 1.0 x))

(define (cbrt-iter2 guess x)
  (if (good-enough?2 guess (improve guess x))
      guess
      (cbrt-iter2 (improve guess x)
                 x)))

(define (good-enough?2 guess guess-next)
  (< (abs (- guess guess-next)) 0.001))

(define (cbrt2 x)
  (cbrt-iter2 1.0 x))

(define (cbrt-print x)
  (format #t "cbrt2 ~s = ~s\n" x (cbrt2 x))
  (format #t "cbrt  ~s = ~s\n" x (cbrt x))
  )

(let ((x 8))     (cbrt-print x))
(let ((x 1e-15)) (cbrt-print x))
(let ((x 1e15))  (cbrt-print x))

1.9 前者は，再帰的．(inc で遅延計算の列を作るから)
後者は，反復的．(状態変数で定義されているから)

メモ

• 再帰的プロセス(recursive process) - 膨張と収縮，遅延計算(deferred operations)の列
• 反復的プロセス(iterative process) - 状態変数(static variables)

1.10 f=2n
g=2^n
h=2↑↑n