말 그대로 잡설

psycho 2014. 8. 25. 15:09

 프로그램을 짜다 보면 제곱근의 정수 부분을 구해야 할 일이 가끔씩 생긴다. 간단하게 예를 들어 소수 판정 알고리즘을 만든다고 하자. "어떤 수가 있을 때 그 수를 나누어 나머지가 0이 되는 수는 1과 그 수 자신밖에 없다"는 소수의 정의 그대로 판정하자면, n이 소수인지 알기 위해서는 2 이상 n 미만의 모든 수로 나눠보아야 한다. 문제는 이게 판정해야 할 수 n이 커지면 엄청나게 오래 걸린다는 사실이다. 그렇기 때문에 판정하는 데 필요한 연산의 횟수를 줄이기 위한 수학적인 아이디어들이 필요하게 되는데, 그 중 하나가 제곱근이다. n이 n의 제곱근보다 큰 어떤 수로 나누어 떨어진다면, 당연히 그 짝이 되는 n의 제곱근보다 작은 수로도 나누어 떨어져야 하기 때문에, 2 이상 n의 제곱근보다 작은 수들로 나누어보면 그 수가 소수인지 아닌지 알 수 있게 되는 것이다. 물론 이런 아이디어에는 해당 범위의 소수만으로 나누어보면 된다는 등의 여러 아이디어들이 더 있지만, 주제에서 벗어나는 만큼 여기서는 생략하도록 한다.

 

 앞의 예 같은 경우가 아니더라도, 어떤 수의 제곱근의 정수 부분을 구할 일이 생겼다고 치자. C를 기준으로 이야기하자면, 가장 간단한 방법은 sqrt()와 floor() 함수를 조합하는 것이다. C 표준 함수이기 때문에 특별히 이식성에 문제가 생기지도 않는다. 문제는 이게 정수 연산이 아니라 부동소수점 연산이기 때문에, 하드웨어에서 부동소수점 연산을 지원하지 않는 경우 엌 소리 나는 느림맛을 볼 수 있다는 점이다. 거기에 숫자가 굉장히 커지면 부동소수점의 유효숫자 문제 때문에 틀린 값이 나오기도 한다. 수학 함수가 들어가야 하니 프로그램의 덩치가 커지는 건 덤이다. 어차피 필요한 것은 정수부분 뿐이기 때문에, 정수연산만을 활용하여 제곱근을 구하고 싶다면 어떻게 해야 할까?

 

 필자가 필요 반 호기심 반으로 만들어보기 전에, 만인의 숭배를 받는 구글신에는 어떤 괴수가 얼마나 간단하고 쓸만한 알고리즘을 구현해놓았는지 잠깐 검색을 해보았다. 그런데, 필자가 검색어 선정 능력이 일천하여 그런지는 모르나 다음의 알고리즘 정도밖에 건질 수가 없었다1.

 

unsigned long sqrt(unsigned long n)2

{

unsigned long square = 1;

unsigned long delta = 3;

while(square <= n)

{

square += delta;

delta += 2;

}

return (delta / 2 - 1);

}

 

 이 방법은 (n + 1)^2 = n ^ 2 + 2n + 1이라는 등식에 기반한다. 초기치로 1의 제곱인 1을 주고, 2n+1에 해당하는 값을 계속 더해가며 제곱근을 구하고자 하는 값을 넘지 않는 최대의 반복횟수를 찾는 것이다. 이는 2n+1이라는 값을 입력값에서 빼가며 판정하는 다른 페이지3의 알고리즘도 마찬가지이다. 이 알고리즘은 원하는 값을 정확하게 찾아내기는 하지만, 문제는 제곱근을 계산해야 할 값 n이 커지면(극단적으로 2^64에 가까운 값을 주기라도 하면4) 동해물과 백두산이 마르고 닳도록 시간이 걸린다는 데 있다. 이런 식이라면 카운터 변수를 두고 그 숫자의 제곱과 입력값을 비교해서 결정하는 것과 다를 것이 무엇인가. "덧셈만 사용 가능한" 장비가 아니라면 이런 방법을 쓰는 건 분명 바람직하지 않다.

 

 여기서부터가 본론이다. 검색과 정렬에 대해 배운 적이 있는 사람이라면 "이분 검색"이라는 알고리즘을 들어본 적이 있을 것이다. 이 알고리즘을 응용하면 훨씬 빠르게 원하는 값을 찾아낼 수 있다. 다음은 이분 검색을 응용하여 제곱근의 정수부분을 구하는 알고리즘이다.

 

#include <inttypes.h>

uintmax_t int_sqrt(uintmax_t n)
{

uintmax_t min = 0, max = 1ULL << (sizeof(uintmax_t) * 4), r = (min + max) >> 1;

/* Binary search method for finding square root. */
while(min != max - 1)
{

min += (r * r <= n) * ((max - min) >> 1);
max -= (r * r >= n) * ((max - min) >> 1);

r = (min + max) >> 1;

}

return r;

}

 

 이 알고리즘은 입력값의 제곱근으로 가능한 최소값과 최대값을 초기값으로 주고, 그 중간값의 제곱과 입력값을 비교하는 것이 기본 아이디어이다. 이분 검색의 아이디어대로 중간값의 제곱이 입력값보다 크면 범위의 최대값을 줄이고, 작으면 범위의 최소값을 늘린다. 구간의 크기가 1이 되어 반복이 끝나면 임시변수 r에는 입력값 n의 제곱근의 정수 부분이 남게 된다. if문으로 길게 쓰기가 귀찮아 비교부분이 조금 난해한 모양이 되었는데, 이는 대부분의 C 컴파일러에서 비교문이 참이면 숫자 1을 반환하고 거짓이면 숫자 0을 반환한다는 특성을 이용한 것이다.

 

 성능 비교는 따로 게시하지 않겠다. 이유는 구글신을 통해 알아낸 첫 번째 알고리즘이 이 글을 작성하고 있는 현재 돌려놓은 지 몇 시간이 지났음에도 결과를 내놓을 생각을 하고 있지 않기 때문이다. 이건 오래 걸릴 거라는 걸 알면서도 일부러 18446744073709551615(2^64 - 1) 따위의 입력을 준 것이 원인일 것이다. 장비마다 다르겠지만 현재 필자가 이 글을 작성하고 있는 컴퓨터(Core i5-2500S)에서는 그냥 sqrt()와 floor()를 조합하는 방법이 필자가 소개한 알고리즘보다 20배 정도 빠르다는 것만 말해두겠다.

각주 1

http://www.lbebooks.com/downloads/exportal/Verilog_NEXYS_Example24.pdf

각주 2

원문에 약간의 편집을 하였다.

각주 3

http://bab2min.tistory.com/181

각주 4

당연히 제시된 코드 그대로는 안 되고, 자료형을 수정해야 한다.

  1. http://www.lbebooks.com/downloads/exportal/Verilog_NEXYS_Example24.pdf [본문으로]
  2. 원문에 약간의 편집을 하였다. [본문으로]
  3. http://bab2min.tistory.com/181 [본문으로]
  4. 당연히 제시된 코드 그대로는 안 되고, 자료형을 수정해야 한다. [본문으로]