社内SICP勉強会(第4回) - 元データ分析の会社で働いていた人の四方山話

第３回の話題

- 末尾再帰はどの処理系でも必ずしもデフォルトで有効ではない

(追記)
勉強会で出た話はLispの実装系についての話でした。
Schemeでは有効のようです。

範囲

P23 1.2.3 増加の程度からP26 問題1.9まで

内容

1.2.3 増加の程度
- 階乗計算の線形再帰的プロセスのステップ数は、入力nに比例して増加する。
  - プロセスの必要とするステップ数はΘ(n)で増加。必要なスペースもΘ(n)で増加
- 反復的階乗では、ステップ数はΘ(n)、スペースはΘ(1)
- 木構造のFibonacci計算はΘ(\phi^n)ステップと、Θ(n)のスペース
- 増加の程度はプロセスの振る舞いのおおよその記述しか与えない
1.2.4 ベキ乗
- ベキ乗を題材にプロセスとステップの話

問題

問題1.14

スペースは木構造の深さに比例する。
- 最大の深さは全て1セントで両替したとき ⇒ nセントの両替にはσ(n)で増加する。
ステップ数について

(count-change 11)⇒(cc 11 5)であるから、(cc 11 5)について考えていく

一旦、(cc n 5)として、考える。

(cc n 5)の手続き呼び出しから計算ステップについては、
(cc n 5) => 1 + (cc n 4) + (cc n-50 5)
となる。同様に、各コインの種類の場合を考えると

- (cc n 4) => 1 + (cc n 3) + (cc n-25 4)
- n(cc n 3) => 1 + (cc n 2) + (cc n-10 3)
- (cc n 2) => 1 + (cc n 1) + (cc n-5 2)
- (cc n 1) => 1 + (cc n 0) + (cc n-1 1)

ここで、(cc n 0)は0を返す終了条件である。(両替対象はまだ残っているが、コインがなくなってしまった状態)
再帰が終了するための条件はである(cc n 0)を作るのは(cc n 1)であるから、それぞれの計算ステップを考えていく
(cc n 0) => 1
(cc n 1) => 1 + 1 + (cc n-1 1)
今度は、(cc n-1 1)について考えていく
(cc n-1 1) => 1 + (cc n-1 0) + (cc n-2 1)
これを一般化して考えていくと、(cc n 1)の形が終了するためには、ccの１番目の引数が(n-n)の形式になることである。

- (cc n-n 1) => 1
- (cc n-(n-1) 1) => 1 + (cc 1 0) + (cc n-(n-1)-1 1) => 1 + 1 + 1 = 3
- (cc n-(n-2) 1) => 1 + (cc 2 0) + (cc n-(n-2)-1 1) => 1 + 1 + 3 = 5
- (cc n-(n-3) 1) => 1 + (cc 3 0) + (cc n-(n-3)-1 1) => 1 + 1 + 5 = 7
- (cc n-(n-4) 1) => 1 + (cc 4 0) + (cc n-(n-4)-1 1) => 1 + 1 + 7 = 9

一般化して

- (cc n-(n-n) 1) => 1 + (cc n 0) + (cc n-(n-n)-1 1) => 1 + 1 + (2n-1) = 2n+1

となり、一般項は2n + 1
(cc n 1)の計算ステップは2n+1であると言え、展開されていく一つの枝の計算ステップは2n+1であることが理解できる。
(cc n 1)は計算が終了するための一つの形である。

続いて、コインの種類が2つ(1セントと5セント)の場合を考える。
- (cc n 2) => 1 + (cc n 1) + (cc n-5 2)

となる。
(cc n-5 2)の枝の展開をさらに考えると

- (cc n-5 2) => 1 + (cc n-5 1) + (cc n-10 2)

となる。この右端の枝の展開は、nが0以下になるまで（ちょうど両替できるか、もしくはうまく両替できないか判明するまで）繰り返される。
この繰り返しは、おおざっぱに見積もってn/5回となる。(一度の両替で5ずつ減っていくから)
繰り返し毎に(cc n 1)の枝が出現し、こちらは2n+1回のステップと見積もれる(Θ記法ではΘ(n))だから、計算ステップは $\frac{n^2}{5}$ となる。
Θ記法では $\theta (n^2)$ となる。

同様に(cc n 3)の時を考えると

- (cc n 3) => 1 + (cc n 2) + (cc n-10 3)

