최대공약수(GCD)를 구하는 가장 빠른 방법은?

학교 수학 시간에 안 가르치는 것 같은데, 최대공약수를 구하는 알고리즘이 유클리드 호제법이다.

인류 최초의 알고리즘이라고도 알려져있기도 하다.

 

위대한 수학자 유클리드

 

개념은 단순하다. 서로를 나누어 나머지를 계속 구하는 것.

좀 더 원시적(?)으로 구현하려면 나머지(나누기) 대신 빼기로 구현해도 된다.

 

보통은 아래와 같은 코드를 사용한다.

 

size_t GCD(size_t x, size_t y)
{
	while (y) {
		x %= y;
		if (!x) { return y; }
		y %= x;
	}

	return x;
}

 

그런데, 조금 뒤져보니 Binary GCD라는 알고리즘이 있다.

짝수인 경우 2로 계속 나누어 나눈 횟수를 미리 세어둔 뒤 유클리드 호제법을 사용하는 방식이다.

이 알고리즘은 CPU 명령을 활용하는 _BitScanForward()를 이용하면 상당한 성능 향상을 얻을 수 있다.

 

Visual C++에서 64비트 버전으로 작성하면 아래와 같은 코드가 나온다.

 

size_t GCDfast(size_t x, size_t y)
{
	if (!x || !y) return (x + y);

	unsigned long cf2, temp;
	_BitScanForward64(&cf2, x | y);

	_BitScanForward64(&temp, x);
	x >>= temp;

	for (;;) {
		_BitScanForward64(&temp, y);
		y >>= temp;

		if (x == y) break;
		if (x > y) std::swap(x, y);
		if (x == 1) break;

		y -= x;
	}

	return x << cf2;
}