1.2.3 Orders of Growth 〜 1.2.5 Greatest Common Divisors

1.2.3 〜 1.2.5は、例題によって理解を深める節。1.2.6も例題だけど、えらく長いので1.2.6は別に分ける。

1.2.3 Orders of Growth

問題の大きさに伴って、空間計算量と時間計算量がどのように増えていくかをΘ記法を用いて説明したもの。具体的なΘ記法の説明は無かったけど、要するにf(x)=O(g(x)), g(x)=O(f(x))を満たす時、g(x)=Θ(f(x))となる。より具体的には、f(x)とg(x)の差が定数倍程度に収まる事を表す。ランダウの記法の中では、最も条件が狭い。

Exercise 1.14

11セントのお釣りを支払う組み合わせを求める様子を描画する問題。ツリーを描けと言われているけども、面倒なのでprocedureが呼ばれる様子を列挙。

(cc 11 5)
 (cc 11 4)
  (cc 11 3)
   (cc 11 2)
    (cc 11 1)
     (cc 11 0)
     (cc 10 1)
      (cc 10 0)
      (cc 9 1)
       (cc 9 0)
       (cc 8 1)
        (cc 8 0)
        (cc 7 1)
         (cc 7 0)
         (cc 6 1)
          (cc 6 0)
          (cc 5 1)
           (cc 5 0)
           (cc 4 1)
            (cc 4 0)
            (cc 3 1)
             (cc 3 0)
             (cc 2 1)
              (cc 2 0)
              (cc 1 1)
               (cc 1 0)
               (cc 0 1)
    (cc 6 2)
     (cc 6 1)
      (cc 6 0)
      (cc 5 1)
       (cc 5 0)
       (cc 4 1)
        (cc 4 0)
        (cc 3 1)
         (cc 3 0)
         (cc 2 1)
          (cc 2 0)
          (cc 1 1)
           (cc 1 0)
           (cc 0 1)
     (cc 1 2)
      (cc 1 1)
       (cc 1 0)
       (cc 0 1)
      (cc -4 2)
   (cc 1 3)
    (cc 1 2)
     (cc 1 1)
      (cc 1 0)
      (cc 0 1)
     (cc -4 2)
    (cc -9 3)
  (cc -14 4)
 (cc -39 5)

…長い。

Exercise 1.15

問A

1回のsineの適用につきangleが1/3になっているから、angleの値の変遷は次行のようになる。
12.15 -> 4.05 -> 1.35 -> 0.45 -> 0.15 -> 0.05
但し、最後のangle=0.05の時だけpは呼び出されないので、結果的にpは5回適用される。

問B

number of stepsは　　を解けば、。よって、。Θ記法で表すとΘ(log(a))となる。
spaceも同じ。なぜなら、sineの1回の適用でsineの結果を1つだけ保持する必要があるから。

1.2.4 Exponentiation

累乗を求めるprocedureを、recursive processとiterative processの両方で作成。さらにtree recursionを用いる事によって、計算量をlogのオーダーまで落とした。
この節はやけに短いなと思ったら、その分Exerciseが豊富にあった。

Exercise 1.16

iterative processでexponentiationを求めるプログラムを書けという問題。

(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 (* b b) (/ n 2)))
        (else (fast-expt-iter (* a b) (* b b) (/ (- n 1) 2)))))

Exercise 1.17

(define (double x) (* x 2))
(define (halve x) (/ x 2))
(define (fast-mult a b)
  (cond ((= b 1) a)
        ((even? b) (double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (+ b -1))))))

Exercise 1.18

(define (double x) (* x 2))
(define (halve x) (/ x 2))
(define (fast-mult a b)
  (fast-mult-iter a b a))
(define (fast-mult-iter a b c)
  (cond ((= b 1) a)
        ((even? b) (fast-mult-iter (double a) (halve b) c))
        (else (fast-mult-iter (+ (double a) c) (halve (+ b -1)) c))))

