$ cd ~

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
                   (+ (square p) (square q))
                   (+ (* 2 p q) (square q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        (- count 1)))))

(define (square x) (* x x))