Chapter 1, Building Abstractions with Procedures

Section - Procedures and the Processes They Generate

Exercise 1.19


It is shown that the following transformation $T$ on $(a,b)$:
$a \leftarrow a + b$
$b \leftarrow a$
generates fibonacci numbers: fib(n), fib(n+1) when this transformation is applied n times starting with $a = 0$ and $b = 1$.

Note that here the problem says that applying transformation one times means $T^1$, then applying two times means $T^2$, similarly applying $n$ times means $T^n$.

Now there is another transformation $T_{pq}$ transforms $(a,b)$ as:
$a \leftarrow bq + aq + ap$
$b \leftarrow bp + aq$

Lets call the result generated by transformation $T_{pq}$ on $(a,b)$ as $a', b'$. Thus:
$a' = bq + aq + ap$ and
$b' = bp + aq$.

Now as asked in the question, we apply this transformation again on the last result. Thus we apply $T_{p,q}$ twice. Or we can say that we apply $T_{pq}^{2}$. Applying this we get:
$a'' = b'q + a'q + a'p$
$b'' = b'p + a'q$.

Now we put values of $a'$ and $b'$ to compute $a''$:

$a'' = (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p$.
$= bpq + aq^2 + bq^2 + aq^2 + apq + bqp + aqp + ap^2$.
$= (2pq + q^2)b + (2pq + q^2)a + (p^2 + q^2)a$.

Similarly we put values to compute $b''$:

$b'' = (bp + aq)p + (bq + aq + ap)q$.
$= (2pq+q^2)a + (p^2 + q^2)b$.

Thus transformation $T_{pq}^{2}$ gives:
$a'' = (2pq + q^2)b + (2pq + q^2)a + (p^2 + q^2)a$
$b'' = (2pq+q^2)a + (p^2 + q^2)b$.

Let $p' = (p^2 + q^2)$ and $q' = (2pq + q^2)$, then we have:

$a'' = bq' + aq' + ap$
$b'' = bp' + aq'$.

But this is also a result of transformation $T_{p'q'}$. Thus $T_{pq}^{2} = T_{p'q'}$.

As mentioned in the book, transformation $T$ is a special case of transformation $T_{pq}$ when $p = 0$ and $q = 1$. Thus $T_{pq} = T$ when $p = 0$ and $q = 1$.

Since for finding $fib(n)$ and $fib(n+1)$, we need to compute $T^n$ and $T_{pq} = T$(for $p = 0$ and $q = 1$), it follows that $T^n = T_{pq}^n$.

Thus we need to compute $T_{pq}^n$ for $p = 0$ and $q = 1$. But we already know how to square $T_{pq}$ by computing $p'$ and $q'$. Again we can square $T_{p'q'}$ to get $T_{pq}^4$. Thus we can follow the exponential algorithm from previous exercises to compute $T^n_{pq}$ by squaring till we reach $n$.

Now if we look at the algorithm given in book, it is clear we need to compute $p' = (p^2 + q^2)$ and $q' = (2pq + q^2)$.

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