問題解決ノート(36)——最大公約数問題

2つの正の整数の最大公約数を求めます.
考え方:これはとても基本的な問題で、最もよく見られるのは2つの方法で、転がり相除算法と転がり相減算法です.一般式は、それぞれf(x,y)=f(y,x%y)、f(x,y)=f(y,x−y)(x>=y>0)である.一般式に基づいてアルゴリズムを書くのは難しくないが,ここでは与えない.ここでは「プログラミングの美しさ」のアルゴリズムを示し,主に反復の回数を減らすためである.
xおよびyについて,y＝k＊y 1,x＝k＊x 1の場合,f(x,y)＝k＊f(x 1,y 1)となる.また、x=p*x 1の場合、pは素数であり、y%p!=0で、f(x,y)=f(p*x 1,y)=f(x 1,y).p=2をとる.
参照コード:

//    :       
//    : x,y    
//   :        
int gcd_solution1(int x, int y)
{
	if(y == 0)
		return x;
	else if(x < y)
		return gcd_solution1(y, x);
	else
	{
		if(x&1) //x   
		{
			if(y&1) //y   
				return gcd_solution1(y, x-y);
			else    //y   
				return gcd_solution1(x, y>>1);
		}
		else //x   
		{
			if(y&1) //y   
				return gcd_solution1(x>>1, y);
			else    //y   
				return gcd_solution1(x>>1, y>>1) << 1;
		}
	}
}

次の非再帰バージョン:

int gcd_solution2(int x, int y)
{
	int result = 1;
	while(y)
	{
		int t = x;
		if(x&1)
		{
			if(y&1)
			{
				x = y;
				y = t % y;
			}
			else
				y >>= 1;
		}
		else
		{
			if(y&1)
				x >>= 1;
			else
			{
				x >>= 1;
				y >>= 1;
				result <<= 1;
			}
		}
	}
	return result * x;
}