Ex. 1.19

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.