论坛 › 计算机数学 › fibonacci(10^14) % 1234567891011是多少?

公子相 发表于 2024-1-9 17:11:10

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

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

oasuoxi 发表于 2024-1-9 17:12:01

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

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

dingji 发表于 2024-1-9 17:12:43

1# gracias
http://upload.wikimedia.org/wikipedia/en/math/6/b/5/6b53a73248d35568fc4f1e561b127202.png
http://upload.wikimedia.org/wikipedia/en/math/9/8/a/98a1f6974f068111f6fdc922620ffc69.png

ahqhegudiz 发表于 2024-1-9 17:13:13

1# gracias
http://upload.wikimedia.org/wikipedia/en/math/6/b/5/6b53a73248d35568fc4f1e561b127202.png
http://upload.wikimedia.org/wikipedia/en/math/9/8/a/98a1f6974f068111f6fdc922620ffc69.png
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)]$

Zpasarbola 发表于 2024-1-9 17:13:27

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

asomiajht 发表于 2024-1-9 17:13:44

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

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

ebirugerxos 发表于 2024-1-9 17:14:39

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

dingji 发表于 2024-1-9 17:14:54

其中肯定用到了二进制！

duhiladikiti 发表于 2024-1-9 17:15:15

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))

ouukucakac 发表于 2024-1-9 17:15:45

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

查看完整版本: fibonacci(10^14) % 1234567891011是多少?