C++算法——Stein算法

2022/12/29 C++ 算法 Stein算法 gcd

Stein算法是更相减损术的改进。

求gcd(a,b)时，可以分为几种情况进行优化。 1. a和b都是偶数。gcd(a,b)=2*gcd(a/2,b/2) 2. a b一奇一偶(不妨a奇b偶)。gcd(a,b)=gcd(a,b/2) 3. a和b都是奇数。gcd(a,b)=gcd((a+b)/2,(a-b)/2) 结束条件 gcd(a,a)=a

Stein算法只用到加减法和移位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
int stein_gcd(int a,int b) //递归形式
{
    if(a<b)
        a^=b,b^=a,a^=b;
    if(b==0)
        return a;
    if((!(a&1))&&(!(b&1)))
        return stein_gcd(a>>1,b>>1)<<1;
    else if((a&1)&&(!(b&1)))
        return stein_gcd(a,b>>1);
    else if((!(a&1)&&(b&1)))
        return stein_gcd(a>>1,b);
    else
        return stein_gcd(a-b,b);
}

int stein(int a,int b) //循环形式
{
    int k=1;        //k用来记录2的次幂
    while((!(a&1))&&(!(b&1)))
    {
        k<<=1;
        a>>=1;
        b>>=1;
    }
    while(!(a&1))
        a>>=1;
    while(!(b&1))
        b>>=1;
    if(a<b)
        a^=b,b^=a,a^=b;
    while(a!=b)
    {
        a-=b;
        if(a<b)
            a^=b,b^=a,a^=b;
    }
    return k*a;
}
img_show