转自http://www.programfan.com/club/showbbs.asp?id=227318&page=1

bpttc的发言

int GCD_Stein( int x, int y )
{
        int factor = 0;
        int temp;

        if ( x < y )
        {
                temp = x;
                x = y;
                y = temp;
        }
        while ( x != y )
        {
                if ( x & 0x1 )
                {/* when x is odd */
                        if ( y & 0x1 )
                        {/* when x and y are both odd */
                                y = ( x - y ) >> 1;
                                x -= y;
                        }
                        else
                        {/* when x is odd and y is even */
                                y >>= 1;
                        }
                }
                else
                {/* when x is even */
                        if ( y & 0x1 )
                        {/* when x is even and y is odd */
                                x >>= 1;
                                if ( x < y )
                                {
                                        temp = x;
                                        x = y;
                                        y = temp;
                                }
                        }
                        else
                        {/* when x and y are both even */
                                x >>= 1;
                                y >>= 1;
                                ++factor;
                        }
                }
        }
        return ( x << factor );
}

Stein算法

对两个正整数 x>y ：
1.均为偶数 gcd(x,y)=2gcd(x/2,y/2)；
2.均为奇数 gcd(x,y)=gcd((x+y)/2,(x-y)/2)；
2.x奇y偶   gcd(x,y)=gcd(x,y/2)；
3.x偶y奇   gcd(x,y)=gcd(x/2,y) 或 gcd(x,y)=gcd(y,x/2)；（注意此时判断 x/2和y的大小）

评论