SICP 読書ノート#37 - 3.5.2 無限ストリーム(2) (pp.196-197)
問題 3.59
べき級数、聞き覚えはあるから習ったことはあるんだろうけど、さっぱり思い出せない。こんな時はWikipedia。先生いつもありがとう。
(a)
べき級数の項のストリームを引数に取り、それを積分した結果の項のストリームを返すintegrate-seriesを実装する。
引数のストリームを \( \{s_{n}\} \) とすると、
- \( i_{0} = s_{0} \)
- \( i_{1} = \frac{1}{2} s_{1} \)
- \( i_{2} = \frac{1}{3} s_{2} \)
- \( i_{3} = \frac{1}{4} s_{3} \)
- ...
- \( i_{k} = \frac{1}{k} s_{k} \)
のようなストリームを返す手続きを実装すればよいので、
(define (integrate-series s) (define (iter s k) (cons-stream (/ (stream-car s) k) (iter (stream-cdr s) (+ k 1)))) (iter s 1))
テスト。
racket@> (define i (integrate-series ones)) racket@> (map (lambda (x) (stream-ref i x)) (enumerate-interval 0 5)) => '(1 1/2 1/3 1/4 1/5 1/6)
(b)
まずはexp-seriesを動かしてみる。
(define exp-series (cons-stream 1 (integrate-series exp-series))) ;; test racket@> (map (lambda (x) (stream-ref exp-series x)) (enumerate-interval 0 5)) => '(1 1 1/2 1/6 1/24 1/120)
確かに、
\( e^{x} = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots \)
の定義通り \( k \) 番目の項が \( \frac{1}{k!} \) となっている。うーん、すごい。
次にcos、sinの級数の式について、
\( \cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \dots \)
\( \sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \dots \)
それぞれ積分してみると、
\( \int \cos x = x - \frac{x^3}{3!} + \frac{5^4}{5!} - \dots = \sin x \)
\( \int \sin x = \frac{x^2}{2!} - \frac{x^4}{4!} + \frac{x^6}{6!} - \dots = 1 - \cos x \)
より、
\( \cos x = 1 - \int \sin x \)
\( \sin x = \int \cos x \)
となるので、この定義をそのまま実装する。
(define cosine-series (cons-stream 1 (scale-stream (integrate-series sine-series) -1))) (define sine-series (cons-stream 0 (integrate-series cosine-series)))
テスト。元々のべき級数の式と同じになる。
racket@> (map (lambda (i) (stream-ref cosine-series i)) (enumerate-interval 0 10)) => '(1 0 -1/2 0 1/24 0 -1/720 0 1/40320 0 -1/3628800) racket@> (map (lambda (i) (stream-ref sine-series i)) (enumerate-interval 0 10)) => '(0 1 0 -1/6 0 1/120 0 -1/5040 0 1/362880 0)
問題 3.60
2つのべき級数の項のストリームをそれぞれ \( \{ a_{n} \} \) 、\( \{ b_{n} \} \) とすると、2つのべき級数の積の項のストリームは、
- \( m_{0} = a_{0} * b_{0} \)
- \( m_{1} = a_{0} * b_{1} + a_{1} * b_{0} \)
- \( m_{2} = a_{0} * b_{2} + a_{1} * b_{1} + a_{2} * b_{0} \)
- \( m_{3} = a_{0} * b_{3} + a_{1} * b_{2} + a_{2} * b_{1} + a_{3} * b_{0} \)
- ...
となる。
問題の穴埋めについて
(define (mul-series s1 s2) (cons-stream ⟨??⟩ (add-streams ⟨??⟩ ⟨??⟩)))
\( m_{0} \) より最初の<??>は自明。
(* (stream-car s1) (stream-car s2))
2、3番目の<??>はadd-streamsの引数となるので、
(add-streams <??> (mul-series <??> <??>))
のように畳み込みながら足すイメージなんだけど、全然思いつかず…
1〜2日寝かせて、図を凝視していたら分かった。
- \( m_{0} = a_{0} * b_{0} \)
- \( m_{1} = a_{0} * b_{1} + a_{1} * b_{0} \)
- \( m_{2} = a_{0} * b_{2} + a_{1} * b_{1} + a_{2} * b_{0} \)
- \( m_{3} = a_{0} * b_{3} + a_{1} * b_{2} + a_{2} * b_{1} + a_{3} * b_{0} \)
- ...
- \( m = a_{0} * \{ b_{n} \} + a_{1} * \{ b_{n} \} + a_{2} * \{ b_{n} \} + a_{3} * \{ b_{n} \} + \dots \)
上の図の通りに実装。
(define (mul-series s1 s2) (cons-stream (* (stream-car s1) (stream-car s2)) (add-streams (scale-stream (stream-cdr s2) (stream-car s1)) (mul-series (stream-cdr s1) s2))))
テスト。
racket@> (map (lambda (i) (stream-ref (mul-series integers integers) i)) (enumerate-interval 0 5)) => '(1 4 10 20 35 56)
ｷﾀ━(ﾟ∀ﾟ)━!
問題 3.61-62
問題3.60と同様、ほとんど数学なのでパス。
次回は「§3.5.3 ストリームパラダイムの開発」から。
