14. [수치] 최대공약수 구하기 (이진 gcd 알고리즘)

컴퓨터를 이용해서 최대공약수를 구할 때, 유클리드 알고리즘이 최적이라고 생각하기 쉬우나, 사실 그렇지 않다.

1961년 스페인 Josef Stein에 의해 고안된 이진 GCD알고리즘이 더 최적이다. 이 알고리즘에서는 나눗셈을 사용하지 않고, 오직 뺄셈, 홀짝판정, 짝수의 반감에 의해서만 gcd를 구할 수 있어, 컴퓨터에서의 연산과정이 빠르게 진행된다.

컴퓨터에서 이진 gcd알고리즘이 적합한 이유

• 2의 거듭제곱에 대한 곱 혹은 나눗셈은, Shift연산에 의해 쉽게 구현되고, 컴퓨터에서 Shift연산은 비용이 아주 적게 드는 연산이다.

 a x 2 ==>  a >> 1;

 a x 8 ==>  a >> 3

 a / 16 ==> a << 4

• 짝수인지 홀수인지의 판별은, 가장 하위비트가 0인지 1인지를 보면된다.

컴퓨터에서 수는 어차피 이진수로 보관되어 있고, 가장 하위비트가 0인지 1인지는 비트 And연산 한 번이면 쉽게 파악 가능

if (a & 1 == 1) ==> a는 홀수

<문제>

최대공약수를 구하는 알고리즘 중, 나눗셈 혹은 모듈러스 연산을 사용하지 않는 알고리즘이 있다.

이 알고리즘은 GCD 성질 중 다음의 5가지 특성을 이용하여 구현된다고 한다.

• a=짝수 b=짝수 이면 gcd(a,b) = 2 x gcd(a/2, b/2)
• a=짝수 b=홀수 이면, gcd(a,b) = gcd(a/2,b)
• a=홀수 b=홀수 이면, a-b는 짝수이고 abs(a-b) < max(a,b)
• gcd(a,b) = gcd(a-b,b)
• gcd(a,0) = a

위 5가지 성질을 이용해서, 두 수의 gcd를 구하시오.

 

ex) gcd(40902, 24140) = 34

 

<풀이>

두 수의 짝, 홀을 판별하고, 각 경우에 따라 수를 감소시키면서(2로 나누던지, 빼던지), 어느 한 쪽 수가 0이될때까지 진행시키면 될 듯하다.

(두 수가 짝수이면 왜 gcd(a,b) = 2 x gcd(a/2, b/2) 가 되는지 등 좀 생각해보면 원리를 알 수 있을 듯 하지만... 그냥 맞다고 생각하자.^^ )

 

A1. 두 수가 짝수이면 계속해서 2로 나누고, 나눈 횟수를 기억하자.

A2. 이제 두 수중 하나는 홀수인데(왜냐면 위에서 둘 다 짝수가 아닐때까지 계속 2로 나누니깐), (홀,짝) (짝,홀)의 경우는, 짝수를 2로 나눈다.

A3. 이제 둘다 홀 수가 되었는데, gcd(a,b) = gcd(a-b,b)이므로, 한 쪽을 두 수의 차로 대치한다. (t=a-b)

A4. 두 홀수의 차는 짝수이고, 이 경우는 gcd(짝수, 홀수)의 경우가 되므로, 짝수를 2로 나눈다. 
     이 과정을, 두 수의 차가 0이 될 때까지 계속한다.

 

위와 같은 알고리즘을, 프로그래밍 코드에 더 가깝게 상세 Flow를 짜보면 다음과 같다.

F1. 두 수(a,b)가 짝수인 한은 계속해서 두 수를 2로 나눠, 수를 작게 만들면서, 그 횟수(k)를 센다.

   이 과정을 거치면, 이제 두 수중 하나는 홀수이다. 경우의 수를 보면 3가지

    (홀,짝) (짝,홀) (홀,홀)

F2. (홀,짝) (짝,홀)의 경우는, 주어진 gcd성질 2번째를 이용해서, 짝수(t)를 홀수가 될 때가지 계속해서 2로 나누자.

        a=홀 ->t=-b  ;a,b 중 어느쪽이 짝수였는지 구분하기 위해, b가 짝수인 경우는 -t로 한다. 

        a=짝 ->t=a

        t = t/2, while t=짝수  ;(홀,홀)의 경우 t=-b가 된 상태고, 이는 홀수이기에, 이 루틴이 실행되지 않고 바로 3으로 이동됨

F3. 위 2번을 거치면, 두 수는 (홀,홀)임.  성질 3을 이용해서 a의 값을 작게 만든다: gcd(a,b)=gcd(t=a-b,b)

F4. 만약 t(=a-b)가 짝수가 되면, 홀수가 될 때까지 2로 나눠주고, t=0이면 다음단계로, 아니면 F3 다시 수행

F5. t의 값이 0이 될 때까지 F4를 반복 

 

이것을 프로그램으로 짜보면 아래와 같다.

<소스 코드>

package p1;

 

public class CalculateGCD_binary {

         public CalculateGCD_binary(){

                  test();

         }

        

         private void test(){

                  int a,b,g;

                 

                  a=40902; b=24140;

                  g = calGCD_binary(a,b);

                 

                  System.out.println("GCD("+a+","+b+")="+g);

         }

        

         private int calGCD_binary(int a, int b){

                  int t,k;

                 

                  //should be a > b

                  if(a<b){

                           t = a;

                           a = b;

                           b = t;

                  }

                 

                  //1. 둘 다 짝수의 경우 : gcd(a,b) = 2 gcd(a/2,b/2)

                  k=0;

                  while( ((a & 1) == 0) && ((b & 1) == 0)){

                           a >>>= 1; b >>>= 1;

                           k++;

                  }

                 

                  //2. 이제 둘 중 하나는 홀수

                  if((a & 1) == 1){ //a=홀수

                           t = -b;

                  }else{ //a=짝수, b=홀수

                           t = a;

                  }

                 

                  //3. 둘 다 홀수로 만듬

                  while( (t & 1) == 0)

                           t >>= 1; //signed shift에 유의

                 

                  //4. a, b 복원

                  if(t<0) b = -t;

                  else    a = t;

                 

                  //5. gcd(a,b) = gcd(a-b,b)이용. 그리고, 둘 다 홀수이므로 t=a-b 는 짝수가 됨

                  while(true){

                           t = a - b; //t:짝수, 만약 a<b이면 t<0

                           if(t == 0) break;

                          

                           while( (t & 1) == 0) t >>= 1; //홀수될 때까지

                           if(t<0) b = -t;

                           else    a = t;                     

                  }

                                  

                  return (a << k);  //a x 2^k        

                 

         }

 

         public static void main(String[] args) {

                  new CalculateGCD_binary();

 

         }

 

}

 

 

-끝-