SICP ex 1.19 - I have no talent.

$a \leftarrow a+b$
$b \leftarrow a$

の変換なので、ベクトルで表すと、

$\left(\begin{array} a+b \\ b \end{array}\right)=T\left(\begin{array} a \\ b \end{array}\right)$

から

$T=\left(\begin{array} 1 & 1 \\ 1 & 0 \end{array}\right)$

$T_{pq}$ は $a \leftarrow bq+aq+ap$ , $b \leftarrow bp+aq$ からベクトルで表すと、

$\left(\begin{array} bq+aq+ap \\ bp+aq \end{array}\right)=T_{pq}\left(\begin{array} a \\ b \end{array}\right)$
$T_{pq}=\left(\begin{array} p+q & q \\ q & p \end{array}\right)$
$T^{2}_{pq}=\left(\begin{array} (p+q)^2+q^2 & q(p+q)+qp \\ q(p+q)+qp & p^2+q^2 \end{array}\right)$
$\left(\begin{array} p'\\ q'\end{array}\right)=\left(\begin{array} p^2+q^2 \\ q(p+q)+pq \end{array}\right)$

から、対数的ステップ数の手続きは、

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