유클리드 알고리즘
Euclidean algorithm. 두 자연수의 최대공약수를 구하는 알고리즘. 기원전 300년 경에 유클리드의 《원론》1)에서 처음 기술되었으며 아마 그 이전에도 알려져 있었을 것으로 추측된다. 따라서 가장 오랫동안 살아 남은 알고리즘이라 할 수 있는데, Donald Knuth는 TAOCP에서 이 알고리즘을 "모든 알고리즘의 할아버지"라고 부르기까지 한다.
《원론》에서의 설명을 간략히 요약하면, 두 숫자 a와 b의 최대공약수를 구하려면 큰 쪽에서 작은 쪽을 빼는 것을 반복하다가 한 쪽이 다른 쪽의 배수가 되면 작은 쪽이 최대공약수가 된다는 것이다. (이를테면 25와 10의 최대공약수는 15와 10, 5와 10의 최대공약수와 같고, 10이 5의 배수니까 최대공약수는 5가 된다.) 실제 설명은 현대적인 표현이 아닌 기하학적인 방법으로 되어 있는데다가 1에 대한 경우를 따로 처리하기 때문에 보기는 그다지 편하지 않다.
분석
유클리드 알고리즘은 최대공약수의 세 가지 성질에 토대를 둔다.
- k > 0이고 a > 0이면 \gcd(ka,a) = a이다.
- a > b > 0이면 \gcd(a,b) = \gcd(a-b,b).
- \gcd(a,b) = \gcd(b,a).
첫번째 성질은 현대적인 \gcd의 정의를 쓰면 \gcd(a,0) = \gcd(0,a) = a로 바꿀 수 있으며, 두번째는 여러 번의 뺄셈 대신 나머지연산을 써서 \gcd(a,b) = \gcd(a \mod b,b)로 바꿀 수 있다. 두번째와 세번째를 합치면 a > b일 때 \gcd(a,b) = \gcd(b,a \mod b)라는 결과를 얻을 수도 있다.
유클리드 알고리즘이 모든 자연수에 대해서 끝난다는 점은 매 시점에서 두 자연수 중 하나는 항상 줄어 든다는 점, 또는 두 자연수의 합이 항상 단조감소한다는 점에서 쉽게 증명할 수 있다. (이 경우 두번째와 세번째 성질을 합쳐서 항상 "감소"하도록 만드는 게 증명에 유리하다.) 유클리드 알고리즘이 옳다는 점은 위의 성질로부터 거의 곧바로 유도된다.
유클리드 알고리즘은 최악의 경우 나눗셈이 O(\log \min\{a,b\})회 필요하다. 이 최악의 경우란 두 인접한 피보나치수를 입력으로 주었을 경우이며, 따라서 로그의 밑수는 황금비가 된다. 좀 더 일반적으로 생각해서, 자연수가 임의정밀도정수일 때 필요한 연산의 수는 O\left((\log \min\{a,b\})^2\right)회이다. 후자는 눈꼽만큼 개선이 가능하나 아주 큰 숫자가 아니면 별 쓸모가 없다.
