## The Problem Statement

*This problem statement is taken nearly verbatim from Section 1.2.4 from the book Structure and Interpretation of Computer Programs. The original text is available here free.*

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 section 1.2.2: $a\gets a + b$ and $b\gets a$. Call this transformation $T$, and observe that applying $T$ over and over again $n$ times, starting with $1$ and $0$, produces the pair $\operatorname{Fib}(n + 1)$ and $\operatorname{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_{p,q}$, where $T_{p,q}$ transforms the pair $(a,b)$ according to $a\gets bq + aq + ap$ and $b\gets bp + aq$. Show that if we apply such a transformation $T_{p,q}$ 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)))))

## Discussion

This problem isn’t very tricky (despite the long prose), but it does open up an interesting piece of mathematics, and exposes a remarkable trick for computing Fibonacci numbers quickly.

To use a different notation, we are told about a transformation $T_{p,q}$ defined like so:

\[

\begin{pmatrix} a \\ b \end{pmatrix} \xrightarrow{T_{p,q}}

\begin{pmatrix} bq+aq+ap \\ bp+aq \end{pmatrix}.

\]

We can think of $T_{p,q}$ as a sort of “parameterized function” that takes a pair as input, and produces another pair as output. As an aside, another parameterized function/transformation is rotation. Let $R_\theta$ be the operator that rotates a point by $\theta$ radians. The transformation is defined like so:

\[

\begin{pmatrix} x \\ y \end{pmatrix} \xrightarrow{R_\theta}

\begin{pmatrix} x\cos\theta-y\sin\theta \\ x\sin\theta+y\cos\theta \end{pmatrix}.

\]

Back on track, the question is essentially asking us to figure out what $p’$ and $q’$ are in the following:

\[

\begin{pmatrix} a \\ b \end{pmatrix} \xrightarrow{T_{p,q}^2}

\begin{pmatrix} bq'+aq'+ap' \\ bp'+aq' \end{pmatrix},

\]

where $T_{p,q}^2=T_{p,q}\circ T_{p,q}$ is the act of applying $T_{p,q}$ twice in succession.

Why would they ask this though? Well, the motivation comes from the *binary exponentiation* concept they talked about in this section. From the binary exponentiation example, we saw that to compute $x^n$ when $n$ is even, it’s easier to compute $(x^{n/2})^2$. It effectively cuts out that extra $n/2$ multiplications for a single squaring.

This exercise is almost exactly the same. The original iterative Fibonacci uses the transformation $T_{0,1}$ over and over. To compute the $n$th Fibonacci number, we compute $T_{0,1}^n$, which is $n$ successive applications of $T_{0,1}$. The goal of this exercise is to be able to “square” a transformation so instead of $T_{0,1}^n$, we could do $(T_{0,1}^{n/2})^2$, when $n$ is even. If $n$ is odd, then we do $T_{0,1}^n = T_{0,1}\circ T_{0,1}^{n-1}$, and now $n-1$ will be even. If we can do this, we effectively chop the amount of work left at each step in half, which leads to logarithmic complexity (to compute the $n$th Fibonacci number, we only need to use about $\log_2 n$ steps).

## The Solution

**SPOILER WARNING! This contains the solution.**

The actual exercise is easy, if a little tedious. We just apply the transformation twice, and do a little algebraic razzmatazz to get it to match the form we want.

Again, recall

\[

\begin{pmatrix} a \\ b \end{pmatrix} \xrightarrow{T_{p,q}}

\begin{pmatrix} bq+aq+ap \\ bp+aq \end{pmatrix}.

\]

This is effectively the first transformation done for us. Now we just do it again!

\[

\begin{pmatrix} bq+aq+ap \\ bp+aq \end{pmatrix}

\xrightarrow{T_{p,q}}

\begin{pmatrix}

(bp+aq)q+(bq+aq+ap)q+(bq+aq+ap)p \\

(bp+aq)p+(bq+aq+ap)q\end{pmatrix}

\]

Now expand the products.

\[

\begin{pmatrix}

bpq+aq^2+bq^2+aq^2+apq+bpq+apq+ap^2 \\

bp^2+apq+bq^2+aq^2+apq\end{pmatrix}

\]

Now, we are supposed to get into a form which resembles the original. To remind us, it’s

\[

\begin{pmatrix} bq'+aq'+ap' \\ bp'+aq' \end{pmatrix}.

\]

Starting with the bottom is easier. Notice how we need to get into a form where all of the products containing $b$ are collected into one product (i.e., $bx+by+bz\to b(x+y+z)$), as with all of the products containing $a$. Looking at the bottom only, the products containing $b$ are just $bp^2$ and $bq^2$. So we factor the $b$ out and get $b(p^2+q^2)$. If we do the same for $a$, whose products are $2apq$ (look, there are two $apq$’s in there!) and $aq^2$, we get $a(2pq+q^2)$. So the bottom becomes

\[

\begin{pmatrix}

?? \\

b(p^2+q^2)+a(2pq+q^2)

\end{pmatrix}.

\]

Now it’s in the form of $bp’+aq’$ and we see $p’=p^2+q^2$ and $q’=2pq+q^2$. But, as a sanity check, we must be able to write the top with these same values of $p’$ and $q’$. First, start by collecting all of the products containing $b$. Indeed, we have $2bpq$ and $bq^2$, giving us $b(2pq+q^2)$:

\[

\begin{pmatrix}

b(2pq+q^2)+\cdots \\

b(p^2+q^2)+a(2pq+q^2)

\end{pmatrix}.

\]

Now we need to find $aq’$. So we need the products $2apq$ and $aq^2$. We see we have both (in fact, we have *two* $aq^2$ terms, but we only use one), so take them to form

\[

\begin{pmatrix}

b(2pq+q^2)+a(2pq+q^2)+\cdots \\

b(p^2+q^2)+a(2pq+q^2)

\end{pmatrix}.

\]

Finally, we are left with the terms $ap^2$ and $aq^2$, exactly the terms we need for the last $ap’$ term:

\[

\begin{pmatrix}

b(2pq+q^2)+a(2pq+q^2)+a(p^2+q^2) \\

b(p^2+q^2)+a(2pq+q^2)

\end{pmatrix}.

\]

So, in all, we find that the square transformation $T_{a,b}^2$ can be done in only one transformation $T_{p^2+q^2,2pq+q^2}$. Now, we just write this in our Scheme program.

(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)) ; compute p' = p^2 + q^2 (+ (* 2 p q) (* q q)) ; compute q' = 2pq + q^2 (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))

You can calculate $q^2$ once to save a multiply if you’re so inclined.