유클리드 알고리즘

두 수가 모두 0이면 결과는 정의되지 않습니다. 임의로 큰 수가 모두 조건을 만족하기 때문입니다. 이 경우를 제외하면 다음 관찰이 성립합니다. 두 수 중 하나가 0이면 두 수의 $\gcd$는 나머지 한 수와 같습니다.

#구하는 알고리즘

유클리드 알고리즘은 다음의 간단한 공식에 기반하여 두 수 $a$와 $b$의 $\gcd$를 $O(\log \min(a, b))$에 구합니다:

여기서는 $a > b$라고 가정합니다.

이 공식이 올바름을 증명해 봅시다:

• $g = \gcd(a, b)$가 $a$와 $b$를 모두 나누면, 그 차 $(a-b)$도 $g$로 나누어떨어집니다.

• $b$의 어떤 더 큰 약수 $d$도 $(a-b)$를 나눌 수 없습니다. $d > g$이면 $d$는 $a$를 나눌 수 없으므로 $(a - b)$도 나누지 않습니다.

직접적인 재귀 구현은 다음과 같습니다.

int gcd(int a, int b) {
    if (a < b)
        swap(a, b);
    if (b == 0)
        return a;
    else
        return gcd(b, a - b);
}

이 알고리즘은 오래 걸릴 수 있습니다. 예를 들어 $(10^9, 1)$ 쌍에서는 10억 번을 반복합니다.

더 나아간 최적화의 아이디어는 $a$에서 $b$를 한 번에 하나씩 빼는 것이 아니라, 다음번에 $a$와 $b$의 자리가 이미 바뀌어 있도록, 즉 새로운 $b$가 새로운 $a$보다 작아지도록 충분히 많이 빼는 것입니다. 이를 달성하는 간단한 방법은 $a$에서 $b$를 가능한 한 최대 횟수만큼 한꺼번에 빼는 것, 즉 새로운 $b$ 대신 $a$를 $b$로 나눈 나머지를 취하는 것입니다:

구현:

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

조금 더 빠른 반복 형태:

int gcd(int a, int b) {
    while (b > 0) {
        a %= b;
        swap(a, b);
    }
    return a;
}

최신 C++에는 내장 라이브러리 함수 gcd가 있으며, 음수인 경우와 $(0, 0)$의 경우를 잊지 않는다면 이 함수를 사용하는 것을 권장합니다.

또한 유클리드 알고리즘 외에도 2~3배 더 빠른 이진 GCD가 있습니다.

#실행 시간

두 번의 반복마다 더 작은 수가 적어도 절반으로 줄어든다는 것을 보일 수 있으며, 따라서 알고리즘은 $O(\log \min (a, b))$에 동작합니다. 이 평가는 최악의 경우뿐만 아니라 평균적인 경우에도 해당합니다.

주목할 만한 점은 이 알고리즘의 최악의 입력이 인접한 피보나치 수라는 것입니다. 그래프에서 이들은 황금비 비율에 놓인 파란 점으로 나타납니다.

또한 $1$부터 $A$까지의 수 $n$개로 이루어진 묶음의 $\gcd$를 구하는 작업이 $O(n \log A)$가 아니라 $O(n + \log A)$ 시간에 동작한다는 사실을 알아 두면 때때로 유용합니다. 이는 귀납법으로 어렵지 않게 증명할 수 있습니다.