<< Previous exercise (3.62) | Index | Next exercise (3.64) >>
(define (louis-sqrt-stream x)
(cons-stream 1.0
(stream-map (lambda (guess) (sqrt-improve guess x))
(louis-sqrt-stream x))))
To access the second element in the stream (louis-sqrt-stream n) by taking the stream-car of (stream-cdr (louis-sqrt-stream n)) requires two evaluations of (louis-sqrt-stream n): one as the argument to stream-cdr and one in the course of applying that procedure to its argument. Thus one redundant evaluation is performed. Similarly, accessing the third element in the stream by taking the stream-car of (stream-cdr (stream-cdr (louis-sqrt-stream n))) requires two evaluations of (stream-cdr (louis-sqrt-stream n)): one as the argument to stream-cdr and one in the course of applying that procedure to its argument. (Memoization is irrelevant here, since the interpreter cannot see that the second application of stream-cdr to (louis-sqrt-stream n) is an application to the "same" object as the first application, due to the way Louis designed his procedure.) Thus one redundant evaluation is performed, on top of the redundancies involved in evaluating (stream-cdr (louis-sqrt-stream n)) twice. In general, to access the (k + 1)th element in the stream (by k + 1 applications of stream-cdr followed by one application of stream-car) requires one more than twice the number of redundant evaluations required to access the kth element. In other words, the number of redundant evaluations grows exponentially with the index of the element accessed. As already hinted, there would not have been further redundancy if our implementation of delay did not use memoization. For as a result of the distinctness of an "external" call to (louis-sqrt-stream n) from its own internal call to (louis-sqrt-stream n), the two calls to (stream-cdr (louis-sqrt-stream n)) made in the course of evaluating (stream-cdr (stream-cdr (louis-sqrt-stream n))), for example, cannot exploit memoization because the interpreter cannot see that stream-cdr is being applied to the "same" object in each case.
(define (sqrt-stream x)
(define guesses
(cons-stream 1.0
(stream-map (lambda (guess) (sqrt-improve guess x))
guesses)))
guesses)
Unlike the louis-sqrt-stream procedure, accessing the second element in the stream (sqrt-stream n) by taking the stream-car of (stream-cdr (sqrt-stream n)) does not create an second, internal call to (sqrt-stream n). Instead, evaluation of the (sqrt-stream n) argument passed to stream-cdr merely assigns the guesses variable to a value in the environment. This fact prevents the exponential growth of redundant evaluations observed in Louis's procedure. If, however, our implementation of delay did not use memoization, redundant evaluations would arise in another way. For example, to access the third element in the stream by taking the steam-car of (stream-cdr (stream-cdr (sqrt-stream n))) would require two "full" evaluations of (stream-cdr guesses): one as (a reduction of) the argument passed to stream-cdr and, due to the absence of memoization, another one in the course of evaluating the application of that procedure to its argument. In general, without the memoization optimization of delay, accessing the (k + 2)th element in the stream would require one more than twice the number of redundant evaluations required to access the (k + 1)th element. In other words, the number of redundant evaluations would grow exponentially with the index of the element accessed -- in the same way that Louis's procedure already does notwithstanding memoization.
The complexity of louis-sqrt-stream is O(n^2), not O(e^n) like cel said.
Here I denote (lambda (guess) (sqrt-improve guess x)) as sqrt-improve-x and abbreviate `cons-stream` and `stream-map` as `cons` and `map` for the sake of simplicity.
;; Accessing 1st element (cons 1.0 (map sqrt-improve-x (louis-sqrt-stream x))) ;; Accessing 2nd element (cons 1.0 (map sqrt-improve-x (cons 1.0 ;; it has to go through one `map` to reach the top-most stream map sqrt-improve-x (louis-sqrt-stream x)))) ;; Accessing 3rd element (cons 1.0 (map sqrt-improve-x (cons 1.0 map sqrt-improve-x (cons 1.0 ;; it has to go through two `map`s (map sqrt-improve-x (louis-sqrt-stream x)))))) ;; Accessing 4th element (cons 1.0 (map sqrt-improve-x (cons 1.0 (map sqrt-improve-x (cons 1.0 map sqrt-improve-x (cons 1.0 ;; it has to go through three `map`s (map sqrt-improve-x (louis-sqrt-stream x)))))))) ;; ...
It's easy to see that accessing n-th element consists of (n-1) applications of `stream-cdr`, one expansion of `louis-sqrt-stream` and (n-1) applications of `stream-map`, which means that the complexity is O(n^2).
It can be checked empirically with the following procedure:
(define (sqrt-stream x) (cons-stream 1.0 (stream-map (lambda (guess) (sqrt-improve guess x)) (sqrt-stream x)))) (define (sqrt-improve guess x) (average guess (/ x guess))) (define (average x . xs) (/ (apply + (cons x xs)) (+ (length xs) 1))) (define (time proc . args) (newline) (display "time-elapsed: ") (let ((start-time (runtime))) (define res (apply proc args)) (display (- (runtime) start-time)) res)) ; warm-up (define sqrt2 (sqrt-stream 2)) (stream-ref sqrt2 4000) ; test (define sqrt2 (sqrt-stream 2)) (time stream-ref sqrt2 1000) ; 0.48 (define sqrt2 (sqrt-stream 2)) (time stream-ref sqrt2 2000) ; 1.85 ~= 0.48 * 3.9 (define sqrt2 (sqrt-stream 2)) (time stream-ref sqrt2 3000) ; 4.18 ~= 0.48 * 8.7 (define sqrt2 (sqrt-stream 2)) (time stream-ref sqrt2 4000) ; 7.45 ~= 0.48 * 15.5
The function defined by Louis calls `(sqrt-stream x)' recursively, which yields a new sequence with the same values, only not memoized yet. Thus this version is slower, but if memoization didn't take place, both implementations would be the same.