Exercise 1.19

Let \(T_{pq}(a,b) = (bq+aq+ap,bp+aq).\) Applying \(T_{pq}\) twice gives

$$ \begin{aligned} & \ \ \ \ \ \ T_{pq}(T_{pq}(a,b)) \ &= \ T_{pq}(bq+aq+ap,bp+aq) \ &= \ ((bp +aq)q + (bq + aq + ap)q + (bq+aq+ap)p), \ & \ \ \ \ \ \ \ (bp+aq)p + (bq+aq+ap)q)\ &= \ (bpq + aq^2 + bq(q+p) + aq(q+p) + ap(q+p)), \ & \ \ \ \ \ \ \ bp^2 + aqp + bq^2 +aq^2 + apq) \ &=(b-q + aq^2 +bq^2 + bpq + aq^2 + apq+ apq +ap^2, \ & \ \ \ \ \ \ \ bp^2 +apq+bq^2 + aq^2 + apq) \ &= \ (b(q^2 + 2pq) + a(q^2 +2pq) + a(p^2 + q^2), \ & \ \ \ \ \ \ \ b(p^2+q^2)+a(q^2 + 2pq)) \ &= \ T_{p'q'}(a,b) \end{aligned} $$ where \(p' = p^2 + q^2\) and \(q' = q^2 + 2pq\).

Using this, we can implement fib with \(\Theta(\log n)\) time complexity:

(define (fib n)
  (define (iter a b p q count)
    (cond ((= count 0) b)
          ((even? count)
           (iter a
                 b
                 (+ (* p p) (* q q))
                 (+ (* q q) (* 2 p q))
                 (/ count 2)))
          (else (iter (+ (* b q) (* a q) (* a p))
                      (+ (* b p) (* a q))
                      p
                      q
                      (- count 1)))))
  (iter 1 0 0 1 n))

(fib 6) => 8
(fib 100) => 354224848179261915075