최대공약수 구하기 (Great Common Division, GCD)

최대공약수 (the Greatest Common Divisor, GCD)를 구하는 프로그램을 만들 것이다.

최대공약수에 대한 개념은 중학생 때 공약수를 배우면서 자세히 다뤘던 것 같다. 혹시나 최대공약수 개념을 모르거나 헷갈린다면 링크( Link ) 를 타고 가서 한 번 살펴보길 바란다. 이번에 최대공약수를 찾을 때는 무작정 찾는 방법과 유클리드 호제법을 이용하는 방법 2가지를 이용할 것이다.

---

첫 번째로 무작정 찾는 방법이 있다. 어떤 두 자연수를 받아서 큰 수를 a, 작은 수를 b라고 부르자. 이때 최대공약수는 b보다 작거나 같음이 자명하다. 따라서 b부터 시작해서 숫자 크기를 1씩 줄여가면서 a랑 b를 나눌 수 있는지 검사한다. 그렇게 해서 최초로 발견되는 숫자가 최대공약수이다. 다음의 함수로 구할 수 있다.

def gcd_brute_force( a=1, b=0 ):
    div = min(a, b)
    while not ( 0 == a%div == b%div ):
        div -= 1
    return div

5줄의 while 반복문에 진입 직전에 div는 min(a, b)를 가진다. 두 수가 서로소인 경우 (최악의 경우) 반복문을 min(a, b)번만큼 돌아야된다. 따라서 선형 스케일 O(n) 임을 알 수 있다.

두 번째로 유클리드 호제법을 이용한 방법을 설명하겠다. 어떤 두 자연수를 받아서 큰 수를 a, 작은 수를 b라고 부르자. 또한 a를 b로 나눈 나머지를 r이라고 부르자. a,b의 최대공약수는 b,r의 최대공약수가 같다. 다시말해 gcd(a,b) == gcd(b,r)이 성립한다. 이것이 유클리드 호제법이다. 유클리드 호제법을 통해 최대공약수를 계산할 수 있다. 나머지 r이 0이 될때 나누는 수 b이다. 다음 함수로 구할 수 있다.

def gcd_euclid( a=1, b=0 ):
    if b == 0:
        return a
    return gcd_euclid(b, a%b)

이 원리는 구현이 간단하다는 점에서 좋다. 코드가 간결해진다. 또한 0<=r<b가 성립하므로 숫자 크기를 빠르게 줄여가면서 최대공약수를 찾아갈 수 있기 때문에 좋다. r이 0으로 수렴하는 속도가 꽤 빨라서 유용한 알고리즘으로 알려져 있다. 링크 ( Link ) 자료를 참고해서 알아보니 log 스케일 O(log n)임을 알 수 있었다.

---

한편 이들의 연산 속도차가 어느 정도 나는지 실제로 실험해보았다.

import time
 
def gcd_brute_force( a=1, b=0 ):
    div = min(a, b)
    while not ( 0 == a%div == b%div ):
        div -= 1
    return div
 
def gcd_euclid( a=1, b=0 ):
    if b == 0:
        return a
    return gcd_euclid(b, a%b)
 
num1 = input('1st positive integer: ')
num2 = input('2nd positive integer: ')
 
num_iter = 100
time_s = time.time()
for _ in xrange( num_iter ):
    gcd_eu = gcd_euclid(num1, num2)
time_eu = (time.time() - time_s) / num_iter
 
time_s = time.time()
for _ in xrange( num_iter ):
    gcd_bf = gcd_brute_force(num1, num2)
time_bf = (time.time() - time_s) / num_iter
 
print 'GCD of %d,%d is %d. time_eu: %g'%(num1, num2, gcd_eu, time_eu)
print 'GCD of %d,%d is %d. time_bf: %g'%(num1, num2, gcd_bf, time_bf)

17줄에 보면, 100번을 돌려보며 테스트할 수 있게 만들었다. 실제 시스템 시간을 받아서 실험한 것이긴 한데 살펴보면 for 반복문을 조작하는 시간까지 포함된 것이므로 정확히 우리가 알고싶은 알고리즘 계산 시간을 알려주진 못할 수 있다. 그래도 두 알고리즘의 시간 차는 살펴볼 수 있었기에 이대로 비교해보도록 하겠다. 몇몇 테스트의 결과는 아래와 같으며 time은 초 (second) 단위이다.

#1
1st positive integer : 5
2nd positive integer : 20
GCD of 5,20 is 5. time_eu: 1.66893e-06
GCD of 5,20 is 5. time_bf: 1.18017e-06
 
#2
1st positive integer : 4
2nd positive integer : 19
GCD of 4,19 is 1. time_eu: 2.26021e-06
GCD of 4,19 is 1. time_bf: 2.12908e-06
 
#3
1st positive integer : 2354
2nd positive integer : 5786
GCD of 2354,5786 is 22. time_eu: 2.98023e-06
GCD of 2354,5786 is 22. time_bf: 0.00038204
 
#4
1st positive integer : 16758  
2nd positive integer : 27058  
GCD of 16758,27058 is 2. time_eu: 5.55038e-06
GCD of 16758,27058 is 2. time_bf: 0.00230854
 
#5
1st positive integer : 234567
2nd positive integer : 123789
GCD of 234567,123789 is 3. time_eu: 4.71115e-06
GCD of 234567,123789 is 3. time_bf: 0.0167189

위 결과에서 살펴볼 것들은 테스트 1,2번과 3,4,5의 차이에 있다. O(n)인 알고리즘보다 O(log n)인 알고리즘이 항상 빠를 것으로 기대했는데 테스트 1,2번과 같이 작은 숫자들에서는 그렇지 않았다. 아마 함수를 재귀형식으로 부르는 과정에서 차이를 불러일으키는게 아닌가 예상된다. 숫자가 대략 10배씩 커져도 time_eu는 전체적으로 10^-6 스케일로 나타났으며, time_bf는 대략 10배씩 커지는 경향이 있었다. log 스케일의 위대함을 알 수 있는 좋은 예시라고 생각된다.