19

Exercise 1.19: 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 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 $| 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 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 $| 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)))))

T is the transformation of applying

a <- a + b
b <- a

Tpq is

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

and T is T10 actually.

Applying Tpq twice, it transforms (a, b) into (a2, b2)

a1 = bq + aq + ap
b1 = bp + aq

a2 = b1q + a1q + a1p 
   = (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
   = bpq + aqq + bqq + aqq + apq + bqp + aqp + app
   = b(pq + qq + qp) + a(qq + qq + pq + qp + pp)
   = b(pq + qq + qp) + a(pq + qq + qp) + a(qq + pp)
b2 = b1p + a1q 
   = (bp + aq)p + (bq + aq + ap)q
   = bpp + aqp + bqq + aqq + apq
   = b(pp + qq) + a(qp + qq + pq)

let p′ = pp + qq, and q′ = 2pq + qq, we can simplify the above to

a2 = bq′ + aq′ + ap′
b2 = bp′ + aq′

That is to say: $| T_{pq}^{2} = T_{p'q'} |$.

The completed procedure is

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

(fib 0)

(fib 1)

(fib 2)

(fib 3)

(fib 4)

(fib 5)

(fib 6)