알고리듬#1+@ 이진 최대공약수(스테인의 알고리듬)

이번에 배울 내용은 유클리드 알고리듬과 유사한 스테인의 알고리듬이다. 

전에 컴퓨터의 연산은 뺄셈이던지 곱셈이던지 혹은 나눗셈이던지 항상 이진 덧셈으로 이루어진다고 했다. 

그런데 곱셈 연산과 나눗셈 연산의 경우 덧셈이 아닌 방식으로 동작시키는 것이 가능하다. 바로 비트시프트를 이용하는 것이다. 

여기 1byte크기의 메모리에 데이터가 저장되어있다고 하자.

이 정수의 4배를 구하려면 같은 수를 덧셈 연산을 4번 해야 한다. 

반면 비트시프트 연산의 경우 단순히 저장된 데이터중 일부 비트정보를 뒤집으면 되기에 이론적으로 횟수로는 2번의 횟수가 되어 덧셈 연산보다 더욱 빠를 수 있다.

나눗셈의 경우도 곱셈과 연산 방향만 바뀔 뿐 연산 수행 횟수는 동일하다. 

이러한 비트시프트라는 것과 짝수에 반드시 2라는 약수가 있다는 것을 활용한 것이 이진 최대공약수 알고리듬이다. 

이진 최대 공약수 판정법(Binary Greatest Common Divisor/Stain's Algorithm)

유클리드 호제법과 비트시프트 연산을 활용하여 최대공약수를 판정하는 알고리듬

A와 B 모두 짝수일 경우:

-> GCD(A/2**n, B/2**n)*2**n

두 수를 모두 2로 홀수가 나올 때 까지 나눈 후 유클리드 호제법을 적용하고 그 결과에 2로 나눈 횟수만큼 2를 곱한다.

A 또는 B중 하나만 짝수일 경우:

-> GCD(B, A/2**n)

두 수 모두 홀수인 경우:

-> GCD(A, B)

C코드

// 이진 최대공약수 판정법
// 시간복잡도 O(logN)
int binary_GCD(int A, int B) {
    int C;
    int T = 0; // 두 수 모두 짝수인 경우 카운트
    if((A & 1) == 0 || (B & 1) == 0) //비트연산 짝수체크
    {
    	// 조건 A에 걸려서 진입했을 경우 B체크 필요
    	// 조건 B에 걸려서 진입했을 경우 A는 홀수
        if ((B & 1) == 0)
    	{
            if(A > B)	// A가 B보다 클 경우 아래의 반복문 연산중 T의 값이 이상해지는 것을 방지
            {		// ex) A = 16, B = 8 : T = 3이 정답인데 T = 4가 발생
        	int temp = A;
                A = B;
                B = temp;
            }
            // 두 수 모두 짝수인 경우 반드시 A <= B 만큼 반복횟수 시행
            while((A & 1) == 0)
            {
            	T++;
        	A >>= 1;
            }
        }
        while((B & 1) == 0)
        {
            B >>= 1;
        }
    }
    while(B != 0) 
    {
        C = A % B;
        A = B;
        B = C;
    }
    return A << T;
}

우쒸 생각보다 고려할게 많은 알고리즘이었다. 그리고 논리적인 수행횟수는 줄어들긴 하지만 실제로 유클리드 호제법보다 획기적으로 연산 횟수를 줄여주진 않는다고 한다. 아마 조건체크와 반복 연산이 추가되서 줄긴 줄지만 덜 준 느낌...?이든다.

다음 제공되는 코드는 위키백과에서 제공하는 C 코드다. 개인적으로 do while을 싫어하기도 하고, 최대한 반복문 횟수를 줄이고 싶어서 직접 코드를 다른 방식으로 구현해 보았다. 혹시 제가 발견하지 못한 고려사항이 있다면 알려주시면 감사드립니다. 

 unsigned int gcd(unsigned int u, unsigned int v)
 {
     int shift;

     /* GCD(0,x) := x */
     if (u == 0 || v == 0)
       return u | v;

     /* u와 v가 2로 나누어지지 않을 때까지
        시프트해 주고, 횟수를 센다. */
     for (shift = 0; ((u | v) & 1) == 0; ++shift) {
         u >>= 1;
         v >>= 1;
     }

     while ((u & 1) == 0)
       u >>= 1;

     /* 여기에서 u는 홀수이다. */
     do {
         while ((v & 1) == 0)  /* v가 짝수라면 홀수가 될 때까지 시프트해 준다. */
           v >>= 1;

         /* 이제 u와 v는 모두 홀수이다. u와 v의 차는 짝수이다.
            u = (u와 v 중 작은수), v = (u와 v의 차)/2 로 놓는다.*/
         if (u < v) {
             v -= u;
         } else {
             unsigned int diff = u - v;
             u = v;
             v = diff;
         }
         v >>= 1;
     } while (v != 0);

     return u << shift;
 }

출저 : 위키백과 이진 최대공약수 알고리즘 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

해당 코드들은 제 깃허브에 있습니다. 유사코드는 제공하지 않습니다.

Workspace/알고리듬 at main · cyphen156/Workspace · GitHub