SICP 読み (3)

scheme SICP

このエントリは果たして大晦日中に投入できるのだろーか、と思ひつつ下書きを書いてます。
と、ゆー事で問題 1.11 〜 13 はスルー。特に Pascal's triangle はハマリまくってるだけに惜しい。ってか答え見たい。(別途検討してログ投入予定ッス
ここから以降は 2 章に行くまでに興味深いテーマ多し。(がしかし、スルーも多いぞ

問題 1.16

あら、これは参考になるな。

最初の fast-expt

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

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

で、状態を管理する変数 a を使って反復なナニを、という事で以下のような状態を表現すれば良いのね、と。

  • 最初
    • a は b ^ 0 (1)
    • b ^ n
    • a * b ^ n = 1 * b ^ n
  • 二回目
    • a は b ^ 1
    • b ^ (n - 1)
    • a * b ^ (n - 1) = b * b ^ (n - 1)
  • 三回目
    • a は b ^ 2
    • b ^ (n - 2)
    • a * b ^ (n - 2) = (b * b) * b - (n - 2)

で、最終的に n が 0 になったら a に b ^ n が格納されている、という手ハズですか。実装は以下ッス。

(define (fast-expt2 b n)
  (let f ((b b) (n n) (a 1))
    (cond ((= n 0) a)
	  (else (f b (- n 1) (* a b))))))

問題 1.17

これ、問題の意図を分かりかねとるんですが、_このアルゴリズムは b に線型のステップ数を_ってどーゆー意味だろ。とりあえず double と halve を使って fast-expt 的なナニを作るにはどうすれば良いやら。

直前の問題のソレによれば
(* a b)
は
(* 2 (* a (/ b 2))) ;; 2a(b/2)
と表現できるか。
例えば、(* 3 4) の場合だと
(* 2 (* 3 (/ 4 2))) ;; => (2 * (3 * 2))
あるいは (* 5 6) の場合だと
(* 2 (* 5 (/ 6 2))) ;; => (2 * (5 * 3))

ただし、b が奇数の場合は工夫が必要、と。
(+ a (* 2 (* a (/ (- b 1) 2)))) ;; a + 2a*1 か。
3*5 は 3+(2*(3*2)) から 3+(2*(2*(3*1))) ですか。
では 5*6 は??
2*(5*3) から 2*(5+(5*2)) から 2*(5+(2*(5*1))) で OK ?

てコトは実装としては (define (* b n) として

  • 偶数なら : (double (* b (halve n)))
  • 奇数なら : (+ b (double (* b (halve (- n 1)))))

でええんかの。マイナス演算使ってはダウトなのかなぁ。

こんな感じ??

(define (double n)
  (+ n n))
(define (halve n)
  (/ n 2))

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

(define (* b n)
  (cond ((= n 0) 0)
	((= n 1) b)
	((even? n) (double (* b (halve n))))
	(else (+ b (double (* b (halve (- n 1))))))))

なんかアルゴリズムの検討が微妙です。しかも解はダウトかも。

問題 1.18

1.17 の解はダウトかも、と言いつつ続けてやってみる。奇数だったらプラス、なナニが足枷です。ぶっちゃけこうすれば楽やんに。

(define (* b n)
  (let f ((b b) (n n) (a 0))
    (if (= n 0)
	a
	(f b (- n 1) (+ a b)))))

でも多分上のは解答としてはダウトなはず。
えーと。考え方としては

(b * n) と a                 => (3 * 4) と 0
(b * (n/2)) と 2 * a         => (3 * 2) と (2 * 3)
(b * ((n/2)/2) と 2 * 2 * a  => (3 * 1) と (2 * 6)

か。偶数なモデルは話が早いんよね。これで済めば話は早いんですがしかし奇数だとウマくいかんのよ。足せれば良いんですがね。

(b * n) と a                 => (3 * 4) と 0
(b * (n/2)) と 2 * b + a     => (3 * 2) と (0 + (3 * 2))
(b * ((n/2)/2) と 2 * b + a  => (3 * 1) と (6 + (3 * 2))

あらら。足せちゃった。いいのかな。これだと奇数対応可能だぞ。

(b * n) と a                    => (3 * 5) と 0
(b * (n - 1)) と a + b          => (3 * 4) と (0 + 3)
(b * ((n-1)/2) と 2 * b + a     => (3 * 2) と (3 + 6)
(b * (((n-1)/2)/2) と 2 * b + a => (3 * 1) と (9 + 6)

なんか微妙。(3 * 1) はどうなるんだ。a が 0 なら b 返却、とか反則??
暮れも押しせまっているので以下の実装で勘弁して下さひ。

(define (double n)
  (+ n n))
(define (halve n)
  (/ n 2))

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

(define (* b n)
  (let f ((b b) (n n) (a 0))
    (cond ((= n 0) 0)
	  ((= n 1)
	   (if (= a 0)
	       b
	       a))
	  ((even? n) (f b (halve n) (+ a (double b))))
	  (else (f b (- n 1) (+ a b))))))

今年はここまでが限界かなぁ。
冬休み中に 2 章のケツまで、とゆーのは無理っぽいなぁ。

*1:b-1)/2) 検証 (* 3 5) の場合 (+ 3 (* 2 (* 3 (/ (- 5 1) 2)))) ;; => (3 + (2 * (3 * (4 / 2)))) あるいは (* 5 7) の場合 (+ 5 (* 2 (* 5 (/ (- 7 1) 2)))) ;; => (5 + (2 * (5 * (6 / 2)))) これはこれで OK なんですが、どう収束させるんだろうか。 # てか、再帰使わんでもええ気がするなぁ。 3*4 は 2*(3*2) から 2*(2*(3*1