侧边栏壁纸
  • 累计撰写 793 篇文章
  • 累计创建 1 个标签
  • 累计收到 1 条评论
标签搜索

目 录CONTENT

文章目录

Stein算法

Dettan
2022-01-09 / 0 评论 / 0 点赞 / 105 阅读 / 288 字
温馨提示:
本文最后更新于 2022-07-23,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
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;
    }
}
0

评论区