NoSyu의 주저리주저리 :: SICP Exercise 연습문제 3.82

이 문제는 연습문제 3.5에서 만든 몬테 카를로 적분(Monte Carlo integration)을

스트림 방식으로 만든 것입니다.

역시 rand-update 프로시저가 없지만

random 프로시저를 여러 번 호출하는 것으로 대신하였습니다.

결과는 나오는군요.^^

결과를 확인하기 위해 넣은 수치는 연습문제 3.5와 같은 수치입니다.

하지만 여전히 해당 값인 28.274333882308139146163790449516가 나오지 않았습니다.

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 461

; stream
(define true (= 0 0))
(define false (= 1 0))

(define (cons-stream a b)
(cons a (delay b)))
(define the-empty-stream '())
(define stream-null? null?)
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

; section 3.5
(define (stream-ref s n)
(if (= n 0)
(stream-car s)
(stream-ref (stream-cdr s) (- n 1))))

(define (stream-for-each proc s)
(if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

(define (display-stream s)
(stream-for-each display-line s))

(define (display-line x)
(newline)
(display x))

(define (stream-enumerate-interval low high)
(if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))

(define (stream-filter pred stream)
(cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

(define (memo-proc proc)
(let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

(define (scale-stream stream factor)
(stream-map (lambda (x) (* x factor)) stream))

; exercise 3.50
(define (stream-map proc . argstreams)
(if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream
       (apply proc (map stream-car argstreams))
       (apply stream-map
              (cons proc (map stream-cdr argstreams))))))

;;;SECTION 3.5.2
(define (add-streams s1 s2)
(stream-map + s1 s2))

(define ones (cons-stream 1 ones))
(define integers (cons-stream 1 (add-streams ones integers)))

; exercise 3.54
(define (mul-streams s1 s2)
(stream-map * s1 s2))

; exercise 3.55
(define (partial-sums S)
(cons-stream (stream-car S) (add-streams (stream-cdr S)
(partial-sums S))))

; exercise 3.56
(define (merge s1 s2)
(cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream s1car (merge (stream-cdr s1) s2)))
                 ((> s1car s2car)
                  (cons-stream s2car (merge s1 (stream-cdr s2))))
                 (else
                  (cons-stream s1car
                               (merge (stream-cdr s1)
                                      (stream-cdr s2)))))))))

; print-stream-n
(define (print-stream-n S n l)
(define (iter i)
    (if (= i n)
        'done
        (begin (display (stream-ref S i))
               (display "   ")
               (if (= (remainder (+ i 1) l) 0)
                   (newline))
               (iter (+ i 1)))))
(iter 0))

; exercise 3.77
(define (integral delayed-integrand initial-value dt)
(define (int integrand initial-value)
    (cons-stream initial-value
                 (if (stream-null? integrand)
                     the-empty-stream
                     (int (stream-cdr integrand)
                          (+ (* dt (stream-car integrand))
                             initial-value)))))
(int (force delayed-integrand) initial-value))

; section 3.5.5
(define random-numbers
(cons-stream random-init
(stream-map rand-update random-numbers)))

(define cesaro-stream
(map-successive-pairs (lambda (r1 r2) (= (gcd r1 r2) 1))
random-numbers))

(define (map-successive-pairs f s)
(cons-stream
(f (stream-car s) (stream-car (stream-cdr s)))
(map-successive-pairs f (stream-cdr (stream-cdr s)))))

(define (monte-carlo experiment-stream passed failed)
(define (next passed failed)
    (cons-stream
     (/ passed (+ passed failed))
     (monte-carlo
      (stream-cdr experiment-stream) passed failed)))
(if (stream-car experiment-stream)
      (next (+ passed 1) failed)
      (next passed (+ failed 1))))

(define pi
(stream-map (lambda (p) (sqrt (/ 6 p)))
(monte-carlo cesaro-stream 0 0)))

; exercise 3.82
(define (square x) (* x x))

(define (random-in-ranges low high)
(let ((range (- high low)))
(cons-stream (+ low (random range))
(random-in-ranges low high))))

(define (estimate-integral Ps x1 x2 y1 y2)
(define in-P-test
(Ps (random-in-ranges x1 x2) (random-in-ranges y1 y2)))
(stream-map (lambda (p) (* p (- x2 x1) (- y2 y1))) (monte-carlo in-P-test 0 0)))

(define (P-stream x-stream y-stream)
(stream-map
   (lambda (x y) (<= (+ (square (- x 5)) (square (- y 7))) (square 3)))
   x-stream
   y-stream))

; execute
(define ei (estimate-integral P-stream 2 8 4 10))
;(print-stream-n ei 50 5)
(stream-ref ei 10)
(stream-ref ei 100)
(stream-ref ei 1000)
(stream-ref ei 10000)
(stream-ref ei 20000)
(stream-ref ei 30000)
(stream-ref ei 40000)
(stream-ref ei 50000)
(stream-ref ei 60000)
(stream-ref ei 70000)
(stream-ref ei 80000)
(stream-ref ei 90000)
(stream-ref ei 100000)