arongnet 阅读(1285) 评论(25)

Stein算法

欧几里德算法是计算两个数最大公约数的传统 算法,他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷,这个缺陷只有在大素数时才会显现出来。

考虑现在的硬件平台,一般整数最多也就是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算法如下:

  1. 如果A=0,B是最大公约数,算法结束
  2. 如果B=0,A是最大公约数,算法结束
  3. 设置A1 = A、B1=B和C1 = 1
  4. 如果An和Bn都是偶数,则An+1 =An /2,Bn+1 =Bn /2,Cn+1 =Cn *2(注意,乘2只要把整数左移一位即可,除2只要把整数右移一位即可)
  5. 如果An是偶数,Bn不是偶数,则An+1 =An /2,Bn+1 =Bn ,Cn+1 =Cn (很显然啦,2不是奇数的约数)
  6. 如果Bn是偶数,An不是偶数,则Bn+1 =Bn /2,An+1 =An ,Cn+1 =Cn (很显然啦,2不是奇数的约数)
  7. 如果An和Bn都不是偶数,则An+1 =|An -Bn|,Bn+1 =min(An,Bn),Cn+1 =Cn
  8. n++,转4

这个算法的原理很显然,所以就不再证明了。现在考察一下该算法和欧几里德方法效率上的差别。

考虑欧几里德算法,最恶劣的情况是,每次迭代a = 2b -1,这样,迭代后,r= b-1。如果a小于2N,这样大约需要 4N次迭代。而考虑Stein算法,每次迭代后,显然AN+1BN+1≤ ANBN/2,最大 迭代次数也不超过4N次。也就是说,迭代次数几乎是相等的。但是,需要注意的是,对于大素数,试商法将使每次迭代都更复杂, 因此对于大素数Stein将更有优势。


评论列表
joyce
re: Stein算法,另外一个计算最大公约数的方法
求stein算法c++程序
C
re: Stein算法,另外一个计算最大公约数的方法
// m= m>n ? m=n:n-m;   //m=abs(m-n); 
//错了错了!改一下

int g_cd2(int a,int b)
{
    int c=1;
    int m=a,n=b;
    while(m!=0&&n!=0)
    {
        if (m%2==0&&n%2==0)
        {
           m /= 2;
           n /= 2;
           c *= 2;
           continue;   
        }
        if (m%2==0&&n%2!=0)
        {
           m /= 2;
           continue;
        }
        if (m%2!=0&&n%2==0)
        {
           n /= 2;
           continue;
        }
        if (m%2!=0&&n%2!=0)
        {
           int i=m;
           m= m>n ? m-n:n-m;   //m=abs(m-n);
           if(i<n)
               n=i;
           continue;
        }   
    }
    if (m==0)
       return n*c;
    if (n==0)
       return m*c;
}
masm
re: Stein算法,另外一个计算最大公约数的方法
此算法采用汇编语言编写效率更高
masm
re: Stein算法,另外一个计算最大公约数的方法
特别是大数(32位以上)
masm
re: Stein算法,另外一个计算最大公约数的方法
lover_P 你好
该算法所基于
gcd(a,a) = a
gcd(ka, kb) = k gcd(a, b)

gcd(a/da, b) = gcd(a, b) 
其中da是a的(质因数)且不是b的约数;类似的: 
gcd(a, b/db) = gcd(a, b) 
至于你说
“gcd(a/da, b) = gcd(a, b) 
其中da是a的约数而不是b的约数;类似的: 
gcd(a, b/db) = gcd(a, b) ”
我亦不敢苟同

123
re: Stein算法,另外一个计算最大公约数的方法
123
jove
re: Stein算法,另外一个计算最大公约数的方法
考虑欧几里德算法,最恶劣的情况是,每次迭代a = 2b -1,这样,迭代后,r= b-1。如果a小于2N,这样大约需要 4N次迭代。而考虑Stein算法,每次迭代后,显然AN+1BN+1≤ ANBN/2,最大迭代次数也不超过4N次。也就是说,迭代次数几乎是相等的。但是,需要注意的是,对于大素数,试商法将使每次迭代都更复杂,因此对于大素数Stein将更有优势。

不是很明白,能否细讲一下
linky
re: Stein算法,另外一个计算最大公约数的方法
#include <iostream.h>
unsigned int ComDiv(unsigned int nParam1,unsigned int nParam2)
{
unsigned int m,n,nTemp;
n=nParam1;
m=nParam2;
while(m!=0)               //求n和m的最大公约数
    {
nTemp=n%m;
n=m;
m=nTemp;
}
return n;
}
int main()
{
cout<<ComDiv(6,10)<<endl;
return 0;
}
zmp
re: Stein算法,另外一个计算最大公约数的方法
用得了这么麻烦吗?有是可以更简单吗。
zmp
re: Stein算法,另外一个计算最大公约数的方法
我这儿的比你们的简单多了。
zero_create
re: Stein算法,另外一个计算最大公约数的方法
//最大公约数
int MaxFractor(int a, int b)
{
int k=0;
int min=0;
int max=0;
if (abs(a)>abs(b))
{
min=b;
max=a;
}
else
{
min=a;
max=b;
}

int maxI = sqrt(min)+1;
for (int i=1; i<=maxI; i++)
{
k=min/i;
if (min%i==0 && max%k==0)
{
break;
}
}
if (i>maxI)
{
return 1;
}
else
{
return k;
}
Rester
re: Stein算法,另外一个计算最大公约数的方法
zero_create :小问题,数量级如果上10^100你会崩溃的,那是c语言的标准算法(对比较小的数而言)!毕竟数学很牛的!
Rester
re: Stein算法,另外一个计算最大公约数的方法
不好意思,那是欧几里德算法!突然想清楚考二级c的问题,“为什么最大公约数要这么算”!终于了解了!
H_轩
re: Stein算法,另外一个计算最大公约数的方法
能给个具体的汇编程序吗
daniel sun
re: Stein算法,另外一个计算最大公约数的方法
这是微软的一个sdk里的代码,可以参考一下,我觉得比较简单也高效
int GCD(int a, int b)
{
int gcd;

if (a < b)
{
gcd = GCD(b, a);
}
else
{
assert(a > 0);
assert(b >= 0);

while (b != 0)
{
int t = a % b;
a = b;
b = t;
}

gcd = a;
}

return gcd;
}
Viking
re: Stein算法,另外一个计算最大公约数的方法
daniel sun  
这个也是欧几里德算法吧?
zsp
re: Stein算法,另外一个计算最大公约数的方法
int gcd(int a,int b){
while(a!=b)
{
if(a>b) a-=b;
else b-=a;
}
return a;/*or return b*/
}
z
re: 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);
}
re
re: Stein算法,另外一个计算最大公约数的方法
如果从硬件的结构来理解的话这个算法是有一定优势的,主要是不用mod运算,只是用了移位和加法。
你二大爷
re: Stein算法,另外一个计算最大公约数的方法
你 从那里抄来的,和别人的一模一样,int i=353323489,j=143423145;运行时,运行1000万次,你这个需要29秒,欧几里德只要7秒,你丫下次再抄袭别人的,而且不运行,我抽死你丫
arong
为什么stein比欧几里德好
原因如下:
对于小的数而已,int a,b;
a%b非常容易

而对于特别大的数,计算机编程中进行取余数、除法都是极其复杂的,而判断数是不是奇数(看最后一bit)和除以2(向右移位)是非常非常简单的,因为这个原因,在数特别大的时候,stein就显得特别好了

发表评论
切换编辑模式