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:
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) ) ) ) )