sicp-ex-3.57



<< Previous exercise (3.56) | Index | Next exercise (3.58) >>


adams

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.

xdavidliu

This exercise is referring to the implementation of fibs in the book which looks like this:

 (define fibs 
   (cons-stream 0 
                (cons-stream 1 
                             (add-streams (stream-cdr fibs) 
                                          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.

Agree with your conclusion: "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."

I have a question with how you arrived at this. You stated that the number of additions required to obtain the n-th Fibonacci number is A(n) = A(n-1) + A(n-2).

However, because this is a stream, don't we also need to compute the Fibonacci numbers for the range n=[0,n-1]. Example, when computing Fib(3):

- Compute Fib(0)
- Compute Fib(1)
- Compute Fib(2) by computing Fib(0) and Fib(1) and adding
- Compute Fib(3) by computing Fib(2) [which requires computing Fib(0) and Fib(1) again] and Fib(1), and adding

If this is true, this would yield the number of additions as:

A(n) = A(n-1) + [A(n-1) + A(n-2) + 1]


Sphinxsky

  
  
  
 ;; First, you can answer the first question after modifying the add-streams 
 (define counter 0) 
  
 (define (add-streams stream1 stream2) 
     (stream-map 
         (lambda (a b) 
             (begin 
                 (set! counter (1+ counter)) 
                 (+ a b))) 
         stream1 
         stream2)) 
  
  
 ;; 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)) 
         (- 1))) 
  
 ;; so Θ(c(n)) = Θ(φ^n) 
  

Cirno

 ;; with memo 
 ;; k = 0, no force 
 ;; k = 1, no force 
 ;; k = 2, 1 force 
 ;; k = 3, 1 force 
 ;; k = 4, 1 force 
 ;; . 
 ;; . 
 ;; . 
 ;; k = n, 1 force 
 ;; total = (n-2) forces 
  
 ;; no memo 
 ;; for each force, we have to add up all the previous forces for fib and for 
 ;; (stream-cdr fib), so we get fib(k-1) + fib(k-2), but thats exactly fib(k).  
 ;; k = 0, no force 
 ;; k = 1, no force 
 ;; k = 2, 1 force 
 ;; k = 3, 2 force 
 ;; k = 4, 3 force 
 ;; k = 5, 5 force 
 ;; k = 6, 8 force 
 ;; . 
 ;; . 
 ;; . 
 ;; k = n, fib(n) force 
 ;; total = fib(n+2)-1-1, which is equal to the sum of the first n numbers with 
 ;; fib(1) excluded, but thats equal to (phi^(n+2)-psi^(n+2))/sqrt(5) - 2