Fibonacci Numbers

Continuing reading the SICP book...

In every book about algorithms I have read there is always a chapter about the Fibonacci numbers. Mainly on the different algorithms of calculating the n-th Fibonacci number and comparing their order of growth. First comes the algorithm, based on definition:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

This function is good at explaining tree recursion, but is awful for calculating Fibonacci numbers, as it makes too many unnecessary calculations. The order of growth is Θ(Fib(n)), which means exponential. The next comes iterative funcion, which solves the task much better, using less resources and time. Its order of growth is Θ(n) - linear.

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
     b
     (fib-iter (+ a b) a (- count 1))))

But there is also an algorithm that calculates Fibonacci number with Θ(log n) complexity. There, in the book they give you the function with gaps and some pointers ( no C here :) ), how to fill them.

(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
                   [??] calculate p'
                   [??] calculate q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

The authors remind us of the transformation of the state variables a and b in the previous (iterative) fib-iter procedure: a ← a + b and b ← a. Provided these state changes are labeled transformation T, applying T repeatedly for n iterations starting with a = 1 and b = 0 will produce the pair a = Fib(n + 1) and b = Fib(n). So the Fibonacci numbers are produced by the n^th power of the transformation T (Tⁿ), starting with the pair (1, 0).

Now consider the family of transformations T_pq which transforms the pair (a, b) according to the following rules:

a ← bq + aq + ap
b ← bp + aq

Where transformation T is just a special case of T_pq, where p = 0 and q = 1. Now it's up to you to find the transformation T_p'q' such so, if we apply T_pq twice, the effect is the same as using a single transformation T_p'q' of the same form. Compute p' and q' in terms of p and q and put into the function.

I will not provide the solution here, in case you want to handle it yourself. But if you are eager to see the result, visit some other blog that has the solution. :)