2.7 最大公约数问题

问题描述：

求2个正正数的最大公约数，如果2个数很大，有什么简单的算法吗？ 

解法1：辗转相除法 

假设f(x, y) 表示x,y的最大公约数是g，而k=x/y,b=x%y，则g必能整出b。
因为x=ky + b，b=x-ky，b/g=(x-ky)/g一定为整数，所以必有g整除b。
如下所示：
f(42, 30) = f(30, 12) = f(12, 6)= f(6, 0) = 6
代码如下：

int gcd(int x , int y)  
{  
   return (y == 0 )?x :gcd(y , x % y) ;    
} 

解法二：辗转相减法

解法1用到取模运算，大于大整数而言，取模运算开销昂贵，所以用相减 

int gcd(int x , int y)
{
	if(x<y)
		return gcd(y,x) ;  
    else if(y == 0)
    	return x ;
    else
    	return gcd(x-y,y);        
} 

解法三：综合

解法一的问题在于计算复杂的大整数除法运算，解法二将除法改为减法，降低了复杂度，但是迭代次数增多，如何折中？
若x，y均为偶数， f(x,y) = 2*f(x/2,y/2) = 2*f(x>>1,y>>1)
若x为偶数，y为奇数，f(x,y) = f(x/2,y) = f(x>>1,y)
若x为奇数，y为偶数，f(x,y) = f(x,y/2) = f(x,y>>1)
若x，y均为奇数， f(x,y) = f(y,x-y)

此解法结合了上述两种方法：
第一种方法递归次数相当少但每次取模挺耗时，而第二种递归可能会相当多，
但每次运算都是减法运算，很快。
综合两者，用2为基数，可以保证递归次数不那么多，同时运算也快。

int gcd(int x , int y)  
{  
	if(x < y)  
		return gcd(y , x) ;  
  	if(y == 0)  
    	return x ;  
   	if(isEven(x)) //x为奇  
   	{  
    	if(isEven(y)) //y为奇             
        	return gcd(x - y, y) ;           
    	else         //y为偶  
        	return gcd(x , y >>1) ;              
   }      
   else         //x为偶  
   {  
    	if(isEven(y)) //y为奇数              
    		return gcd(x >> 1, y) ;           
     	else         //y为偶  
        	return 2 * gcd(x >> 1, y >> 1) ;        
   }     
}