ex1.19.rkt

#lang scheme
;; Exercise 1.19
;; There is a clever algorithm for computing the Fibonacci numbers in a logarithmic
;; number of steps. Recall the transformation of state variables a and b in the fib-iter
;; process of Section 1.2.2: 
;;         a <- a + b
;;         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^n, 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 T(p,q) where T(p,q) transforms the pair (a, b) according to:
;;         a <- bq + aq + ap 
;;         b <- bp + aq
;; Show that if we apply such a transformation T(p,q) twice, the affect is the same as using
;; a single transformation T(p', 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 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 
                   (+ (* p p) (* q q))           ; Computed p'
                   (+ (* q q) (* 2 p q))         ; Computed q' 
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

;; p' and q' are computed by applying the above mentioned transformation Tpq twice
;; and comparing the manipulated equation to Tp'q'
;; we can see that applying the transformation on b <- bp + aq, we get
;; => (bp + aq)p + (bq + aq + ap)q
;; => bpp + aqp + bqq + aqq + apq
;; => bpp + aqq + bqq + 2apq
;; => b(pp + qq) + a(pp + 2ap)    # Compare this to equation of b.
;; => p' = pp + qq & q' = qq + 2pq