Euclidean Algorithm

컴퓨터 사이언스나 컴퓨터 공학을 전공하는 학생이라면 누구나 Euclidean Algorithm을 한 번 쯤을 들어봤을 것이다.
Euclidean Algorithm은 가장 오래된 알고리즘 중 하나로 2300년전 그리스의 수학자 Euclid에 의해 고안되었다.

Euclidean Algorithm은 음이 아닌 두 정수 a, b의 최대공약수 GCD(a, b)를 구하는 알고리즘으로 C++로는 아래와 같이 간단하게 구현할 수 있다.

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

코드가 워낙 간단하기 때문에 여태껏 그냥 외워서 쓰고 있었는데 사실 그 본질에 대해서는 제대로 이해하고 있지는 않았다. 오늘 우연히 루프 불변식에 대한 복습을 하다가 그 증명을 하게되어 이 알고리즘을 어느 정도는 느낄 수 있게 되어 여기 정리하고자 한다.


우선 알고리즘을 풀어서 써 보자

GCD(nonnegative integer a, nonnegative integer b) // a>=b, and not both a, b are zero

integer i, j;
i = a, j = b;
while j != 0 do

i = qj + r (where 0 <= r < j)
i = j;
j = r;

end while;
return i; // i is gcd of a and b

end function GCD

우선 아래 관계를 증명하자. (이 증명을 분명 고등학교때 배웠을 텐데 기억속에 지워진지 오래구나!!)

a = qb + r → (gcd(a, b) = gcd(b, r))

a = q1c, b = q2c 라 하면,
r = q1c - qq2c = c(q1 - qq2)
따라서 a와 b의 어떤 공약수 c는 r의 약수이기도 하다.

b = q3d, r = q4d 라 하면,
a = qb + r = qq3d + q4d = d(qq3 + q4)
따라서 b와 r의 어떤 공약수 d는 a의 약수이기도 하다

∴ (a, b)와 (b, r)은 같은 약수를 가지므로 같은 GCD를 가진다.

이제 알고리즘이 제대로 동작한다는 것을 증명하면 된다.

루프 불변식 Q를 Q: gcd(i, j) = gcd(a, b)로 설정하고 수학적 귀납법을 이용하여 루프 불변식이 모든 단계에서 지켜진다는 것을 증명하여 알고리즘이 정확하게 동작한다는 것을 증명할 수 있다. 

Q(k): gcd(i(k), j(k)) = gcd(a, b) → Q(k+1): gcd(i(k+1), j(k+1) = gcd(a, b) 를 증명

알고리즘에서

i(k+1) = j(k)
j(k+1) = r(k)

이다. 따라서

gcd(i(k+1), j(k+1))
= gcd(j(k), r(k))
= gcd(i(k), j(k))    ( a = qb + r → (gcd(a, b) = gcd(b, r))의 증명에 의해 )
= gcd(a, b)          ( 수학적 귀납법의 가정에 의해 )

수학적 귀납법으로 Q(k)가 증명되었다. (base 생략;)

Q가 루프 불변식이므로 루프가 끝날때 gcd(i, j) = gcd(a, b)이며 j = 0 이다.
따라서 gcd(i, 0) = gcd(a,b) 이다.
gcd(i, 0) = i 이므로 i = gcd(a, b) 이다.

따라서 알고리즘은 gcd(a, b)를 구한다.

수학적 귀납법으로 알고리즘에 정확하게 동작한다는 것을 증명하였지만 아직 마음에 와 닿지는 않는 느낌이다. 하지만 위 수식을 그림으로 그려보니 머릿속으로 좀 더 명확한 이미지로 볼 수 있었다.

그림을 어떻게 그려야 할지 감이 안와서 대충 그리긴 했는데.. 어느정도 머릿속의 이미지를 나타낸것 같긴 하다. 나중에 감이 안올때 다시 봤을때 바로 생각이 날 수 있는 정도는 될 것 같다.

이 알고리즘은 유클리드가 저술한 <Stoicheia> 에 처음 실렸는데 이 책의