이전글 : 유클리드 호제법(http://www.tibyte.kr/224)
이진 최대공약수 알고리즘(binary GCD algorithm은 스테인 알고리즘(Stein's algorithm)이라고도 하며 비트연산을 이용하여 컴퓨터에서 최대공약수를 (나머지연산을 사용하는 유클리드 알고리즘보다) 빠르게 구할 수 있는 알고리즘이다.
이 알고리즘으로 36과 24의 최대공약수를 구하는 예시를 보면 다음과 같다.
36 → 18 →9 →9 →6 →3 →3
24 → 12 →6 →3 →3 →3 →0
여기서 이런 규칙을 볼 수 있다.
- 두 수가 짝수일 때는 2로 나눈다.
- 한 수만 짝수일 때는 그 수를 2로 나눈다.
- 두 수가 홀수일 때는 큰 수에서 작은 수를 뺀다.
- 0이 되는 수가 있으면 종료한다.
여기서 최대공약수를 얻는 방법은
두 수가 짝수여서 2로 나누는 계산을 할 때마다, 변수 a를 1씩 증가시킨다.
그리고 마지막에 남은 0이 아닌 수를 b라고 하면
를 계산하는 것이다.
두 수가 모두 2로 a번 나눠진다는 것은
두 수의 공약수에 2가 a번 포함되어있기 때문이라고 생각하면 이해하기가 쉽다.
36과 24의 경우에서, 마지막에 3이 남았다는 것은
바로 전 단계에 두 수에 모두 3이 포함되어있는 것이기 때문에 이 역시 곱해준다(위 식에서는 b)
규칙에서 두 수가 홀수일 때 값을 빼는 것은 유클리드 알고리즘과 관련있는 부분이다.
C언어 코드
int calcGcd(int n1, int n2)
{
int exp = 0;
int n;
while (((n1|n2)&1) == 0) {
++exp;
n1 >>= 1;
n2 >>= 1;
}
while (n1!=0 && n2!=0) {
while ((n1&1) == 0)
n1 >>= 1;
while ((n2&1) == 0)
n2 >>= 1;
if (n1 > n2)
n1 = n1-n2;
else
n2 = n2-n1;
}
if (n1!=0)
n = n1;
else
n = n2;
return n<<exp;
}
관련글 : 유클리드 호제법(http://www.tibyte.kr/224)