; Transformation
; Tpq
; a <- bq + aq + ap
; b <- bp + aq
; 
; Let p' = p^2 + q^2 and q' = 2pq + q^2
; Then
; Tp'q' = (Tpq)^2
; 
; TODO(adrs): proof
; 
; Fibonacci transform is Tpq for p = 0, q = 1
; a <- a + b
; b <- a
; 
; Then Tfib^2 is:
; a <- 2a + b
; b <- a + b

; Invariant: Fib(n + 1), Fib(n) = (Tpq)^count (a, b)
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         ; Fib(n + 1), Fib(n) = (Tpq^2)^(count/2) (a, b)
         (fib-iter a
                   b
                   (+ (square p) (square q))
                   (+ (* 2 p q) (square q))
                   (/ count 2)))
        ; Fib(n + 1), Fib(n) = (Tpq)^(count - 1)(Tpq(a, b))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

(define (fib n) (fib-iter 1 0 0 1 n))