이진 최대공약수 알고리즘
이진 최대공약수 알고리즘은 두 양의 정수의 최대공약수를 계산하는 알고리즘이다. 스테인의 알고리즘이라고도 알려져 있다.
현대 컴퓨터의 이진 표기법 때문에 일반적으로 시프트 연산이 나눗셈, 곱셈보다 빠른데, 이진 최대공약수 알고리즘은 나눗셈과 곱셈을 시프트 연산으로 대체함으로써, 유클리드 호제법보다 좋은 성능을 보여준다. 그래서 이 알고리즘은 나눗셈 연산을 지원하지 않는 프로세서가 장착된 플랫폼에서 특히 더 중요하다. 1961년에 조셉 스테인이 이 알고리즘을 처음 발표했지만, 1세기경 중국에 이미 알려져 있었다.[1]
기본 알고리즘
이 알고리즘은 다음 규칙들을 적용하면서 최대공약수를 찾는 문제를 간단화한다. 아래의 설명에서 gcd(a, b)는 a와 b의 최대공약수를 의미한다.
- gcd(0, v)=v : 0은 모든 수로 나누어 떨어지고, v는 v로 나누어지는 가장 큰 수이기 때문이다.
- 만약 u와 v가 둘 다 짝수이면, gcd(u, v)=2·gcd(u/2, v/2) : 2가 공약수이기 때문이다.
- 만약 u는 짝수, v는 홀수이면, gcd(u, v)=gcd(u/2, v) : 2가 공약수가 아니기 때문이다. 이와 마찬가지로 u는 홀수, v는 짝수라면 gcd(u, v)=gcd(u, v/2) 이다.
- 만약 u와 v가 둘 다 홀수이고 u ≥ v이면, gcd(u, v) = gcd((u−v)/2, v)이다. 마찬가지로 둘 다 홀수이고, u < v이면, gcd(u, v) = gcd((v-u)/2, u)이다. : 이는 유클리드 호제법과 제3단계의 조합이다.
- u = v가 될 때까지나 u = 0 이 될 때까지 2단계에서 4단계를 반복한다. 그 결과는 2kv 꼴로 나온다.
이 알고리즘은 최악의 경우 O(log22 uv)의 시간이 걸린다.
확장된 알고리즘
확장된 유클리드 호제법과 유사한 확장된 이진 최대공약수 알고리즘은 《컴퓨터 프로그래밍의 예술》에서 다른 버전들과 함께 제시되어 있다.[2]
C 언어로 구현한 소스 코드
아래에 있는 이 알고리즘의 C 언어 구현은 두 양의 정수 u와 v를 받는다. 처음에는 2단계를 사용하여 공약수 2를 걸러내고, 3,4단계를 이용하여 남은 숫자의 최대공약수를 계산한다. 그리고 마지막으로 이들을 합쳐 최종 결과를 구한다.
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;
}
효율성
브리지트 발레(Brigitte Vallée)는 비트 연산의 횟수 때문에 이 알고리즘이 평균적으로 유클리드 호제법보다 60% 정도 효율적이라고 증명했다.[3][4][5] 그러나 비록 이 알고리즘이 유클리드 호제법보다 빠르나, 점근표기법상으로는 같다. 이는 더욱 복잡한 현대 마이크로프로세서의 나눗셈 연산 때문이라 할 수 있다.
일반적으로, 위의 C코드와 비슷한 이진 최대공약수 알고리즘 구현은 실제로는 이론보다 이득이 적다.[출처 필요]
함께 보기
참고 자료
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Problem 31-1, pg.902.
주석
- ↑ 도널드 크누스, The Art of Computer Programming, 제2권: Seminumerical Algorithms (3rd Edition). Addison-Wesley.
- ↑ 도널드 크누스. 《앞의 책》. section 4.5.2의 exercise 39의 정답. 646쪽.
- ↑ http://users.info.unicaen.fr/~brigitte/Publications/icalp8-2000.ps
- ↑ http://web.comlab.ox.ac.uk/oucl/work/richard.brent/ftp/rpb183pr.ps.gz
- ↑ Alexander Stepanov의 Notes on Programming