となる。真ん中の枝は先ほど見積もったステップ数を用いて $\frac{n^2}{5}$ 、右端の枝は大雑把に見積もって $\frac{n}{10}$ 回のステップとなる。
掛け合わせて $\frac{n^3}{50}$ ステップずつ増えていく。(Θ記法では $\theta (n^3)$ )

同様に考えて、５つの種類のコインの場合は $\theta (n^5)$

問題1.15

a. 手続きpが作用させられた回数

;; 問題1.15
(define (cube x)
  (* x x x))

(define (p x)
  (- (* 3 x)
     (* 4 (cube x))))

(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

(use slib)
(require 'trace)
(trace sine)
(trace p)

(sine 12.15)

;; a. 手続きpが何回作用させられたか
;; 5回
;;gosh> CALL sine 12.15
;;  CALL sine 4.05
;;    CALL sine 1.3499999999999999
;;      CALL sine 0.44999999999999996
;;        CALL sine 0.15
;;          CALL p 0.049999999999999996
;;          RETN p 0.1495
;;        RETN sine 0.1495
;;        CALL p 0.1495
;;        RETN p 0.4351345505
;;      RETN sine 0.4351345505
;;      CALL p 0.4351345505
;;      RETN p 0.9758465331678772
;;    RETN sine 0.9758465331678772
;;    CALL p 0.9758465331678772
;;    RETN p -0.7895631144708228
;;  RETN sine -0.7895631144708228
;;  CALL p -0.7895631144708228
;;  RETN p -0.39980345741334
;;RETN sine -0.39980345741334
;;-0.39980345741334

b. スペースとステップの増加の見積もり

(sine a)はaを3でn回割って、0.1以下になれば終了という実装なので
$\frac{a}{3^n} \le 0.1$
両辺を底が3の $\log$ を取ると
$\log_{3} a - \log_{3} 3^n \le \log_{3} 0.1$
$n \ge \log_{3} a - \log_{3} 0.1$
$n \ge \log_{3} a + \log_{3} 10$
である。
以上から、 $\theta ( \log_{3} a )$

問題1.16

;; 問題1.16
;; 逐次平方による反復的ベキ乗プロセスの手続き

(define (fast-expt b n)
  (fast-expt-iter 1 b n))

(define (fast-expt-iter a b n)
  (cond [(= n 0) a]
     [(even? n) (fast-expt-iter a (square b) (/ n 2))]
     [else (fast-expt-iter (* b a) b (- n 1))]))

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

(define (square n)
  (* n n))

問題1.17

;; 問題1.17
;; bが0なら0を返す
;; bが偶数なら結果を２倍させつつ、bを半分にしてfast-multiを再度呼び出し
;; bが奇数なら結果にaを足して、bを1減らしてfast-multiを再度呼び出し
(define (fast-multi a b)
  (cond [(= b 0) 0]
     [(even? b) (double (fast-multi a (halve b)))]
     [else (+ a (fast-multi a (- b 1)))]))

(define (double n)
  (* n 2))

(define (halve n)
  (/ n 2))

問題1.18

;; 問題1.18
;; 問題1.17で実装した対数的ステップ数の乗算を反復的プロセスで実装
(define (fast-multi a b)
  (fast-multi-iter a b 0))

(define (fast-multi-iter a b n)
  (cond [(= b 0) n]
     [(even? b) (fast-multi-iter (double a) (halve b) n)]
     [else (fast-multi-iter a (- b 1) (+ a n))]))

(define (double n)
  (* n 2))

(define (halve n)
  (/ n 2))

問題1.19

$a_1 = bq + aq + ap$
$b_1 = bp + aq$
として、 $a_2 = b_1 q + a_1 q + a_1 p$ , $b_2 = b_1 p + a_1 p$ を展開して、まとめればよい。
整理すると、
$a_2 = b(pq + pq + qq) + a(pq + pq + qq) + a(qq + pp)$
$b_3 = b(pp + qq) + a(pq + pq + qq)$
となるから、
$p' = pp + qq$
$q' = 2pq + qq$
となる。

;; 問題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))]))

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

;;gosh> (fib 0)
;;0
;;gosh> (fib 1)
;;1
;;gosh> (fib 2)
;;1
;;gosh> (fib 3)
;;2
;;gosh> (fib 4)
;;3

所感

今週はバタバタしてて時間が取れなかったのでギリギリですね。