SICP Exercise 1.19

Question

There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables a and b in the fib-iter process of 1.2.2: $a\leftarrow a+b$ and $b\leftarrow a$. Call this transformation $T$, and observe that applying $T$ over and over again $n$ times, starting with $1$ and $0$, produces the pair $Fib(n+1)$ and $Fib(n)$. In other words, the Fibonacci numbers are produced by applying $T^n$, the $n$th power of the transformation $T$, starting with the pair $(1,0)$.

Now consider $T$ to be the special case of $p=0$ and $q=1$ in a family of transformations $T_{pq}$ where $T_{pq}$ transforms the pair $(a,b)$ according to $a\leftarrow bq+aq+ap$ and $b\leftarrow bp+aq$. Show that if we apply such a transformation $T_{pq}$ twice, the effect is the same as using a single transformation $T_{p^{\prime }{q}^{\prime }}$ of the same form, and compute $p^{\prime }$ and $q^{\prime }$ in terms of $p$ and $q$. This gives us an explicit way to square these transformations, and thus we can compute $T^n$ using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:

copy(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
                   ⟨??⟩  ;compute p'
                   ⟨??⟩  ;compute q'
                   (/ count 2)))
        (else
         (fib-iter (+ (* b q)
                      (* a q)
                      (* a p))
                   (+ (* b p)
                      (* a q))
                   p
                   q
                   (- count 1)))))

Answer

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

As specified in the question, let us first see what the result is if we apply $T_{pq}$ twice in a row:

$$\begin{array}{rl}a\leftarrow & bq+aq+ap\\ b\leftarrow & bp+aq\\ a^{\prime }\leftarrow & (bp+aq)q+(bq+aq+ap)q+(bq+aq+ap)p\\ b^{\prime }\leftarrow & (bp+aq)p+(bq+aq+ap)q\end{array}$$

We can rewrite $a$ as:

$$\begin{array}{rl}{a}^{\prime }\leftarrow & bpq+aqq+bqq+aqq+apq+bpq+apq+app\\ a^{\prime }\leftarrow & 2bpq+bqq+2apq+2aqq+app\end{array}$$

Which we can then bring into the same shape as our original transformation $a\leftarrow bq+aq+ap$:

$$\begin{array}{rl}{a}^{\prime }\leftarrow & b(2pq+q^2)+a(2pq+q^2)+a(p^2+q^2)\end{array}$$

This gives us the values for $p^{\prime }$ and $q^{\prime }$:

$$\begin{array}{rl}{p}^{\prime }& =p^2+q^2\\ q^{\prime }& =2pq+q^2\end{array}$$

We can verify this by using these new values for $b^{\prime }$:

$$b^{\prime }\leftarrow b(p^2+q^2)+a(2pq+q^2)$$

And then rewriting our original definition for $b^{\prime }$ to come to the exact same equation:

$$\begin{array}{rl}{b}^{\prime }\leftarrow & (bp+aq)p+(bq+aq+ap)q\\ b^{\prime }\leftarrow & bpp+apq+bqq+aqq+apq\\ b^{\prime }\leftarrow & bpp+bqq+2apq+aqq\\ b^{\prime }\leftarrow & b(p^2+q^2)+a(2pq+q^2)\end{array}$$ $$\begin{array}{}◻& \end{array}$$