►zthomae’s SICP solutions
▼3 Chapter 3
3.1 Exercise 3.1
3.2 Exercise 3.2
3.3 Exercise 3.3
3.4 Exercise 3.4
3.5 Exercise 3.5
3.6 Exercise 3.6
3.7 Exercise 3.7
3.8 Exercise 3.8
3.9 Exercise 3.9
3.10 Exercise 3.10
3.11 Exercise 3.11
3.12 Exercise 3.12
3.13 Exercise 3.13
3.14 Exercise 3.14
3.15 Exercise 3.15
3.16 Exercise 3.16
3.17 Exercise 3.17
3.18 Exercise 3.18
3.19 Exercise 3.19
3.20 Exercise 3.20
3.21 Exercise 3.21
3.22 Exercise 3.22
3.23 Exercise 3.23
3.24 Exercise 3.24
3.25 Exercise 3.25
3.26 Exercise 3.26
3.27 Exercise 3.27
3.28 Exercise 3.28
3.29 Exercise 3.29
3.30 Exercise 3.30
3.31 Exercise 3.31
3.32 Exercise 3.32
3.33 Exercise 3.33
3.34 Exercise 3.34
3.35 Exercise 3.35
3.36 Exercise 3.36
3.37 Exercise 3.37
3.38 Exercise 3.38
3.39 Exercise 3.39
3.40 Exercise 3.40
3.41 Exercise 3.41
3.42 Exercise 3.42
3.43 Exercise 3.43
3.44 Exercise 3.44
3.45 Exercise 3.45
3.46 Exercise 3.46
3.47 Exercise 3.47
3.48 Exercise 3.48
3.49 Exercise 3.49
3.50 Exercise 3.50
3.51 Exercise 3.51
3.52 Exercise 3.52
3.53 Exercise 3.53
3.54 Exercise 3.54
3.55 Exercise 3.55
3.56 Exercise 3.56
3.57 Exercise 3.57
3.58 Exercise 3.58
3.59 Exercise 3.59
3.60 Exercise 3.60
3.61 Exercise 3.61
3.62 Exercise 3.62
3.63 Exercise 3.63
3.64 Exercise 3.64
3.65 Exercise 3.65
3.66 Exercise 3.66
3.67 Exercise 3.67
3.68 Exercise 3.68
3.69 Exercise 3.69
3.70 Exercise 3.70
3.71 Exercise 3.71
3.72 Exercise 3.72
3.73 Exercise 3.73
3.74 Exercise 3.74
3.75 Exercise 3.75
3.76 Exercise 3.76
3.77 Exercise 3.77
3.78 Exercise 3.78
3.79 Exercise 3.79
3.80 Exercise 3.80
3.81 Exercise 3.81
3.82 Exercise 3.82
    ← prev  up  next → 

3.65 Exercise 3.65

We can define the terms of the series equivalent to the natural logarithm of 2 as follows:

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

We can then define an initial, non-accelerated version of the series converting on the value ln 2 as follows:

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

Using Euler acceleration with euler-transform, we can define an accelerated version of this stream as follows:

(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 ln-stream++ (euler-transform ln-stream))

And using tableau acceleration, we can define a "super"-accelerated stream:

(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 ln-stream# (accelerated-sequence euler-transform ln-stream))

If we want to test how quickly these streams converge on the correct value of ln 2, we can write a simple procedure, analogous to stream-limit, that will count the number of stream values that need to be processed until two consecutive values are within a certain tolerance of the correct value.

(define (stream-values-until-precise s correct tolerance)
  (define (count i last rest)
    (let ((r (stream-car rest)))
      (if (< (abs (- correct (average last r))) tolerance)
          i
          (count (+ i 1) r (stream-cdr rest)))))
  (count 2 (stream-car s) (stream-cdr s)))

The initial value passed to count is 2 because, in the case that the first two values of the stream are within tolerance bounds, we would say that 2 stream values have been consumed before reaching this precision. In other words, the minimal number of stream values that need to be examined before the last two are within tolerance is, of course, 2. (It is merely a convention that the value i denotes the number of values that will have been processed after that iteration of count).

Noting that scheme already defines a fuction log for finding the natural logarithm, we can then ask how many values it takes to reach the correct value within a small tolerance (disclosure: which is kept somewhat large to keep the page generation time low) as follows:

> (define correct (log 2))
> (define tolerance 1e-07)
> (stream-values-until-precise ln-stream correct tolerance)

1582

> (stream-values-until-precise ln-stream++ correct tolerance)

36

> (stream-values-until-precise ln-stream# correct tolerance)

6

    ← prev  up  next →