Stein算法

欧几里德算法(辗转相除法)是计算两个数最大公约数的传统算法，它无论从理论还是从效率上都是很好的。但是它有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。
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加1，转1 考虑欧几里德算法，最恶劣的情况是，每次迭代a=2b-1,这样，迭代后，r=b-1。如果a小于2N，这样大约需要4N次迭代。而考虑Stein算法，每次迭代后，显然A(n+1)B(n+1)≤AnBn/2，最大迭代次数也不超过4N次。也就是说，迭代次数几乎是相等的。但是，需要注意的是，对于大素数，试商法将使每次迭代都更复杂，因此对于大素数Stein将更有优势。
//下面是根据该原理写的实现函数
unsigned MaxDivisor(unsigned a, unsigned b)
{
unsigned c = 0;
while(1)
{
// 退出条件
if(a==0)
return b << c;
else if(b == 0)
return a << c;
// 为提高速度，避免用取模判断奇偶
if(!(a & 1) && !(b & 1)) //a,b 都是偶数
{
a >>= 1; b >>= 1; ++c;
}
else if(!(a & 1) && (b & 1)) //a偶 b奇
{
a >>= 1;
}
else if((a & 1) && !(b & 1)) //a奇 b偶
{
b >>= 1;
}
else if((a & 1) && (b & 1)) //a,b都是奇数
{
unsigned tmp = a>b?b:a; //取较小的一个
a = a>b?a-b:(b-a); //绝对差值
b = tmp;
}
}
}