유클리드 호제법

유클리드 호제법 (Euclidean Algorithm) 은 두 자연수의 GCD (Greatest common divisor, 최대 공약수) 를 구하는 가장 일반적인 알고리즘이다. GCD를 구하는 이유야 수없이 많을 수 있고, 특히 PS를 할때는 오만 이상한 이유로 GCD를 구해야 하는데 (...) 

 

코드로는 재귀로 짜면 함수 자체는 한 줄이면 된다. 대충 $\texttt{int gcd(int a, int b)}$ 를 선언하고, $\texttt{return a%b?gcd(b,a%b):b;}$ 해주면 알아서 잘 구해주고, 어차피 이게 느려서 안되는 경우는 잘 없지만 inline을 붙이든 반복문으로 구현을 하든 할수도 있다.

 

GCC 컴파일러를 사용한다면, 직접 구현할 필요도 없다. $\texttt{__gcd(a, b)}$ 하면 된다.

 

이게 왜 성립할까? 즉, 어떻게 이 방법으로 두 수의 최대공약수를 얻을 수 있을까?

돌려 보면 엄청 빠른거 같은데, 얼마나 빠른가? 

 

유클리드 호제법의 원리 증명

먼저 다음 명제를 보자. 

 

Theorem.

두 자연수 $a, b$ 가 어떤 정수 $q$와 $r(0 \leq r < b)$에 대해 $a = bq + r$ 일 때, $\gcd(a, b) = \gcd(b, r)$이 성립한다. 즉, $a$ 를 $b$ 로 나눈 나머지가 $r$ 일 때, $\gcd(a, b) = \gcd(b, r)$.

 

 

이 명제로 충분한가?

저런 명제를 던졌으면 증명을 해야겠지만, 우선은 이 주장을 받아들이면 유클리드 호제법이 잘 작동한다는 것을 납득해 보자. 우리는 $\gcd(a, b)$ 를 구하는 데 있어, $a, b$ 가 너무 커서 구하기 어려우므로, 이것을 $\gcd(b, r)$로 줄이려고 한다. (단, 이때 $r$은 앞서 명제에 쓰인 대로 $a = bq + r$.) 여전히 충분히 작지 않다면, 이 과정을 반복해서 계속 줄여 나가자.

 

그러다가, 어느 순간 중간에 두 수의 gcd가 자명해지는 순간이 있다. $\gcd(p, q)$ 는 $p$ 가 $q$ 의 배수일 때 자명하게 $q$ 니까. 

따라서, 우리는 "자명한 최대공약수가 나타날 때까지 숫자를 줄이겠다" 라는 마인드를 갖고 코드를 돌리면 된다. 이제 앞 명제를 증명하는 것으로 충분하다는 사실을 알았으니 실제로 증명해 보자.

 

증명

Let $\gcd(a,b) = g$. 이제, $a = xg, b = yg$ 를 만족하는 자연수 $x, y$ 가 $\gcd$의 정의에 의해 반드시 존재한다. 

따라서, $a - bq = (x-yq)g = r$ 이므로, $r$ 은 $g$ 로 나누어 떨어진다. 반대로, $\gcd(b, r) = h$ 라고 하자. 이제, $\gcd$ 는 가장 큰 공약수이므로, $h$가 $g$ 로 나누어 떨어져야 하며 ($g$가 $r$과 $b$ 모두의 약수이므로!) , $g \leq h$ 임은 당연하다. 

 

또한, $b = y'h, r = z'h$ 를 만족하는 자연수 $y', z'$가 존재해야 한다. 따라서, $a = bq + r = (by'+z') h$ 이므로, 반대로 $a$는 $h$로 나누어 떨어진다. 그런데, 앞서 $\gcd(a, b) = g$ 라고 정의하였고, $h$ 는 $a$ 와 $b$ 의 공약수이므로, $g$는 $h$로 나누어 떨어지며 $g \geq h$ 이다.

 

$g \leq h$ 이고 $h \leq g$ 이므로, $g = h$ 임을 알 수 있다.

 

시간 복잡도 분석

$a < b$ 였다고 하더라도, 한 번의 Step으로 $a' > b'$ 이 되므로 우리는 $a > b$ 를 가정하자.

 

어떤 $a_n, b_n$에 대하여 $a_n > b_n > 0$ 이고, 유클리드 호제법의 함수 $\texttt{gcd}$ 가 $n$번 호출된다고 가정하자. 이때, 우리는 $b_n$의 Lower bound를 찾고자 한다. 구체적으로는, 다음을 증명하자.

$$b_n \geq fib_{n-1}$$

($fib$는 피보나치 수열이다)

By induction, 한 번 호출로 끝나기 위해서는 $b_n = 0$ 이어야 한다. 피보나치 수열의 0번째 항을 0으로 두는 것이 마음에 들지 않는다면, 두 번 호출로 끝나기 위한 $b$의 최솟값이 1임을 생각해도 좋다.

 

$a_k, b_k$ 가 한 번 호출을 받고 $a_{k-1}, b_{k-1}$ 로 넘어갔다고 하자. 이때, $a_{k-1} = b_k$ 이다.

또한, 이 값은 다시 $a_{k-2}, b_{k-2}$ 로 넘어가고 $a_{k-2} = b_{k-1}$ 이다.

$b_{k-2}$ 는 $a_{k-1}$ 을 $b_{k-1}$ 로 나눈 나머지이므로, $a_{k-1} = qb_{k-1} + b_{k-2}$ 이 성립하는 $q \geq 1$ 이 존재하고, 따라서 $a_{k-1} = b_{k} \geq b_{k-1} + b_{k-2}$ 이다.

 

이는 즉, 대략 $fib_i$ 까지의 수를 $i$번의 함수 호출로 커버할 수 있다는 뜻이 된다. 피보나치 수열이 대략 $1.6^n$ (정확히는 $\varphi^n$) 이므로 유클리드 호제법의 시간 복잡도는 $\mathcal{O(\log (b))}$ 이다.

 

실제로 가장 호출 횟수가 많은 건 $a, b$가 피보나치 수 일 때이다.

 

참고로, (언젠가 다뤄보고 싶긴 하지만, 수식이 너무 많고 복잡해서 다 이해를 못 했다;;) 1부터 $n$ 범위의 임의의 수 $a, b$를 골랐을 때, GCD 함수의 실행 횟수의 기댓값은 

$$\frac{12}{\pi^2} \log 2 \log n + 0.06$$ 이라고 한다. (위키피디아 링크)