====== 유클리드 알고리즘 ======

Euclidean algorithm. 두 자연수의 [[최대공약수]]를 구하는 [[알고리즘]]. [[기원전]] 300년 경에 [[유클리드]]의 《[[원론]]》((정확히는, 7권 명제 2와 10권 명제 3. 두 명제는 수학적으로는 사실상 같으나 사용하는 용어가 다르다.))에서 처음 기술되었으며 아마 그 이전에도 알려져 있었을 것으로 추측된다. 따라서 가장 오랫동안 살아 남은 알고리즘이라 할 수 있는데, [[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)$$회이다. 후자는 눈꼽만큼 개선이 가능하나 아주 큰 숫자가 아니면 별 쓸모가 없다.

===== 같이 보기 =====

  * [[이진최대공약수알고리즘]]
  * [[확장유클리드알고리즘]]

{{tag>알고리즘}}