# Fibonacci numbers through transformation

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 `Tⁿ` , 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, 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 `Tⁿ` 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)))))
``````