Chapter 5, Computing with Register Machines

Exercise 5.29


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
;;; EC-Eval input:
(fib 0)

(total-pushes = 16 maximum-depth = 8)
;;; EC-Eval value:
0

;;; EC-Eval input:
(fib 1)

(total-pushes = 16 maximum-depth = 8)
;;; EC-Eval value:
1

;;; EC-Eval input:
(fib 2)

(total-pushes = 72 maximum-depth = 13)
;;; EC-Eval value:
1

;;; EC-Eval input:
(fib 3)

(total-pushes = 128 maximum-depth = 18)
;;; EC-Eval value:
2

;;; EC-Eval input:
(fib 4)

(total-pushes = 240 maximum-depth = 23)
;;; EC-Eval value:
3

;;; EC-Eval input:
(fib 5)

(total-pushes = 408 maximum-depth = 28)
;;; EC-Eval value:
5

;;; EC-Eval input:
(fib 6)

(total-pushes = 688 maximum-depth = 33)
;;; EC-Eval value:
8

;;; EC-Eval input:
(fib 7)

(total-pushes = 1136 maximum-depth = 38)
;;; EC-Eval value:
13

;;; EC-Eval input:
(fib 8)

(total-pushes = 1864 maximum-depth = 43)
;;; EC-Eval value:
21

;;; EC-Eval input:
(fib 9)

(total-pushes = 3040 maximum-depth = 48)
;;; EC-Eval value:
34

;;; EC-Eval input:

(a) Clearly this is

(b)

First lets prove that , where is a constant.

For :

If we look at the procedure, computing requires two things:

  • Execution of comparision inside if.
  • computing and .
  • After computing them, we add them together.

Since the first and third steps are independent of n, it follows that the number of pushes that occur in these steps is some constant number.

Thus the total pushes we need is this constant number and the pushes that happen because of computing and computing .

Thus where is the constant number of pushes that happen irrespective of n.

We can easily compute the value of from the data we have above. It gives us .

Now, we shall prove that .

We shall prove it using mathematical induction.

Suppose that the above formulae is correct for all integers such that . Now if we can deduce that this is true for too, then this will complete the proof.

For case :

. Since , for this to be true, we must have (putting the value of ).

Similarly, for case , we must have .

Now for the case and :

From the above we know that . Since and lies between and , by our assumption we have:

and . Putting them in formulae , we get:

, which further simplifies to:

. Now if , then the theorem will be correct for this case too.

Thus from all above cases, our theorem will be true if and only if there exists value(s) of and such that all of the following are true:

  • .
  • .
  • And, .

We already know . Solving them we find that and . Thus there exist values of and which satisfy all of the above equations, it follows that the theorem is correct!


Comments:

It’s one thing to prove that a formulae is correct and entirely another thing to come up with a formulae. This exercise requires only to prove the correctness of the formulae presented in it. I doubt that I could have come up with this formulae myself!