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’q'}$ of the same form, and compute $p'$ and $q'$ 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:

(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

(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{align} a\leftarrow &bq+aq+ap \newline b\leftarrow &bp+aq \newline a'\leftarrow &(bp+aq)q +(bq+aq+ap)q+(bq+aq+ap)p \newline b'\leftarrow &(bp+aq)p+(bq+aq+ap)q \end{align} $$

We can rewrite $a$ as:

$$ \begin{align} a'\leftarrow &bpq+aqq+bqq+aqq+apq+bpq+apq+app \newline a'\leftarrow &2bpq+bqq+2apq+2aqq+app \end{align} $$

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

$$ \begin{align} a'\leftarrow &b(2pq+q^2)+a(2pq+q^2)+a(p^2+q^2) \end{align} $$

This gives us the values for $p'$ and $q'$:

$$ \begin{align} p'&=p^2+q^2 \newline q'&=2pq+q^2 \end{align} $$

We can verify this by using these new values for $b'$:

$$ b'\leftarrow b(p^2+q^2)+a(2pq+q^2) \newline $$

And then rewriting our original definition for $b'$ to come to the exact same equation:

$$ \begin{align} b'\leftarrow &(bp+aq)p+(bq+aq+ap)q \newline b'\leftarrow &bpp+apq+bqq+aqq+apq \newline b'\leftarrow &bpp+bqq+2apq+aqq \newline b'\leftarrow &b(p^2+q^2)+a(2pq+q^2) \newline \end{align} $$ $$ \tag*{$\Box$} $$