工夫すると、計算オーダーを n log n にすることが出来る

行列の形でフィボナッチ数列の漸化式を記述すると
|0 1|^n |0|
|1 1| . . |1|
でn番目とn+1番目のフィボナッチ数が求まることがわかる

この式を用いれば
計算オーダー n log n で正確に n 番目のフィボナッチ数を求めることができる