フィボナッチ数の計算

f(n)=f(n-1)+f(n-2)という式で定義されているとすれば，2次元ベクトルv(n)=(f(n), f(n-1))^Tを定義して，2行2列行列Aを第1行が(1,1)，第2行が(1,0)となるように定義すれば．v(n)=Av(n-1)という線形漸化式が成り立つので，f(n)を計算するためにはAのn乗を計算すればよくって，それをO(log n)回の四則演算で計算すれば√5が出てくる余地はなくて，すべて自然数の計算でできることになります．はい．
またSICPにはこれと似た末尾再帰的なO(log n)アルゴリズムが演習問題として出ていたと思います．
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html のExercise 1.19です．