fibonacci(10^14) % 1234567891011是多少?

gracias

如题:
我知道有个公式直接计算fibonacci第n项,可能是这个数太大了,可我还是计算不出来.不知道该怎么求?
.

gxqcn

Fibonacci 直接公式含有无理数，不便计算。

可用矩阵推导其递推式，得到一个整数矩阵的幂，
再用矩阵的模幂计算即可，非常快速。

wayne

1# gracias

mathe

1# gracias


wayne 发表于 2012-2-20 13:47

这里用这个公式用处不大，要用gxqcn的方法
${(F_{n+1}=F_n+F_{n-1}),(F_n=F_n):}$
所以得到
$[(F_{n+1}),(F_n)]=[(1,1),(1,0)][(F_n),(F_{n-1})]$
所以
$[(F_{n+1}),(F_n)]=[(1,1),(1,0)]^{n-1}[(F_2),(F_1)]=[(1,1),(1,0)]^{n-1}[(1),(1)]$

liangbch

根据3楼的公式，fibonacci(10^14)有20万亿位数字，我们的PC显然无法计算。一个可行的做法是，从1开始，每计算几项就求做一次模运算，直到计算到10^14。

mathematica

根据3楼的公式，fibonacci(10^14)有20万亿位数字，我们的PC显然无法计算。一个可行的做法是，从1开始，每计算几项就求做一次模运算，直到计算到10^14。
liangbch 发表于 2012-2-20 19:24

这个问题郭肯定能解决的，因为郭的素性判定算法用到了！

mathematica

这个问题，对于郭，是相当简单的，和模幂算法应该差不多！

mathematica

其中肯定用到了二进制！

wayne

http://en.wikipedia.org/wiki/Pisano_period

http://oeis.org/A001175

Let the prime factorization of n be p1^e1...pk^ek. Then a(n) = lcm(a(p1^e1), ..., a(pk^ek))

mathe

发现这个题目里面模1234567891011不是素数，而且素因子都不大，所以也可以采用wayne在楼上的方法了。
不过还是直接采用4#的方法效率高，只要对n-1采用二进制表示，然后采用通常计算模幂的方法计算出矩阵的n-1次方即可。