<< Previous exercise (3.56)
| Index |
Next exercise (3.58) >>
Every term in fibs is computed first as the sum of two previous terms. Since fibs is memoized recalling each previous term requires no additions. Thus each term after the first uses one addition. To compute the nth term (starting at n=0), max(0, n-1) additions are made. If we had not memoized fibs, then to recall previous terms in fibs would require each term to be recomputed. Since the only terms not computed are 1 and zero, fib(n) would require at least fib(n) - 1 additions which is exponential.
This exercise is referring to the implementation of fibs in the book which looks like this:
(add-streams (stream-cdr fibs)
The call to add-streams must read the previous two elements of fibs. When delay is memoized, reading the previous two elements can be done with a lookup, without any additions, and the only addition is the one performed immediately after that. Every adjacent pair of Fibonacci numbers are added only once; the first time. Hence, the total number of additions to get the n-th Fibonacci number is O(n).
If delay were *not* memoized, then the lookup part of the previous two elements would be replaced by a full computation, since every element in a stream besides the very first one is delayed and must be forced every time it is accessed. Hence, "looking up" the values of the two previous Fibonacci numbers now requires all the additions needed to compute those two numbers in the first place.
Let's define A(n) as the number of additions required to obtain the n-th Fibonacci number, assuming that delay is implemented *without* memoization. Then, we have A(n) = A(n-1) + A(n-2), which is exactly the Fibonacci recursion relation. This recursion has the solution A = O(ϕ^n) where ϕ is the golden ratio. Hence, the number of additions when delay is not memoized is exponential.
As an aside, the book also presents an alternative implementation of fibs:
(define (fibgen a b)
(cons-stream a (fibgen b (+ a b))))
(define fibs (fibgen 0 1))
This implemention uses an iterative model, not a recursive one, so it takes O(n) additions even when delay is not memoized.
;; First, you can answer the first question after modifying the add-streams
(define counter 0)
(define (add-streams stream1 stream2)
(lambda (a b)
(set! counter (1+ counter))
(+ a b)))
;; let count-add(fib(n)) = c(n)
;; then c(n+2) = c(n+1) + c(n) + 1
;; so you can get the c(n) like this
(define (count+add n)
(/ (+ 5 (sqrt 5)) 10)
(expt (/ (+ 1 (sqrt 5))2) n))
(/ (- 5 (sqrt 5)) 10)
(expt (/ (- 1 (sqrt 5))2) n))
;; so Θ(c(n)) = Θ(φ^n)