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

zgg___

1. m = {{1, 0}, {0, 1}};s = IntegerDigits[10^14 - 1, 2];
2. Do[m = Mod[If[s[[i]] == 0, m.m, m.m.{{1, 1}, {1, 0}}], 1234567891011], {i, Length[s]}];
3. m[[1, 1]]

复制代码

wayne

31# zgg___

matlab

m = {{1, 0}, {0, 1}};s = IntegerDigits[10^14 - 1, 2]; Do[m = Mod] == 0, m.m, m.m.{{1, 1}, {1, 0}}], 1234567891011], {i, Length}]; m[[1, 1]] zgg___ 发表于 2012-2-23 15:43

运行结果是多少呀？

gxqcn

与 mathe 在11# 给出的结果一致。

Ian

費氏數列有很多同餘的性質, 當n很大時, 可以此降低n的大小 比如 5^k|F_{5^k} 因此, {F_n mod 5^k} 其實是週期數列 In particular, F_n = F_{n mod 5^k} mod 5^k.

mathematica

m = {{1, 0}, {0, 1}};s = IntegerDigits[10^14 - 1, 2]; Do[m = Mod] == 0, m.m, m.m.{{1, 1}, {1, 0}}], 1234567891011], {i, Length[ s]}]; m[[1, 1]] zgg___ 发表于 2012-2-23 15:43

我觉得zgg__的最后一行的代码应该是错误的!

mathematica

1. (*问题:fibonacci(10^14) % 1234567891011是多少?*)
2. (*问题网址:http://bbs.emath.ac.cn/thread-4054-1-1.html*)
3. (*参考资料:http://en.wikipedia.org/wiki/Modular_exponentiation*)
4. Clear["Global`*"];(*Clear all variables*)
5. result={{1,0},{0,1}};(*单位矩阵*)(*也是最终的求解的模幂的结果矩阵*)
6. base={{1,1},{1,0}};(*模幂的底,此处是矩阵*)
7. modulus=1234567891011;(*模*)
8. n=10^14;
9. exponent=n-1;(*模幂的指数*)
10. (*循环计算,此处是矩阵的乘法运算符号 . ,而不是 * 这个运算符号*)
11. While[
12. exponent>0,
13. If[ Mod[exponent,2]==1,
14. (*如果是奇数按照下列方式处理,以及处理指数*)
15. result=Mod[result.base,modulus];exponent=exponent-1,
16. (*如果是偶数,按照下列方式处理,以及处理指数*)
17. base=Mod[base.base,modulus];exponent=exponent/2
18. ]
19. ];
20. out=result.{{1},{1}};(*模幂的最后的矩阵再乘以列向量*)
21. out[[2,1]](*第二行第一列是所要求得到的结果*)

复制代码

上面的是我的代码!!!!!!!!!!!!!!

mathematica

我的求解结果是: 921144120792

mathematica

如果把底矩阵换成: base={{1,2},{1,3}};(*模幂的底,此处是矩阵*) 就可以看出我的代码的求解结果与 zgg的求解结果是有差别的!

mathematica

1. Clear["Global`*"];(*Clear all variables*)
2. m = {{1, 0}, {0, 1}};s = IntegerDigits[10^14 - 1, 2];
3. Do[m = Mod[If[s[[i]] == 0, m.m, m.m.{{1, 2}, {1, 3}}], 1234567891011], {i, Length[s]}];
4. m[[1, 1]]

复制代码

zgg的求解结果是: 1014272271491

1. (*问题:fibonacci(10^14) % 1234567891011是多少?*)
2. (*问题网址:http://bbs.emath.ac.cn/thread-4054-1-1.html*)
3. (*参考资料:http://en.wikipedia.org/wiki/Modular_exponentiation*)
4. Clear["Global`*"];(*Clear all variables*)
5. result={{1,0},{0,1}};(*单位矩阵*)(*也是最终的求解的模幂的结果矩阵*)
6. base={{1,2},{1,3}};(*模幂的底,此处是矩阵*)
7. modulus=1234567891011;(*模*)
8. n=10^14;
9. exponent=n-1;(*模幂的指数*)
10. (*循环计算,此处是矩阵的乘法运算符号 . ,而不是 * 这个运算符号*)
11. While[
12. exponent>0,
13. If[ Mod[exponent,2]==1,
14. (*如果是奇数按照下列方式处理,以及处理指数*)
15. result=Mod[result.base,modulus];exponent=exponent-1,
16. (*如果是偶数,按照下列方式处理,以及处理指数*)
17. base=Mod[base.base,modulus];exponent=exponent/2
18. ]
19. ];
20. out=result.{{1},{1}};(*模幂的最后的矩阵再乘以列向量*)
21. out[[2,1]](*第二行第一列是所要求得到的结果*)

复制代码

而我的求解结果是: 788935779506