斐波那契数列更快，但起始数不同 (F[n]=F[n-1]+F[n-2])

Question

（这里是初学者）

我想知道如何求数列F[n]=F[n-1]+F[n-2]的第n个数。

输入：

F[0] =  a;
F[1] =  b;
a,b < 101
N < 1000000001 
M < 8; M=10^M;

a和b是起始序列号。

n 是我需要查找的序列的第 n 个数。

M取模，数字很快变大所以F[n]=F[n]%10^M，我们求余数，因为只需要第n个数的最后一位

递归方法太慢：

int fib(int n)
{
   if (n <= 1)
      return n;
   return fib(n-1) + fib(n-2);
}

O(n)时间的动态规划解法也太慢了：

f[i] = f[i-1] + f[i-2];

如果序列的第一个数字是 0 和 1（第 n 个数字可以在 O(log n) 中找到），虽然有解决方案可以通过使用以下公式更快地找到第 n 个数字：

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

但是如果起始数字是 25 和 60 这样的数字，这个公式就不起作用了。而且递归方法太慢了。

所以我想知道如何比 O(n) 更快地找到序列的第 n 个数。部分代码会有所帮助。

谢谢。

Answer 1

这个矩阵：

A = / 1  1 \
    \ 1  0 /

乘以列向量(f_n+1, f_n时, 其中f_n 是斐波那契数列中的第 n 个数字，将为您提供列向量 (f_n+2, f_n+1) ，即它将使您前进一步。无论序列的初始元素是什么，这都有效。

例如：

/ 1  1 \ / 8 \  =  / 13 \
\ 1  0 / \ 5 /     \ 8  /

所以第n个斐波那契数是A^n-1v的第一个元素，其中v是包含f₁的列向量和 f₀，序列中的前两个数字。

因此，如果你能快速计算 A^n-1 对某个数取模，这将得到 f_n。这可以使用在 O(logn) 中工作的 Exponentiation by squaring 来完成。只需确保在每次乘法和加法后都执行模运算，以防止数字变得太大。

Fibonacci sequence faster, but with different starting numbers (F[n]=F[n-1]+F[n-2])