SICP Exercise 1.19
This was my favourite exercise so far. Calculating values of p’ and q’ was fairly easy. Applying the $$T_{pq}$$ transformation twice and factoring out a and b in each case did the trick.
$$ T_{pq} $$ is defined as:
$$ \begin{aligned} &a \leftarrow bq + aq + ap \ &b \leftarrow bp + aq \end{aligned} $$
We’re told applying $$T_{pq}$$ twice has the same effect as applying $$T_{p’q’}$$ once.
Applying $$T_{pq}$$ twice gives:
$$ a \leftarrow (bp+aq)q + (bq+aq+ap)q + (bq+aq+ap)p $$
Which can be simplified to:
$$ a \leftarrow b(2pq+q^2) + a(2pq+q^2) + a(q^2+p^2) $$
Similarly for b:
$$ \begin{aligned} &b \leftarrow (bp+aq)p + (bq+aq+ap)q \ &b \leftarrow b(p^2+q^2) + a(2pq+q^2) \end{aligned} $$
And by simple comparision, we get:
$$ \begin{aligned} &p’ \leftarrow p^2 + q^2 \ &q’ \leftarrow 2pq + q^2 \end{aligned} $$
Which can now simply be put into the fib-iter procedure.
(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
(+ (square p) (square q))
(+ (* 2 p q) (square q))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
(define (square x) (* x x))