Exercise 1.19 in “The Structure and Interpretation of Computer Programs” reads as follows: 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 a + b and b 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 Tn, the nth 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 Tpq, where Tpq transforms the pair (a,b) according to a bq + aq + ap and b bp + aq. Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation Tp’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 Tn using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure (translated to Clojure), which runs in a logarithmic number of steps.
Each step in the Fibonacci sequence can be calculated using the ‘:else’ portion of this algorithm, which simply adds the previous two numbers (in its own way). The problem here is to define this step in a way that enables this computation to complete in a logarithmic number of steps. Working the formulas will help illustrate this concept more clearly.
Currently, a and b are defined as follows: a = bq + aq + ap b = bp + aq
What we need to determine is an equation which calculates a and b applying the transformation twice. This can be accomplished by substituting our initial equations for a and b into themselves as follows:
a = (bp + aq)q + (bp + aq + ap)q + (bp + aq + ap)p b = (bp + aq)p + (bp + aq + ap)q
What we would like now, is to simplify these ugly equations to be expressed in terms of a and b, so we can see what our p’ and q’ will be. Although I did this backwards when I attempted it, it is easier to simplify b first and then try and simplify a in a similar fashion. b simplifies to:
b = bp2 + apq + bq2 + aq2 + apq
b = b(p2 + q2) + a(2pq + q2)
If we can then rewrite ‘a’ using the same terms, we can isolate p2 + q2 as p’ and 2pq + q2 as q’. Let’s see how ‘a’ shakes out:
a = bpq + aq2 + bq2 + aq2 + apq + bpq + apq + ap2
Kind of nasty, but.. a = a(q2 + p2) + a(2pq + q2) + b(2pq + q2)
The equations are now rewritten in the same form as they were originally, with
p’ = p2 + q2 and q’ = 2pq + q2
We can now insert these values in our function and give it a test drive.
After a couple quick tests, we are able to verify the function now calculates numbers in the Fibonacci sequence in a logarithmic number of steps.