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

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

辗转相除法是人工算法；更适合计算机的算法是辗转相减+移位算法

账号		自动登录	找回密码
密码			欢迎注册

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