豊橋→京都→東京

京都にいたのは2時間ぐらいでした．京大からタクシーをひろって駅までいこうとした直前に京大のH氏に出会い，立ち話をしそうになったので，「新幹線に乗らないといけないから」といってなんとか振り切ろうとしましたが「新幹線なんか遅れてもいいじゃん」というような理由になっていないような理由で引き止められ，2分ぐらい立ち話をしてしまったため，京都駅で猛ダッシュをしてぎりぎり新幹線に乗れたところだったので，かなり疲れました．
その後，コマゼミに予定通り到着．品川駅でも走ったため予定よりも早く駒場に着きました．
久々のコマゼミは楽しかったです．

フィボナッチ数の計算

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です．