SICP Exercise 3.57 fibs using add-streams

Exercise 3.57.  How many additions are performed when we compute the nth Fibonacci number using the definition of fibs based on the add-streams procedure? Show that the number of additions would be exponentially greater if we had implemented (delay <exp>) simply as (lambda () <exp>), without using the optimization provided by the memo-proc procedure described in section 3.5.1.64

 SOLUTION

 The Racket code and explanation is here.

 The Scheme code and tests are here.

 EXPLANATION

 (define fibs
(stream-cons
0
(stream-cons
1
(add-streams (stream-rest fibs) fibs)
)
)
)

 Number of additions performed:

 0th Fibonacci number (0): 0 additions
1st Fibonacci number (1): 0 additions
2nd Fibonacci number (1): 1 addition
3rd Fibonacci number (2): 2 additions
4th Fibonacci number (3): 3 additions

 As we can see above, for every higher Fibonacci number, one additional addition is performed. So when we compute the nth Fibonacci number, n - 1 additions are performed in total.

Now, if we had implemented (delay <exp>) simply as (lambda () <exp>) without memoization, then, upon accessing the nth Fibonacci number using (stream-ref fibs n) where n > 1, add-streams is executed which accesses the fibs stream twice. Since accessing fibs results in a call to add-streams, the result is that every add-streams call results in two calls to add-streams. This pattern results in 2^n additions. 

 Therefore the number of additions will be exponentially greater compared to when we use memoization in the 'delay' implementation.

Comments

Post a Comment

Popular posts from this blog

SICP Exercise 4.18 a alternative strategy for interpreting internal definitions

Exercise 4.18.   Consider an alternative strategy for scanning out definitions that translates the example in the text to (lambda < vars >   (let ((u '*unassigned*)         (v '*unassigned*))     (let ((a < e1 >)           (b < e2 >))       (set! u a)       (set! v b))     < e3 >)) Here  a  and  b  are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the  solve  procedure from section  3.5.4 : (define (solve f y0 dt)   (define y (integral (delay dy) y0 dt))   (define dy (stream-map f y))   y) Will this ...
Read more

SICP Exercise 3.11 make-account internal definitions with local state

Image
Exercise 3.11.    In section  3.2.3  we saw how the environment model described the behavior of procedures with local state. Now we have seen how internal definitions work. A typical message-passing procedure contains both of these aspects. Consider the bank account procedure of section  3.1.1 : (define (make-account balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amount)     (set! balance (+ balance amount))     balance)   (define (dispatch m)     (cond...
Read more

SICP Exercise 3.13 make-cycle

Image
Exercise 3.13.    Consider the following  make-cycle  procedure, which uses the  last-pair  procedure defined in exercise  3.12 : (define (make-cycle x)   (set-cdr! (last-pair x) x)   x) Draw a box-and-pointer diagram that shows the structure  z  created by (define z (make-cycle (list 'a 'b 'c))) What happens if we try to compute  (last-pair z) ? SOLUTION The code is here: Exercise 3.13 make-cycle The box-and-pointer diagrams are here:
Read more