SICPゼミ第28回

練習問題3.63

Reasoner の方法では毎回新しい sqrt-stream (lambda closure の中) を作り出してひとつめの項から計算し直しているので、実質メモ化を行っていないのと同じで、無駄な計算が多くなる。

by tube

練習問題3.64

(define (stream-limit stream tolerance)
  (define (abs x)
    (if (< x 0)
        (* x -1)
        x))
  (if (< 
        (abs 
          (- (stream-car stream)
             (stream-car (stream-cdr stream))))
        tolerance)
      (stream-car (stream-cdr stream))
      (stream-limit (stream-cdr stream) tolerance)))

by pine

練習問題3.65

(define (stream-limit stream tolerance count)
  (define (abs x)
    (if (< x 0)
        (* x -1)
        x))
  (if (< 
        (abs 
          (- (stream-car stream)
             (stream-car (stream-cdr stream))))
        tolerance)
      (begin 
        (display count)
        (newline)
        (stream-car (stream-cdr stream)))
      (stream-limit (stream-cdr stream) tolerance (+ count 1))))

これで何ステップかかったか表示できる

(define (ln2-summands n)
  (cons-stream (/ 1.0 n)
               (stream-map - (ln2-summands (+ n 1)))))

(define ln2-stream
  (partial-sums (ln2-summands 1)))


(define (euler-transform s)
  (let ((s0 (stream-ref s 0)) 
        (s1 (stream-ref s 1)) 
        (s2 (stream-ref s 2))) 
    (cons-stream (- s2 (/ (square (- s2 s1))
                          (+ s0 (* -2 s1) s2)))
                 (euler-transform (stream-cdr s)))))

(define (make-tableau transform s)
  (cons-stream s (make-tableau transform (transform s))))

(define (accelerated-sequence transform s)
  (stream-map stream-car (make-tableau transform s)))

本体

gosh> (stream-limit ln2-stream 0.01 1)
100
0.6980731694092049
gosh> (stream-limit (euler-transform ln2-stream) 0.01 1)
1
0.6904761904761905
gosh> (stream-limit (euler-transform ln2-stream) 0.000001 1)
61
0.6931466925212173
gosh> (stream-limit (accelerated-sequence euler-transform ln2-stream) 0.000001 1)
5
0.6931471806635636

実行結果
by pine

回数指定で display させてみた。

(define (display-stream-count s count)
  (if (> count 0)
      (begin (display-line (stream-car s))
             (display-stream-count (stream-cdr s) (- count 1)))
      (newline)))

ふつうのやつ。

> (display-stream-count log-stream 10)

1.0
0.5
0.8333333333333333
0.5833333333333333
0.7833333333333332
0.6166666666666666
0.7595238095238095
0.6345238095238095
0.7456349206349207
0.6456349206349207

もっと先へ、<<加速>>したくはないか？
列加速の世界へ！！！！

> (display-stream-count (euler-transform log-stream) 10)

0.7
0.6904761904761905
0.6944444444444444
0.6924242424242424
0.6935897435897436
0.6928571428571428
0.6933473389355742
0.6930033416875522
0.6932539682539683
0.6930657506744464

超加速の世界へ！！！！！！！

> (display-stream-count (accelerated-sequence euler-transform log-stream) 10)

1.0
0.7
0.6932773109243697
0.6931488693329254
0.6931471960735491
0.6931471806635636
0.6931471805604039
0.6931471805599445
0.6931471805599427
0.6931471805599454

by tube

練習問題3.66

(define (search-stream stream search count)
  (if (stream-null? stream)
      'Done
      (if (and (= (car (stream-car stream)) (car search)) (= (cadr (stream-car stream)) (cadr search)))
          count
          (search-stream (stream-cdr stream) search (+ count 1)))))

とりあえず数えるの
by pine

一般的な(n, m) について回数を求める式です。