ずっと前にtwitterで見たのだが、（詳細は忘れた。申し訳ない） フィボナッチ数列は行列を使うと効率的なアルゴリズムになるという趣旨の発言があった。 これがどういう意味かを説明しようと思う。
説明不要だと思うが一応書く。フィボナッチ数列とは以下の三項間漸化式で求められる数列である。 $$F_{n+2}=F_{n+1}+F_n,F_1=1,F_0=0$$ 一般項は以下のようになっている。 $$F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$$ 注：一般項で求める場合は浮動小数点数演算を使用するので誤差が大きくなる。よって今回のプログラムでは一般項は使用しない。
一応注意だが、今回は大きな数を扱うことになるので、$n$項目のフィボナッチ数ではなく、$n$項目のフィボナッチ数を$10^9+7$で割った余りを求めるプログラムを書いている。そこだけは了承してほしい。 また、このページも参考にしてほしい。
フィボナッチ数列を求めるときにまず思いつく方法は再帰である。この場合かなり実装が簡単になる。 ただし引数が大きくなるとそれに伴って元の数も極端に大きくなってしまう。せめて過去のデータを記録するようにして同じ処理を繰り返さないほうがいいだろう。 そのような考えで作られたのが以下のコードである。
前者は（実験していないからわからないがおそらく）指数関数時間のアルゴリズムであり、後者は多項式時間$O(N)$のアルゴリズムである。 多項式時間でもかなり効率的であるように見えるが、以下に書くのは時間計算量$O(\log{N})$のアルゴリズムである。
これは冒頭でも述べたとおり行列の積を使用している。 というのも以下の性質を使用している。 $$\left(\begin{array}{cc}1&1\\1&0\end{array}\right)^n=\left(\begin{array}{cc}F_{n+1}&F_n\\F_n&F_{n-1}\end{array}\right)$$ 証明は数学的帰納法とかで頑張ったら行けるはず。この式を利用して$F_N$を求めるためにまず$N$を２進数表記にする。$N$を２進数表記にしたときの桁数を$M$とする。
そこで、以下の$M$個の行列$A_i,(0\leq i\leq M-1)$をそれぞれ求める。 $$A_i=\left(\begin{array}{cc}1&1\\1&0\end{array}\right)^{2^i}$$ これは$1\leq i\leq M-1$において漸化式 $$A_i=A_{i-1}^2$$ を利用すれば$M$回程度の計算で終わらせることができる。 計算した行列はそれぞれメモリに記録しておく。 また、オーバーフロー防止のために計算するたびに$10^9+7$で割ったあまりを求めるということに気をつけてほしい。
そして$N$が2進数表記で$i_1,i_2,\ldots,i_k(i_1 < i_2 < \cdots < i_k)$桁目が$1$になる場合、 $$A=A_{i_1}A_{i_2}\cdots A_{i_k}$$ というようにかけたら、 $$A=\left(\begin{array}{cc}F_{N+1}&F_N\\F_{N}&F_{N-1}\end{array}\right)$$ というようになるため、$A$の$(1,2)$成分をとればそれがフィボナッチ数列の第$N$項(を$10^9+7$で割ったあまり)が求められるというわけである。
これは入力変数は$N$のみであり、ループ回数は$M\simeq\log_2{N}$回程度なので時間計算量は$O(\log{N})$となる。 また、$N$乗を効率的に計算する問題では今回のように2進数を計算する方法が有効であるためうまくいけば同じように$O(\log{N})$の解法が期待できる。