非常に大きな'n'に対してn番目のフィボナッチ数を求める。

質問

フィボナッチ数列の第n項が非常に大きな値、例えば1000000である場合、どのようにして求めることができるかについて考えていました。小学校で習う漸化式を使うと fib(n)=fib(n-1)+fib(n-2) を使うと、50 番目の項を見つけるのに2-3分かかります!

ググってみたら、Binetの公式を知ったのですが、n>79の値では適切ではないそうです。 ここで

素数を求めるのと同じように、そのためのアルゴリズムはあるのでしょうか？

どのように解くのですか？

行列の累乗法(線形漸化法)を利用します。 詳しい説明と手順は この のブログで紹介しています。実行時間は O (ログ n ).

これ以上の方法はないと思います。