my attempt to do the exercises in sicp.

Tuesday, December 21, 2010

sicp exercise 3.65

;; Exercise 3.65.  Use the series

;; to compute three sequences of approximations to the natural logarithm of 2, in the same way we did above for . How rapidly do these sequences converge?

(define count 0)

(define (euler-transform s)
  (let ((s0 (stream-ref s 0))           ; Sn-1
        (s1 (stream-ref s 1))           ; Sn
        (s2 (stream-ref s 2)))          ; Sn+1
    (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)))

(define (partial-sums s)
  (define result (cons-stream (stream-ref s 0)
                              (add-streams (stream-cdr s) result)))

(define (add-streams s1 s2)
  (stream-map + s1 s2))

(define (stream-limit stream tolerance)
  (define (iter initial-value str)
    (let ((s (stream-car str)))
      (if (> tolerance (abs (- s initial-value))) s
          (iter s (stream-cdr str)))))
  (iter (stream-car stream) (stream-cdr stream)))
(define (incr n)
  (set! count (+ count 1))
  (+ 1 n))
(define (ln-2-summands n)
  (cons-stream (/ 1.0 n)
               (stream-map - (ln-2-summands (incr n)))))
(define ln-2-stream
  (partial-sums (ln-2-summands 1)))

(define acc-ln-2-stream (accelerated-sequence euler-transform (partial-sums (ln-2-summands 1))))

;; Value of ln 2 from wolfram alpha:

(display (stream-limit ln-2-stream 0.0001))(newline)
(display count)(newline)
(set! count 0)
(display (stream-limit acc-ln-2-stream 0.00001))(newline)
(display count)(newline)

;; Output:
;Loading "sicp_prob_03.65.scm"...
;... done

No comments: