论坛 › 算法交流 › fibonacci(10^14) % 1234567891011是多少?

zgg___ 发表于 2012-2-23 15:43:03

m = {{1, 0}, {0, 1}};s = IntegerDigits;
Do] == 0, m.m, m.m.{{1, 1}, {1, 0}}], 1234567891011], {i, Length}];
m[]

wayne 发表于 2012-3-1 13:58:17

31# zgg___
:b:

matlab 发表于 2012-3-3 11:01:32

m = {{1, 0}, {0, 1}};s = IntegerDigits;
Do == 0, m.m, m.m.{{1, 1}, {1, 0}}], 1234567891011], {i, Length}];
m[]
zgg___ 发表于 2012-2-23 15:43 https://bbs.emath.ac.cn/static/image/common/back.gif
运行结果是多少呀？

gxqcn 发表于 2012-3-3 15:20:42

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

Ian 发表于 2012-4-4 16:12:03

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

mathematica 发表于 2012-7-13 09:46:35

m = {{1, 0}, {0, 1}};s = IntegerDigits;
Do == 0, m.m, m.m.{{1, 1}, {1, 0}}], 1234567891011], {i, Length[ s]}];
m[]
zgg___ 发表于 2012-2-23 15:43 https://bbs.emath.ac.cn/static/image/common/back.gif


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

mathematica 发表于 2012-7-13 09:49:09

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

mathematica 发表于 2012-7-13 09:53:25

我的求解结果是:
921144120792

mathematica 发表于 2012-7-13 09:54:24

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

mathematica 发表于 2012-7-13 09:56:30

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

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