이진 최대공약수 알고리즘이진 최대공약수 알고리즘은 두 양의 정수의 최대공약수를 계산하는 알고리즘이다. 스테인의 알고리즘이라고도 알려져 있다. 현대 컴퓨터의 이진 표기법 때문에 일반적으로 시프트 연산이 나눗셈, 곱셈보다 빠른데, 이진 최대공약수 알고리즘은 나눗셈과 곱셈을 시프트 연산으로 대체함으로써, 유클리드 호제법보다 좋은 성능을 보여준다. 그래서 이 알고리즘은 나눗셈 연산을 지원하지 않는 프로세서가 장착된 플랫폼에서 특히 더 중요하다. 1961년에 조셉 스테인이 이 알고리즘을 처음 발표했지만, 1세기경 중국에 이미 알려져 있었다.[1] 기본 알고리즘이 알고리즘은 다음 규칙들을 적용하면서 최대공약수를 찾는 문제를 간단화한다. 아래의 설명에서 gcd(a, b)는 a와 b의 최대공약수를 의미한다.
이 알고리즘은 최악의 경우 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코드와 비슷한 이진 최대공약수 알고리즘 구현은 실제로는 이론보다 이득이 적다.[출처 필요] 같이 보기참고 자료
각주
외부 링크 |
Portal di Ensiklopedia Dunia
