weima learns to program

my attempt to do the exercises in sicp.

Sunday, December 19, 2010

sicp exercise 3.57

;; 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

(define numofsum 0)
(define (plus a b)
(set! numofsum (+ 1 numofsum))
(+ a b))

(define (reset)(set! numofsum 0))

(stream-map plus s1 s2))

(define fibs
(cons-stream 0
(cons-stream 1
fibs))))

(newline)
(display (stream-ref fibs 0))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 1))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 2))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 3))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 4))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 5))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 6))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 20))(display " ")(display numofsum)(newline)

(display "-------------")(newline)

(reset)
(define (fibo n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (plus (fibo (- n 1))
(fibo (- n 2))))))

(display (fibo 0)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 1)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 2)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 3)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 4)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 5)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 6)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 20)) (display " ") (display numofsum) (newline)(reset)

;; Output:
;0 0
;1 0
;1 1
;2 2
;3 3
;5 4
;8 5
;6765 19
;-------------
;0 0
;1 0
;1 1
;2 2
;3 4
;5 7
;8 12
;6765 10945
;... done