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