<< Previous exercise (5.45) | Index | Next exercise (5.47) >>
Summary ======= ┌─────────────┬──────────────────┬──────────────────┐ │ Fibonacci │ Maximum Depth │ Number of Pushes │ ├─────────────┼──────────────────┼──────────────────┤ │ Interpreted │ 5n + 3 │ 56*(fib n+1)-34 │ ├─────────────┼──────────────────┼──────────────────┤ │ Compiled │ 2n + 0 │ 7*(fib n+1)-2 │ ├─────────────┼──────────────────┼──────────────────┤ │ Machine │ 2n - 2 │ 4*(fib n+1)-4 │ └─────────────┴──────────────────┴──────────────────┘ Machine ======= The stats for (fib 4) are from the hand-sumulation in Ex 5.5 ┌────┬───────────┬───────────────┬──────────────────┐ │ n │ Fibonacci │ Maximum Depth │ Number of Pushes │ ├────┼───────────┼───────────────┼──────────────────┤ │ 1 │ 1 │ 0 │ 0 │ ├────┼───────────┼───────────────┼──────────────────┤ │ 2 │ 1 │ 2 │ 4 │ ├────┼───────────┼───────────────┼──────────────────┤ │ 3 │ 2 │ ... │ ... │ ├────┼───────────┼───────────────┼──────────────────┤ │ 4 │ 3 │ 6 │ 16 │ ├────┼───────────┼───────────────┼──────────────────┤ │ 5 │ 5 │ ... │ ... │ ├────┴───────────┴───────────────┼──────────────────┤ │ │ 4*(fib n+1)-4 │ └────────────────────────────────┴──────────────────┘ If using the optimizaton from Ex. 5.6 the number of pushes will be smaller, i.e.: 3*(fib n+1)+3 Iterpreted & Compiled ===================== ┌────┬───────────┬────────────────────────────┬──────────────────────────┐ │ │ │ Interpreted │ Compiled │ │ │ Fibonacci ├───────────┬────────────────┼───────────┬──────────────┤ │ │ │ Max Depth │ No of Pushes │ Max Depth │ No of Pushes │ ├────┼───────────┼───────────┼────────────────┼───────────┼──────────────┤ │ 1 │ 1 │ 8 │ 22 │ 3 │ 5 │ ├────┼───────────┼───────────┼────────────────┼───────────┼──────────────┤ │ 2 │ 1 │ 13 │ 78 │ 4 │ 12 │ ├────┼───────────┼───────────┼────────────────┼───────────┼──────────────┤ │ 3 │ 2 │ 18 │ 134 │ 6 │ 19 │ ├────┼───────────┼───────────┼────────────────┼───────────┼──────────────┤ │ 4 │ 3 │ 23 │ 246 │ 8 │ 33 │ ├────┼───────────┼───────────┼────────────────┼───────────┼──────────────┤ │ 5 │ 5 │ 28 │ 414 │ 10 │ 54 │ ├────┼───────────┼───────────┼────────────────┼───────────┼──────────────┤ │ 6 │ 8 │ 33 │ 694 │ 12 │ 89 │ ├────┼───────────┼───────────┼────────────────┼───────────┼──────────────┤ │ 7 │ 13 │ 38 │ 1,142 │ 14 │ 145 │ ├────┼───────────┼───────────┼────────────────┼───────────┼──────────────┤ │ 8 │ 21 │ 43 │ 1,870 │ 16 │ 236 │ ├────┼───────────┼───────────┼────────────────┼───────────┼──────────────┤ │ 9 │ 34 │ 48 │ 3,046 │ 18 │ 383 │ ├────┼───────────┼───────────┼────────────────┼───────────┼──────────────┤ │ 10 │ 55 │ 53 │ 4,950 │ 20 │ 621 │ ├────┼───────────┼───────────┼────────────────┼───────────┼──────────────┤ │ 11 │ 89 │ 58 │ 8,030 │ 22 │ 1,006 │ ├────┴───────────┴───────────┼────────────────┼───────────┼──────────────┤ │ │ 56*(fib n+1)-34│ │ 7*(fib n+1)-2│ └────────────────────────────┴────────────────┴───────────┴──────────────┘
Here are the results:
Interpreted => S(n) = 42*Fib(N+1) - 30
Special purpose => Pushes S(n) = 3*Fib(n+1) - 3 Detpth 2n - 2
Normal copmile => Pushes S(n) = 7*Fib(n+1) - 2 Depth 2n
Modified compiler. This is the compiler I posted in the previous exercise.
=> Pushes S(n) = 3*Fib(n+1) Depth 2n - 2
As can be seen here. The modified compiler behaves the same as the special purpose machine.