유클리드 호제법(Euclid's GCD Algorithm)

people.cs.ksu.edu/~schmidt/301s14/Exercises/euclid_alg.html

Euclid's GCD Algorithm

개요

유명한 알고리즘 중 하나로 유클리드 호제법(Euclid's GCD Alogirhtm)이 있다. 이는 2개의 자연수의 최대공약수(GCD: Greatest Common Divisor)를 구하는 알고리즘이다.

기하학의 아버지인 유클리드가 기원전 300년쯤에 개발한 알고리즘이다.

 

알고리즘 자체는 간단한데, 어떻게 이 알고리즘이 성립하는지 그러한 부분들부터 차근차근 한번 정리하면서 알아보자.

 

유클리드 호제법 증명

//(GCD(x, y)//)를 자연수 //(x//), //(y//)의 최대공약수라고 하자.

 

만약 //(x=y//)인 경우 아래는 자명하다.

 

//(GCD(x,y) = GCD(x,x) = x//)

 

공약수의 성질

그리고 유클리드는 //(x>y//)인 경우, 아래의 성질도 성립함을 알아내었다.

//(GCD(x,y) = GCD(x-y, y)//)

 

뭔가 감이 안 올 수 있는데, 간단하게 증명된다고 한다.

//(d//)를 //(x//)와 //(y//)의 공약수라고 하자.

 

그러면 아래의 조건을 만족하는 정수 //(q_1//)과 //(q_2//)가 존재한다.

//(x=q_1d//) , //(y=q_2d//)

 

//(x-y=q_1d-q_2d=(q_1-q_2)d//)

따라서 //(d//)는 //(x-y//)의 약수이기도 하다.

 

비슷한 이유로 이 역도 가능하다는 것을 보일 수 있다. //(x-y//)와 //(y//)의 약수는 //(x//)의 약수이기도 하다.

따라서 //(x//)와 //(y//)의 공약수 집합은, //(x-y//)와 //(y//)의 공약수 집합과 일치한다.

따라서 그 집합에서 가장 큰 원소인 최대 공약수 역시 일치하게 된다.

 

따라서 //(GCD(x,y) = GCD(x-y, y)//)가 성립한다.

 

Naive한 유클리드 호제법

위의 공약수의 성질을 이용해서 x와 y가 같아질 때 까지, 큰 값에서 작은 값을 빼는 방식으로 알고리즘을 수행해볼 수 있다.

이는 아래 두 가지 성질을 이용한 것이다.

//(GCD(x,x) = x//)

//(GCD(x,y) = GCD(x-y, y)//)

int gcd(const int K, const int M) {
    int k = K;   // 간단하게 불변식을 표현하기 위해
    int m = M;   // 인자를 상수로 고정하고
                // 계산을 위해 지역변수(사본)을 사용
    // loop invariant(불변식): GCD(K,M) = GCD(k,m)
    while (k != m) {
        if (k > m) {
            k = k-m; 
        } else {
            m = m-k;
        }
    }
    // 이 시점에서 k = m 이므로 , GCD(K,M) = GCD(k,m) = GCD(k,k) = k
    return k;
}

위와 같은 코드를 통해서 gcd를 쉽게 구해볼 수 있다. 지역변수로 사용한 k와 m은 처음 인자로 들어온 K와 M의 복사본으로 시작이 되며, gcd의 성질을 통해서 큰 값에서 작은 값을 빼더라도 같은 gcd를 갖게 된다.

 

좀 더 빠른 유클리드 호제법

위와 같은 방식으로, 큰 값에서 작은 값을 빼는 방식으로 유클리드 호제법이 구현이 가능한데, 이를 좀 더 빠르게 구현할 수 있다.

 

작은 값은 큰 값에서 뺄 수 있을 때 까지는 계속해서 빼기 연산을 수행할 것이므로, 이를 나머지 연산으로 대체하면 여러번 빼는 연산을 한번으로 대체할 수 있게 된다.

int gcd(int K, int M) {
    int k = K;   
    int m = M;   
    // loop invariant(불변식): GCD(K,M) = GCD(k,m)
    while (k !=0  &&  m != 0) {
        if (k > m)
        { k = k % m; }
        else
        { m = m % k; }
    }
    // 이 시점에서, GCD(K,M) = GCD(k,m) = max(k,m)
    return max(k,m);
}

빼기를 반복하는 경우의 알고리즘에선 k=m이 될 때 알고리즘이 종료되지만, 나머지 연산을 하는 경우 k=m인 경우 k와 m중 하나의 값이 0이 되어버린다. 따라서 리턴값은 그 중 큰 값이 된다.

 

이 코드를 좀 더 간편하게 정리하여, k > m 임을 보장하는 방식으로 코드를 짠다면 아래처럼 코드가 된다.

int gcd(int K, int M) {
    int k = max(K,M);
    int m = min(K,M);
    // loop invariant(불변식): k ≥ m ∧ GCD(K,M) = GCD(k,m)
    while (m != 0) {
        int r = k % m;
        k = m;
        m = r;
    }
    // 이 시점에서, GCD(K,M) = GCD(k,m) = GCD(k,0) = k
    return k;
}

간결한 코드

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}