;;;; Structure and Interpretation of Computer Programs
  Chapter 1 Section 2 Procedures and the Processes They Generate

  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 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 Tn , 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 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   gives us an explicit way to
  square these transformations , and thus we can compute Tn 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
                   (+ (* p p) (* q q)) ; p'
                   (+ (* q q) (* 2 p q)) ; q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

; Appling Tpq twice and some algebraic grunt work we find that ...
;
; a, b
  bp+aq+ap , bp+aq
; (bp+aq)q + (bq+aq+ap)q + (bq+aq+ap)p, (bp+aq)p + (bq+aq+ap)q
;
; ... reduces to 
  b(q^2 + 2pq ) + a[(p^2+q^2)+(q^2 + 2pq ) ] , b(p^2+q^2 ) + a(q^2 + 2pq )
;
  From which we find that p ' is ( p^2+q^2 ) and q ' is ( q^2 + 2pq )
; Or, perhaps more clearly in prefix notation, and for Scheme: 
;
; p' is (+ (* p p) (* q q))
  q ' is ( + ( * q q ) ( * 2 p q ) )

 Structure and Interpretation of Computer Programs
 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,
 produces the pair Fib(n + 1) and Fib(n). In other words, the Fibonacci numbers are
 twice, the effect is the same as using a single transformation Tp'q' of the same
 as in the fast-expt procedure. Put this all together to complete the following
 procedure, which runs in a logarithmic number of steps:
 p'
 q'
 Appling Tpq twice and some algebraic grunt work we find that ...

 a, b
 (bp+aq)q + (bq+aq+ap)q + (bq+aq+ap)p, (bp+aq)p + (bq+aq+ap)q

 ... reduces to 

 Or, perhaps more clearly in prefix notation, and for Scheme: 

 p' is (+ (* p p) (* q q))
  Chapter 1 Section 2 Procedures and the Processes They Generate

  Exercise 1.19

  and observe that applying T over and over again n times , starting with 1 and 0 ,
  produced by applying Tn , 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 and b<-bp + aq . Show that if we apply such a transformation Tpq
  form , and compute p ' and q ' in terms of p and   gives us an explicit way to
  square these transformations , and thus we can compute Tn using successive squaring ,

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

  bp+aq+ap , bp+aq
  b(q^2 + 2pq ) + a[(p^2+q^2)+(q^2 + 2pq ) ] , b(p^2+q^2 ) + a(q^2 + 2pq )
  From which we find that p ' is ( p^2+q^2 ) and q ' is ( q^2 + 2pq )
  q ' is ( + ( * q q ) ( * 2 p q ) )
