Chapter 1, Building Abstractions with Procedures

Section - Procedures and the Processes They Generate

Exercise 1.19


It is shown that the following transformation on :


generates fibonacci numbers: fib(n), fib(n+1) when this transformation is applied n times starting with and .

Note that here the problem says that applying transformation one times means , then applying two times means , similarly applying times means .

Now there is another transformation transforms as:

Lets call the result generated by transformation on as . Thus:
and
.

Now as asked in the question, we apply this transformation again on the last result. Thus we apply twice. Or we can say that we apply . Applying this we get:

.

Now we put values of and to compute :

.
.
.

Similarly we put values to compute :

.
.

Thus transformation gives:

.

Let and , then we have:


.

But this is also a result of transformation . Thus .

As mentioned in the book, transformation is a special case of transformation when and . Thus when and .

Since for finding and , we need to compute and (for and ), it follows that .

Thus we need to compute for and . But we already know how to square by computing and . Again we can square to get . Thus we can follow the exponential algorithm from previous exercises to compute by squaring till we reach .

Now if we look at the algorithm given in book, it is clear we need to compute and .

Thus we have the following completed algorithm:

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
#lang sicp

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
                (fib-iter
                          a
                          b
                          (+ (* p p) (* q q)) 
                          (+ (* 2 p q) (* q q)) 
                          (/ count 2)
                )
         )
         (else
                (fib-iter
                          (+ (* b q) (* a q) (* a p))
                          (+ (* b p) (* a q))
                          p
                          q
                          (- count 1)
                 )
         )
  )
)