Thread: O(Log(n)) Algorithm for Computing Fibonacci Numbers, SICP Ex. 1.19

Hello! I'm so glad this Math Forum exists. Hopefully the people here can help me out. First off, I'm not sure if I'm posting in the right section. I didn't see anything specifically on algorithms and computing but I saw someone else post a Fibonacci question here.

Also, even though I am referencing an exercise of a book (SICP), this is not for any type of school assignment, I am studying this stuff on my own.

MIT offers the book free, and the section this problem is in is here:

Structure and Interpretation of Computer Programs

Earlier in the text it was demonstrated that the recursively defined Fibonacci sequence can be computed with a "linear iterative" process (so only O(n) steps and O(1) space is required to complete the process). The exercise (1.19) is to complete an algorithm that computes Fib(n) in O(Log(n)) time. This is achieved by essentially "squaring" the Fibonacci function. Here is the text of the exercise:

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, which runs in a logarithmic number of steps:

Code:

(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)))))

So what I'm looking for is basically some hints on where to start and how to think about solving this type of problem (in this case, how to find p' and q'). I'm looking more for general problem-solving methods than specifics. Here is some of the work I've done on the problem so far:

I started out trying to do some kind of algebra on the problem :/ Here is an image of my scratch work:

http://www.chrisdavaz.com/files/19.png (I gave a link rather than uploaded because no matter what I seem to do the website says that this is not a valid image file.)

And later on as text:

a <- bq + aq + ap
b <- bp + aq

a <- (bp + aq) q + (bq + aq + ap) q + (bq + aq + ap) p
b <- (bp + aq) p + (ba + aq + ap) q

bpq + aq^2 + bq^2 + aq^2 + apq + bqp + aqp + ap ^2
pq(b + a + b + a) + q^2(a + b + a) + p^2(a)

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

Later on I tried looking at the problem as a ratio between a and b (i.e., "the golden ratio"), since that ratio must be maintained from iteration to iteration:

a(p + q) + bq
----------------
bp + aq

Again, I feel like I am on to something but wind up just staring at this and getting nowhere.

Do any of the thoughts here make sense or is it just aimless wandering?

The calculation that you need to find p' and q' goes like this.

If is the transformation given by then is given by



This is of the form , where and

That deals with the first part of the exercise. I think that for the second part, you need to use the fact that Then by successively squaring that operation n times, you can compute the (2^n)'th Fibonacci number.

Thanks Opalg! I'll study this and see where I went astray.