015. 최대공약수(gcd)

2.9 최대공약수(gcd)

u, v가 둘 다 0이아닌 정수 일 때, u와 v를 모두 나누는 가장 큰 정수가 최대공약수(gcd, greatest commond divisor)이다.

 

최대공약수는 다음과 같은 특성을 가진다.

gcd(0,0) = 0

gcd(u,0) = |u|

gcd(u,v) = gcd(v,u)

gcd(-u,v) = gcd(u,v)

 

gcd는 유클리드 알고리즘을 이용해서 비교적 쉽게 구할 수 있다.

 

알고리즘

S1. [v=0?]

      만일 v=0이면 답은 u가 되고 goto END

     

S2. [u mod v]

      r ← u mod v, u ← v, v ← r

      goto S1

 

알고리즘이 동작되는 과정을 예로 살펴보자.

다음은 2006와 1360의 gcd를 구하는 과정이다.

 

 

코딩

위 알고리즘대로 gcd함수를 작성해 보자

/**************************************************************************
두 정수의 최대공약수(gcd)를 구한다.
Input: @A, @B = 입력값	   
Output:@C = 입력값 A, B에 대한 최대공약수 C = gcd(A,B)
Returns: 
		OK : no error		
Comment:
		
***************************************************************************/
int gcd(BIGINT A, BIGINT B, BIGINT C){
	BIGINT u,v,r;
	//음수인 경우 양수로 바꾸는 과정이 필요하기에 복사본을 만들어 사용
	copy_big(u,A);
	copy_big(v,B);
	//양수로 변환
	abs(u);
	abs(v);

함수명은 gcd로 하고, 입력값 A,B를 받아서 gcd결과를 C로 리턴하도록 한다.

 

gcd특성이 gcd(-a,b) = gcd(a,b) 이기에, 두 입력값을 양수로 변환해서, 양수에 대해서만 계산되도록 한다.

 

        //v가 0이 될 때까지 루프
	while(v[0] != 0){
		mod(u,v,r);
		copy_big(u,v);
		copy_big(v,r);
	}
	//v가 0이므로 gcd=u
	copy_big(C,u);
	return OK;
}	

알고리즘에서 살펴본 바와 같이, v가 0이 될때까지 루프를 돌면서 r = u mod v를 계산하고, u=v, v=r로 대치.

 

최종 루프를 벗어나게 되면 v가 0인 상태이므로 gcd는 u가 되고, 이 값을 C로 카피하고 함수 종료.

 

테스트

아래 테스트 함수 참조

int test_gcd(){
	BIGINT a,b,c;
	BIGINT expected_c;
	int result=-1;
	int ret=-1;
	//01. gcd(0,0) = 0
	a[0] = 0;
	b[0] = 0;
	ret = gcd(a,b,c);
	if(ret != OK) return -1;
	expected_c[0] = 0;
	result = compare_big(c,expected_c);
	if( result != 0)
		return -1;
	//02. gcd(a,0) = a (a>0)
	hexstr2bigint("11223344556677",a);
	b[0] = 0;
	ret = gcd(a,b,c);
	if(ret != OK) return -1;
	copy_big(expected_c,a);
	result = compare_big(c,expected_c);
	if( result != 0)
		return -1;
	//03. gcd(a,0) = |a| (a<0)
	hexstr2bigint("-11223344556677",a);
	b[0] = 0;
	ret = gcd(a,b,c);
	if(ret != OK) return -1;
	hexstr2bigint("11223344556677",expected_c);
	result = compare_big(c,expected_c);
	if( result != 0)
		return -1;
	//04. gcd(a,b) = c (a>b)
	hexstr2bigint("1122334455667788",a);
	hexstr2bigint("112233445566",b);
	ret = gcd(a,b,c);
	if(ret != OK) return -1;
	hexstr2bigint("0132",expected_c);
	result = compare_big(c,expected_c);
	if( result != 0)
		return -1;
	//05. gcd(a,a) = c (a<b)
	hexstr2bigint("112233445566",a);
	hexstr2bigint("1122334455667788",b);
	ret = gcd(a,b,c);
	if(ret != OK) return -1;
	hexstr2bigint("0132",expected_c);
	result = compare_big(c,expected_c);
	if( result != 0)
		return -1;
	return OK;
}

 

프로젝트 파일

 

009.gcd.zip

 

 

009.gcd.zip

0.64MB