algorithm - 找出非常大的 'n' 的第 n 个斐波那契数

Question

我想知道如何找到一个非常大的 n 值(比如 1000000)的斐波那契数列的第 n 项。使用小学递归方程 fib(n)=fib(n-1)+ fib(n-2)，找到第 50 项需要 2-3 分钟!

谷歌搜索后，我开始了解 Binet 的公式，但它不适用于 n>79 的值，因为据说 here

有没有像我们寻找素数那样的算法？

Answer 1

可以使用矩阵求幂法(线性递推法)。您可以在 this 中找到详细的解释和程序。或 this博客。运行时间为 O(log n)。

我认为没有更好的方法来做到这一点。