- 浏览: 50123 次
- 性别:
- 来自: 西安
文章分类
最新评论
欧几里德算法是计算两个数最大公约数的传统算法,他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷,这个缺陷只有在大素数时才会显现出来。
考虑现在的硬件平台,一般整数最多也就是64位,对于这样的整数,计算两个数之间的模是很简单的。对于字长为32位的平台,计算两个不超过32位的整数的模,只需要一个指令周期,而计算64位以下的整数模,也不过几个周期而已。但是对于更大的素数,这样的计算过程就不得不由用户来设计,为了计算两个超过64位的整数的模,用户也许不得不采用类似于多位数除法手算过程中的试商法,这个过程不但复杂,而且消耗了很多CPU时间。对于现代密码算法,要求计算128位以上的素数的情况比比皆是,设计这样的程序迫切希望能够抛弃除法和取模。
Stein算法由J. Stein 1961年提出,这个方法也是计算两个数的最大公约数。和欧几里德算法 算法不同的是,Stein算法只有整数的移位和加减法,这对于程序设计者是一个福音。
为了说明Stein算法的正确性,首先必须注意到以下结论:
- gcd(a,a) = a,也就是一个数和他自身的公约数是其自身
- gcd(ka,kb) = k gcd(a,b),也就是最大公约数运算和倍乘运算可以交换,特殊的,当k=2时,说明两个偶数的最大公约数必然能被2整除
有了上述规律就可以给出Stein算法如下:
- 如果A=0,B是最大公约数,算法结束
- 如果B=0,A是最大公约数,算法结束
- 设置A1 = A、B1=B和C1 = 1
- 如果An和Bn都是偶数,则An+1 =An /2,Bn+1 =Bn /2,Cn+1 =Cn *2(注意,乘2只要把整数左移一位即可,除2只要把整数右移一位即可)
- 如果An是偶数,Bn不是偶数,则An+1 =An /2,Bn+1 =Bn ,Cn+1 =Cn (很显然啦,2不是奇数的约数)
- 如果Bn是偶数,An不是偶数,则Bn+1 =Bn /2,An+1 =An ,Cn+1 =Cn (很显然啦,2不是奇数的约数)
- 如果An和Bn都不是偶数,则An+1 =|An -Bn|,Bn+1 =min(An,Bn),Cn+1 =Cn
- n++,转4
这个算法的原理很显然,所以就不再证明了。现在考察一下该算法和欧几里德方法效率上的差别。
考虑欧几里德算法,最恶劣的情况是,每次迭代a = 2b -1,这样,迭代后,r= b-1。如果a小于2N,这样大约需要 4N次迭代。而考虑Stein算法,每次迭代后,显然AN+1BN+1≤ ANBN/2,最大迭代次数也不超过4N次。也就是说,迭代次数几乎是相等的。但是,需要注意的是,对于大素数,试商法将使每次迭代都更复杂,因此对于大素数Stein将更有优势。
stein算法实现:
unsigned int gcd(unsigned int a,unsigned int b){
if(!a) return b;
else if(!b) return a;
if(~a&0x1 && ~b&0x1) return 2*gcd(a>>1,b>>1);
else if(~a&0x1 && b&0x1) return gcd(a>>1,b);
else if(a&0x1 && ~b&0x1) return gcd(a,b>>1);
else if(a>b) return gcd(a-b,b);
else return gcd(b-a,a);
}
links
en.wikipedia.org/wiki/Binary_GCD_algorithm
http://hi.baidu.com/cxh198412/blog/item/9977f8668628b121ab184caa.html
http://baike.baidu.com/view/3993128.htm
发表评论
-
[转] 这一生,还能见妈妈几次.......
2012-09-25 20:38 0未能找到原链接,请原 ... -
就叫做诗吧
2012-09-18 22:09 607想找个地方,然后写几句话,就叫做诗吧, 但风也不想惊动 ... -
突然就燃了
2012-04-24 15:58 572无语的题目:找出两个链表的第一个交点,自己说了m*n,以及借用 ... -
【转】 Epoll,Poll,Select模型比较
2012-04-21 16:32 1088目前看到的解释的最透彻又最短小的一篇,赞 http:/ ... -
Henri Poincaré
2012-04-10 22:18 761udi书的引论用了亨利 庞加莱的一段话,好奇,原来是大牛。。。 ... -
Udi Manber大神
2012-04-10 16:29 771首席算法官Udi Manber,这位前Amazon的“首席算法 ... -
位操作一题
2012-04-05 21:53 673An array A[1... n] contains all ... -
带权区间调度
2012-04-05 16:08 2576问题:有一组需求{1,...,n},每个需求i有一个开始结束时 ... -
判断变位词
2012-04-05 14:24 1178题目1:输入字符串s1,s2,判断是否为变位词。 解 ... -
区间调度
2012-04-04 13:31 797问题:有一组需求{1,...,n},每个需求i有一个开 ... -
广告牌放置问题
2012-04-03 19:39 0题目: -
网络传输
2012-03-31 16:03 538写这篇短文心里很难过的说,多个节点之间怎样快速传输数据, ... -
IBM的说
2012-03-30 10:06 500接到IBM的实习邀请,虽然公司是主动方,而且人家主动提供机会给 ... -
SPDY协议
2012-03-29 16:10 720很nice的一个协议,google开发,据说正在提交IETF标 ... -
Dutch national flag problem
2012-03-29 09:18 1094这个题目:separate negative and posi ... -
有序数据求交集
2012-03-28 11:22 651网上看到一道老题:两个有序数组a与b,求两者的交集。 ... -
日程安排问题
2012-03-27 22:57 777<算法基础>上的贪婪算法讲的真是好啊,分析的很精到 ... -
paul Graham大神,你又扯淡了不是
2011-12-29 16:21 666lisp是黑客语言? Graham言之凿凿,<黑 ... -
飘零吧,思考的编码
2011-12-27 20:50 597本专题是读书时的札记,不断更新。。。 梭罗认为,我们已经成为 ... -
满园MD5 都hold不住寥
2011-12-23 22:37 655方哥的文章,不知是否方牛写的,拿来。。。 昨天程序员网 ...
相关推荐
用c#实现的最大公约数算法欧几里德和stein,递归和非递归的都有了,stein算法在大数方面比欧几里德要好些
Stein算法是一种计算两个数最大公约数的算法,是针对欧几里德算法在对大整数进行运算时,需要试商导致增加运算时间的缺陷而提出的改进算法。欧几里德算法是计算两个数最大公约数的传统算法,无论从理论还是从实际...
自己写的jsp+servlet演示程序+实验报告,有源代码和war包,如果有自己的服务器,直接上传至tomcat下的webappp就可以演示了
9.6.2 计算最大公约数算法一一Stein算法 288 9.6.3 计算最大公约数示例 289 9.7 最小公倍数 290 9.8 素数 292 9.8.1 素数概述 292 9.8.2 计算素数算法 292 9.9 回文素数 294 9.9.1 回文素数概述 294 9.9.2 ...
为了验证Euclid算法和Stein算法在高精度条件下的真实运行效率,以随机生成的多组高精度正整数,并分别按同位、异位、完全随机、斐波那契数列相邻项4种情况对这两种最大公约数算法的平均执行效率进行比较。...
求两个数的最大公约数,使用了Stein算法和欧几里得算法
Instructorís Manual by Thomas H. Cormen Clara Lee Erica Lin to Accompany Introduction to Algorithms Second Edition by Thomas H. Cormen Charles E....Ronald L....Clifford Stein 算法导论详细答案
Stein 算法,第 4 版,作者:Robert Sedgewick 和 Kevin Wayne 算法设计手册,第 2 版,Steven Skiena 破解编码访谈,第 6 版,作者:Gayle Laakmann Mcdowell 在线资源: 算法,由 Robert Sedgewick 和 Kevin Wayne...
实现求两个整数的最大公约数和最小公倍数。求两个数的最大公约数和最小公倍数的方法有很多种,常用的有欧几里得算法和Stein算法。
《算法导论》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein四人合作编著(其中Clifford Stein是第二版开始参与的合著者)。本书的最大特点就是将严谨性和全面性融入在了一起。
《算法导论》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein四人合作编著(其中Clifford Stein是第二版开始参与的合著者)。本书的最大特点就是将严谨性和全面性融入在了一起。
《算法导论》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein四人合作编著(其中Clifford Stein是第二版开始参与的合著者)。本书的最大特点就是将严谨性和全面性融入在了一起。 本书...
《算法导论》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein四人合作编著(其中Clifford Stein是第二版开始参与的合著者)。本书的最大特点就是将严谨性和全面性融入在了一起。
1:利用辗转相除法(函数嵌套和函数递归)、穷举法、更相减损术、Stein算法(非递归和递归)求出两个数的最大公约数或者/和最小公倍数 2:求每个函数运行时间,进行比较获得最长及最短平均运行时间。
《算法导论》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein四人合作编著(其中Clifford Stein是第二版开始参与的合著者)。本书的最大特点就是将严谨性和全面性融入在了一起。
《算法导论》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein四人合作编著(其中Clifford Stein是第二版开始参与的合著者)。本书的最大特点就是将严谨性和全面性融入在了一起。
《算法导论》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein四人合作编著(其中Clifford Stein是第二版开始参与的合著者)。本书的最大特点就是将严谨性和全面性融入在了一起。