Exercise 1.19

T(a, b)=(a+b, a) と Tpq(a, b)=(bq+aq+bp, bp+aq) の係数を比較すると、n=1の時にp=0, q=1である事が分かる。同様にT^2とTpq^2を比較すると、n=2の時にp=1, q=1。同様にT^nとTpq^nを比較すると、pとqの間には(p',q')=(q,p+q)という関係がある事が分かる。これをn=2の時に適用すると、p''=p+q, q''=p+2qである事が分かる。これがcountが偶数の時のpとqを更新する式になる。

(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 q)
                   (+ q p q)
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

1.2.5 Greatest Common Divisors

ユークリッドの互除法を使って、最大公約数を求めるプログラムの例。最後にラメの定理を使って計算量の増加量を見積もった。

Exercise 1.20

normal-order evaluation

; コメント中に、その行で評価されたremainderを示す。
; 但し、略記の為に(remainder x y)を(x y)と表している。
(gcd 206 40)

;; remainder評価回数 0回
(if (= 40 0)
    206
    (gcd 40 (remainder 206 40)))

;; remainder評価回数 1回
(if (= (remainder 206 40) 0)  ;; (206 40) performed
    40
    (gcd (remainder 206 40) (remainder 40
                                       (remainder 206 40))))

;; remainder評価回数 2回
(if (= (remainder 40
                  (remainder 206 40))
       0)  ;; (206 40), (40 6) performed
    (remainder 206 40)
    (gcd (remainder 40
                    (remainder 206 40))
         (remainder (remainder 206 40)
                    (remainder 40
                               (remainder 206 40)))))

;; remainder評価回数 4回
(if (= (remainder (remainder 206 40)  ;; (206 40), (6 4) performed
                  (remainder 40  ;; (40 6) performed
                             (remainder 206 40))) 0)  ;; (206 40) performed
    (remainder 40
               (remainder 206 40))
    (gcd (remainder (remainder 206 40)
                    (remainder 40
                               (remainder 206 40)))
         (remainder (remainder 40
                               (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40
                                          (remainder 206 40))))))

;; remainder評価回数 7回
(if (= (remainder (remainder 40  ;; (40 6), (4 2) performed
                             (remainder 206 40))  ;; (206 40) performed
                  (remainder (remainder 206 40)  ;; (206 40), (6 4) performed
                             (remainder 40  ;; (40 6) performed
                                        (remainder 206 40)))) 0)  ;; (206 40) performed
    (remainder (remainder 206 40)
               (remainder 40
                          (remainder 206 40)))
    (gcd ...  ; else節は評価されないので省略

;; remainder評価回数 4回
(remainder (remainder 206 40)  ;; (206 40), (6 4) performed
           (remainder 40  ;; (40 6) performed
                      (remainder 206 40)))  ;; (206 40) performed

;; remainder評価回数 0回 (結果)
2

この様に評価されていき、結果remainderは18回評価される。

applicative-order evaluation

(gcd 206 40)

;; remainder評価回数 1回
(if (= 40 0)
    206
    (gcd 40 (remainder 206 40)))  ;; (206 40) performed

;; (gcd 40 6)
;; remainder評価回数 1回
(if (= 6 0)
    40
    (gcd 6 (remainder 40 6)))  ;; (40 6) performed

;; (gcd 6 4)
;; remainder評価回数 1回
(if (= 4 0)
    6
    (gcd 4 (remainder 6 4)))  ;; (6 4) performed

;; (gcd 4 2)
;; remainder評価回数 1回
(if (= 2 0)
    4
    (gcd 2 (remainder 4 2)))  ;; (4 2) performed)

;; (gcd 2 0)
;; remainder評価回数 0回
(if (= 0 0)
    2
    (gcd 0 (remainder 2 0)))

;; remainder評価回数 0回 (結果)
2

この様に評価され、結果remainderは4回評価される。