최대공약수 구하기 (Binary Euclidean algorithm)

유클리드 알고리즘의 변형이다.

스테인 알고리즘(Stein's Algorithm)이라고도 한다.

 

어째든 최대공약수를 찾는 알고리즘이다.

매우 큰 정수를 다룰 때,  나머지 연산자를 이용한 유클리드 호제법보다 빠르다.

 

기본 원리

• 모든 짝수는 2로 나눌 수 있다.

경우의 수	표현(식)	설명
A, B 모두 짝수 일 때	GCD(A, B) = 2 x GCD(A / 2, B / 2)	2를 공통인수로 가진다
A만 짝수일 때	GCD(A, B) = GCD(A / 2, B)	한쪽이 홀수라면, 2는 공통인수가 될 수 없다. 따라서 짝수인 수만 2로 나누어도 GCD는 변하지 않는다
B만 짝수일 때	GCD(A, B) = GCD(A, B / 2)

 

• 두 수가 모두 홀수인 경우

A(홀수) - B(홀수)는 반드시 짝수가 된다.

유클리드 호제법의 원리와 동일하게 'GCD(A, B) = GCD(A - B, B)' 성립한다

 

코드

//gcd(a, b) = gcd(a, b, 1)
int gcd(int a, int b, int res)
{
    if (a == b)
        return a * res;
    else if (a % 2 == 0 && b % 2 == 0)
        gcd(a / 2, b / 2, res * 2);
    else if (a % 2 == 0)
        gcd(a / 2, b, res);
    else if(b % 2 == 0)
        gcd(a, b / 2, res);
    else if(a > b)
        gcd(a - b, b, res);
    else
        gcd(a, b - a, res);
}