Exercise 5.46.  Carry out an analysis like the one in exercise 5.45 to 
determine the effectiveness of compiling the tree-recursive Fibonacci 
procedure

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

compared to the effectiveness of using the special-purpose Fibonacci 
machine of figure 5.12. (For measurement of the interpreted performance, 
see exercise 5.29.) For Fibonacci, the time resource used is not linear 
in n; hence the ratios of stack operations will not approach a limiting 
value that is independent of n. 

————————————————————————————————————————————————————————————————————————


inimino@kat:~/cs/2009/SICP/chap_5$ scheme --load load-eceval-compiler.scm 
1 ]=> (load "ch5-compiler")  
1 ]=> (compile-and-go '(define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))

;;; EC-Eval input:
(fib 1)
(total-pushes = 7 maximum-depth = 3)
;;; EC-Eval value:
1

;;; EC-Eval input:
(fib 2)
(total-pushes = 17 maximum-depth = 5)
;;; EC-Eval value:
1

;;; EC-Eval input:
(fib 3)
(total-pushes = 27 maximum-depth = 8)
;;; EC-Eval value:
2

;;; EC-Eval input:
(fib 4)
(total-pushes = 47 maximum-depth = 11)
;;; EC-Eval value:
3

;;; EC-Eval input:
(fib 5)
(total-pushes = 77 maximum-depth = 14)
;;; EC-Eval value:
5

;;; EC-Eval input:
(fib 6)
(total-pushes = 127 maximum-depth = 17)
;;; EC-Eval value:
8

The pushes in terms of n:

10 * Fib(n+1) - 3

In the handwritten version:

Figure 5.12:

(controller
   (assign continue (label fib-done))
 fib-loop
   (test (op <) (reg n) (const 2))
   (branch (label immediate-answer))
   ;; set up to compute Fib(n - 1)
   (save continue)
   (assign continue (label afterfib-n-1))
   (save n)                           ; save old value of n
   (assign n (op -) (reg n) (const 1)); clobber n to n - 1
   (goto (label fib-loop))            ; perform recursive call
 afterfib-n-1                         ; upon return, val contains Fib(n - 1)
   (restore n)
   (restore continue)
   ;; set up to compute Fib(n - 2)
   (assign n (op -) (reg n) (const 2))
   (save continue)
   (assign continue (label afterfib-n-2))
   (save val)                         ; save Fib(n - 1)
   (goto (label fib-loop))
 afterfib-n-2                         ; upon return, val contains Fib(n - 2)
   (assign n (reg val))               ; n now contains Fib(n - 2)
   (restore val)                      ; val now contains Fib(n - 1)
   (restore continue)
   (assign val                        ;  Fib(n - 1) +  Fib(n - 2)
           (op +) (reg val) (reg n)) 
   (goto (reg continue))              ; return to caller, answer is in val
 immediate-answer
   (assign val (reg n))               ; base case:  Fib(n) = n
   (goto (reg continue))
 fib-done)

Since the form of the computation is the same, there must be a solution 
in the same "a * Fib(n+1) + b" form, but the constants will be lower.

The ratio of performance between the handwritten and compiled version will 
scale with Fib(n+1) rather than with n, as the exercise suggests.  However, 
the ratio of the two runtimes will still be expected to approach a 
constant as n increases.