Ex. 1.19

sicp

あ、確かに。
http://d.hatena.ne.jp/yukichanko/20090823/1251036936
そういえばこの辺り面倒くさくなって説明すっ飛ばした記憶があるなあとか思い出した。
このやり方なかなか巧妙で、変換を続けて行っても常に同じ形式になるように上手く項を調整していて、その項を調整することで計算するという方法で、実際には粛々と計算して整理すれば答は出るんだけど、"a <- bq + aq + ap and b <- bp + aq."とか、ついつい「なに天下りに式押し付けてんなうだー」とか勝手なこと思ってしまい（バカ丸出し）なかなか文面が頭に入らなかった。結局まともに問題読まずに行列に置き換えて考えてしまった。思い出したので備忘録代わり。
下のような変換行列Tを考える
{\bf T} = \left\(\begin{array}1 & 1 \\ 1 & 0 \end{array}\right\)
これを作用させるとfibが一段進むことになる。
{\bf T} \left\(\begin{array}Fib(n) \\ Fib(n-1) \end{array}\right\)= \left\(Fib(n) + Fib(n-1) \\ Fib(n)\right\)
すなわち、
Fib(n) = {\bf T}^n \left\(\begin{array}1\\0\end{array}\right\)
でまあ、このT^nを素直に対数式に計算してやっても良いのだけれど、ここでふと元の問題ではパラメータ２つでできているのにナゼ４つのまま、、、と悔しくなる（更にバカ）。質量保存じゃなくて要素数保存の法則（そんなんあるのかな）に反する。
すぐに考えつくのは 対象行列の n乗だから当然T_10, T_01は同じ。これで３つ。更に T_11は常に T_00 - T_10で表せるので２つでおK。これらをふまえて更にSICPにあわせて p = T_00, q = T_10 と置いてやると、
p_{double} = p^2 + q^2
q_{double} = pq + q T_{11} = pq + q(p - q) = 2pq - q^2
となる。なんと、行列から進んでもほとんど同じような形になるんだけど、最後の符号だけ逆だ。不思議、と思ったところで放置してしまったらしい。とChangeLogを見てみたら書いてあった。
折角なのでhaskellで書いてみた。

fib :: Integer -> Integer
fib n = inner 1 0 1 1 n where
    inner a b p q n 
	| n == 0   = a
	| even n   = inner
			(a)
			(b)
			(p*p + q*q)
			(2*p*q - q*q)
			(n `div` 2)
	| otherwise= inner
			(a*p + b*q )
			(q*a + (p-q)*b)
			(p)
			(q)
			(n -1)

実行。。

*Main> fib 10
89
*Main> fib 1000
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

はええ。当たり前だけど。