mathematica 发表于 2019-3-26 21:09:18

辗转相除法求最大公约数时，啥时候最慢？

我猜测当斐波那契数列相邻两个大整数的时候最慢，但是我没办法证明，我只是猜测！

.·.·. 发表于 2019-3-27 10:50:30

只是对“你想象中的那种算法”如此
而“你想象中的那种算法”在处理类似斐波那契数列的时候，会自动将取模运算（一次除法获取余数）退化成一次减法
计算机做减法超快的

mathematica 发表于 2019-3-27 11:22:59

.·.·. 发表于 2019-3-27 10:50
只是对“你想象中的那种算法”如此
而“你想象中的那种算法”在处理类似斐波那契数列的时候，会自动将取模 ...

你不觉得做减法的次数太多了吗?

mathematica 发表于 2019-3-27 11:24:27

.·.·. 发表于 2019-3-27 10:50
只是对“你想象中的那种算法”如此
而“你想象中的那种算法”在处理类似斐波那契数列的时候，会自动将取模 ...

你想象中是做减法,实际上,还是在做除法,然后求余数,

gxqcn 发表于 2019-3-27 11:46:17

辗转相除法 是人工算法；更适合计算机的算法是 辗转相减+移位算法
页: [1]
查看完整版本: 辗转相除法求最大公约数时，啥时候最慢？