Stein算法是一种计算两个数最大公约数的算法,是针对欧几里德算法在对大整数进行运算时,需要试商导致增加运算时间的缺陷而提出的改进算法。
#define CHECK(a) (!(1&(a)))//判断是否被2整除
#define CLEAN2(a) while(CHECK(a))a=a>>=1//移除非公因子的2
#define BIGERA if(a<b)(t=a,a=b,b=t)//取较大的数为a
int gcd(int a,int b){
int c_2=0,t;
while((CHECK(a))&&(CHECK(b))){
a=a>>=1;b=b>>=1;c_2++;
}
CLEAN2(a);
CLEAN2(b);
BIGERA;
while(a==((a-b)>>1)){
CLEAN2(a);
BIGERA;
}
return b<<c_2;
}
function stein(a,b) {
if (a==0) {return b;}
if (b==0) {return a;}
var c=0;
while (((a & 1)==0)&&(( b & 1 )==0)) {
a=a>>1;
b=b>>1;
c=c+1;
}
while ((a & 1)==0) {
a=a>>1;
}
while ((b & 1)==0) {
b=b>>1;
}
if (a<b) {
b=(b-a)>>1;
var r=stein(b,a)<<c;
return r;
}
else {
a=(a-b)>>1;
var r=stein(a,b)<<c;
return r;
}
}
评论区