SICPを読む_(8)1章_手続きによる抽象の構築(p23-26)

今日はできればp30まで書きたい。ということでノロノロ書いていきます。

1.2.3増加の程度(p23-24)

• 計算の資源を消費する速度について考える。
• プロセスの入力が大きくなるにつれて必要とする資源を、粗く見積る「増加の程度」を考える。

最近の若者はアルゴリズムなんて知らないし(僕です)、マシンパワーに任せてメモリの消費が激しいプログラム書くし(僕です)、計算に使える資源が有限だということを改めて認識しながら勉強していきましょう(僕です)。

1. nを問題の大きさを表すパラメタ
2. R(n)を大きさnの問題に対してプロセスが必要とする資源の量とする

で、一定時間内に決まった数の演算しか出来ない計算機(つまりコンピュータ)の場合、必要な時間は実行した基本機械演算に比例する。

十分大きなnの値に対し,
k1×f(n) <= R(n) <= k2×f(n)
なるnと独立な正の定数k1,k2があれば,R(n)はθ(f(n))の増加の程度だといい、R(n)=θ(f(n))と書く.

階乗計算の線形再帰プロセスはnに比例して増加するので、ステップ数はθ(n)で増加する。必要なスペースもθ(n)で増加した。
反復的階乗ではステップ数はθ(n)だが、スペースはθ(1)だった。

といった感じで、増加の程度を大雑把に把握しておくと後の計算にかかる時間などがおおまかに分かると。

問題1.14(p24)

これは略でいいかな??先日既に10セントで書いちゃったし。

問題1.15(p24)

aは5回だけど、bがいまいちわからない。ちょっとこれは後回しにして、そのうち考えるとする。

1.2.4べき乗(p24-25)

ここで書かれてる逐次平方については、アルゴリズム・サイエンスにも書いてありましたね。

アルゴリズム・サイエンス:入口からの超入門 (アルゴリズム・サイエンスシリーズ―超入門編)

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

(define (fast-expt b n)
  (cond
   ((zero? n) 1)
   ((even? n) (square (fast-expt b (/ n 2))))
   (else
    (* b (fast-expt b (- n 1))))))

• 対数難しい(ぇ
• Θ(log n)とΘ(n)の増加の差はnが大きくなるほど大きくなる
• 反復的プロセスは再帰的プロセスのように直截的に書けない

ここはそんなに難しいことは書いてないのでさくっと。

問題1.16(p26)

• (b^(n/2))^2 = (b^2)^(n/2)
  • 偶数のとき => b^n = (b^2)^(n/2)
  • 奇数のとき => b^n = b*b^(n-1)
• ヒントよりaは初期値1らしい

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

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

(define (expt-iter a b n)
  (cond
   ((zero? n) a)
   ((even? n) (expt-iter a (square b) (/ n 2)))
   (else
    (expt-iter (* a b) b (- n 1)))))

(expt 5 5) ;;=>3125

だと思う。たぶんあってる気がする。

問題1.17(p26)

• 「この言語に加算はあるが乗算はないものとする」らしい

こんな感じかな。そんなに難しくないというか、fast-exptままだね。

(define (double x)
  (+ x x))

(define (halve x)
  (/ x 2))

(define (* a b)
  (cond
   ((zero? b) a)
   ((even? b) (* (double a) (halve b)))
   (else
    (+ a (* a (- b 1))))))

問題1.18(p26)

これも深く考える問題じゃない。

;;double,halveは前の問題から引用
(define (* a b)
  (aster-iter a b 0))

(define (aster-iter a b x)
  (cond
   ((zero? b) x)
   ((even? b) (aster-iter (double a) (halve b) x))
   (else
    (aster-iter a (- b 1) (+ x a)))))

問題1.19(p26)

難しい…。久々に数学チックなことやって疲れました。

• a <= a+b
• b <= a

であると。まぁそれは良いとして、適当に問題文を読み進めると

• a <= bq+aq+ap -(1)
• b <= bp+aq -(2)

と書いてある。

そんで、

• (T_pq)^2 = T_p'q' らしい

なので(2)の式に(1),(2)を代入して展開してやる。
すると、

• b = a(q^2+2pq)+b(p^2+q^2)

が分かるので、(2)式より

• p = (p^2+q^2)
• q = (q^2+2pq)

だと分かる寸法。

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond
   ((zero? count) b)
   ((even? count)
    (fib-iter a
	      b
	      (+ (square p) (square q))
	      (+ (square q) (* 2 p q))
	      (/ count 2)))
   (else
    (fib-iter (+ (* b q) (* a q) (* a p))
	      (+ (* b p) (* a q))
	      p
	      q
	      (- count 1)))))

と、疲れたので今日はここまでー。
結局書き始めて1日越しの投稿となりました。しかもp27までしか書けてない(´・ω・｀)