最大公约数与欧几里德算法

网友投稿 1316 2022-10-02

最大公约数与欧几里德算法

最大公约数与欧几里德算法

记a、b的最大公约数为gcd(a,b)。

这里对于最大公约数的讨论仅限于非负整数,因为显然有gcd(a,b)=gcd(|a|,|b|)。计算最大公约数的Euclid算法基于下面定理:【GCD递归定理】对于任意非负整数a和任意正整数b,gcd(a,b)=gcd(b,a%b)。Euclid算法最简单的递归版本(C语言版)如下:

#include #includeusing namespace std;int Euclid(int a,int b){ if(b) return Euclid(b,b%a); else return a;}int main(){ int n=54,m=63; printf("%d",Euclid(n,m));//输出9 return 0;}

迭代版本(C语言版)如下:

#include #includeusing namespace std;int Euclid(int a,int b){ while(a=a%b) a^=b^=a^=b; return b;}int main(){ int n=54,m=63; printf("%d",Euclid(n,m));//输出9 return 0;}

Euclid算法运行时间分析

【引理】如果a>b≥1且Euclid(a,b)执行了k≥1次递归调用,则a≥Fk+2,b≥Fk+1。(其中Fk为Fabonacci的第k项)

【Lamé定理】对于任意k≥1,若a>b≥1且b

O(log b)是该算法一个粗略的界,事实上当b确定后,Euclid(a,b)的平均迭代次数近似为(12ln2/π2)×lnb。

求最大公约数的Euclid算法需要用到大量的取模运算,这在大多数计算机上是一项复杂的工作,相比之下减法运算、测试数的奇偶性、折半运算的执行速度都要更快些。 二进制最大公约数算法避免了Euclid算法的取余数过程。 二进制最大公约数基于下述事实: 若a、b都是偶数,则gcd(a,b)=2*gcd(a/2,b/2) 若a是奇数、b是偶数,则gcd(a,b)=gcd(a/2,b/2) 若a、b都是奇数,则gcd(a,b)=gcd((a-b)/2,b) 因此可写出二进制最大公约数算法如下(C语言版):

int gcd(int a,int b){ int c=1; while(a-b){ if(a&1){ if(b&1){ if(a>b)a=(a-b)>>1;else b=(b-a)>>1; } else b>>=1; } else{ if(b&1)a>>=1;else c<<=1,a>>=1,b>>=1; } } return c*a;}

或者

int gcd(int u,int v){ int k=1,t; while(~u&1 && ~v&1) k<<=1,u>>=1,v>>=1; t=(u&1)?-v:u>>1; do{ while(~t&1)t>>=1; if(t>0) u=t; else v=-t; }while(t=u-v); return u*k;}

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:#include
下一篇:微信开发中使用async/await(微信是用什么开发出来的)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~