SICP Solutions

Chapter 5, Computing with Register Machines

Exercise 5.46

Note that we can use the same approach outlined in ex-5.29 to arrive at the expression for total-pushes or $\, S_n \,$

Here are the results:

total-pushes($\, S_n \,$ ) maximum-depth
special-purpose $\, 3 {\text{fib}}_{n+1} - 3 \,$ $\, 2n-2 \,$
interpreter $\, 56 {\text{fib}}_{n+1} -40 \,$ $\, 5n+3 \,$
compiler $\, 10{\text{fib}}_{n+1} - 3 \,$ $\, 3n-1 \,$
compiler vs interpreter $\, \frac {10} {56} \,$ $\, \frac 3 5 \,$
special vs interpreter $\, \frac 3 {56} \,$ $\, \frac 2 5 \,$
special vs compiler $\, \frac 3 {10} \,$ $\, \frac 2 3 \,$

Note that i removed an extra save in the special-purpose fibonacci using the suggestion from ex-5.6

Also, with open coding enabled in the compiler version, we get:

$$\, \text{total-pushes} = 3{\text{fib}}_{n+1} + 2\,$$

and,

$$\, \text{maximum-depth} = 2n - 2 \,$$

Note that, for fib. there is one more operator < that i added in open coding operators. Intially the results were quite far apart(it was $\, 7 \text{fib}_{n+1} \,$ ) but after realising that < is not open coded, fixing that made the compiler performance almost same as special-purpose performance.

For adding <, just two things:

• Add code in ch5-compiler.scm parallel to open coding changes for =.
• Also check previous exercise ex-5.45(end of the page there) for adding open code operations.

Well thats it!

(I am not sure why problem says that for large n, we won’t approach limiting value. As shown above, for large $\, n \,$, i think while comparing the $\, \text{fib}_{n+1} \,$ term cancels out even if they are not linear. Probably i am wrong.)

To make it easier to work with special purpose fib, i made few changes so that it can read input from console without requiring to explicitly set in the register. Here’s the modified code:

For completion, let me also put the numbers which led to the above formulas. For interpreter version, they are already in ex-5.29.

For the special-purpose version:

For compiler version:

Compiler with open-coding enabled version(including <):