정수 제곱근 구하기

가끔씩 정수의 제곱근을 구해야할 경우가 가끔씩 있는데, 이때 가장 편한 해결책은 float로 캐스팅해서 sqrt()함수에 넣은뒤 다시 int로 캐스팅하는 것입니다. 요즘 CPU들은 워낙 좋아서 부동소수점 제곱근 연산은 뚝딱 해치우니 속도 걱정은 할 필요가 없지요. 다만... 부동소수점 연산이 잘 지원안되는 환경에서 코딩을 하는 경우에는 정수 제곱근을 구하기위해 선뜻 sqrt함수를 쓰기가 꺼려집니다. 그래서 간단한 연산을 통해 정수 제곱근을 구해내는 함수를 구현해보도록 하겠습니다.

1 2 3 4 5 6 7 8 9 10 11

int isqrt(int n) {     if(n < 0) return -1;     if(n == 0) return 0;     int i = 0;     for(;n >= 0;++i)     {         n -= 2*i + 1;     }     return i-1; }

정수 제곱근을 구해주는 isqrt 함수입니다.구현원리는 정말 단순합니다. 어떤 정수 n으로부터 차례대로 1, 3, 5, 7, 9 ...를 빼가면, 그 빼간 횟수가 n의 정수 제곱근이 됩니다.

잘 이해가 안되신다면, 빼가는 1, 3, 5, 7, 9... 등을 차례로 더하면 뭐가 나오는지 생각해보면 됩니다. 차레로 더하면 1, 4, 9, 16, 25 ... 의 제곱수가 나오잖아요?ㅋ

근데 이건 반복횟수가에 비례해서 증가하기에, 그다지 효율적인 구현이라고는 보기 힘들군요. 약간 최적화해봅시다. 입력된 n이 k비트 정수라고 가정하면, 당연히 n의 제곱근은 k/2비트가 될겁니다. 이걸 이용하면, 반복횟수를 확실히 줄일수 있을듯 한데요?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

int bit8(unsigned char b) {     static int r[256] = {         0, 1, 2, 2, 3, 3, 3, 3,         4, 4, 4, 4, 4, 4, 4, 4,         5, 5, 5, 5, 5, 5, 5, 5,         5, 5, 5, 5, 5, 5, 5, 5,         6, 6, 6, 6, 6, 6, 6, 6,         6, 6, 6, 6, 6, 6, 6, 6,         6, 6, 6, 6, 6, 6, 6, 6,         6, 6, 6, 6, 6, 6, 6, 6,         7, 7, 7, 7, 7, 7, 7, 7,         7, 7, 7, 7, 7, 7, 7, 7,         7, 7, 7, 7, 7, 7, 7, 7,         7, 7, 7, 7, 7, 7, 7, 7,         7, 7, 7, 7, 7, 7, 7, 7,         7, 7, 7, 7, 7, 7, 7, 7,         7, 7, 7, 7, 7, 7, 7, 7,         7, 7, 7, 7, 7, 7, 7, 7,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,         8, 8, 8, 8, 8, 8, 8, 8,     };     return r[b]; }   int bit32(unsigned int b) {     int r;     if((r = bit8(b >> 24)) > 0) return r + 24;     if((r = bit8(b >> 16)) > 0) return r + 16;     if((r = bit8(b >> 8)) > 0) return r + 8;     return bit8(b); } int isqrt2(int n) {     if(n < 0) return -1;     if(n == 0) return 0;     int t = (bit32(n)-1) >> 1;     int i = 1 << t;     n -= 1 << (t << 1);     for(;n >= 0;++i)     {         n -= 2*i + 1;     }     return i-1; }

의도치 않게 코드가 길어졌는데, 위의 bit8과 bit32는 정수가 몇 비트짜리 정수인지 구하기 위한 함수입니다. (기억이 가물가물한데 아마 저 역할을 해주는 어셈블리 연산자가 있었던거 같은데... 찾기 귀찮아서 그냥 함수를 구현해버렸긔ㅋ...) 최적화된 isqrt2함수는 비트수를 이용해 제곱근을 근사해서 i를 설정하고, 거기서부터 차례대로 홀수를 빼나가서 반복횟수를 줄였습니다.

아 최적화를 했으면 성능 비교를 해봐야겠지요.

isqrt함수와 isqrt2함수를 임의의 int 정수 500만개에 대해 수행해보았습니다. (/O2옵션주고 컴파일)

제 컴퓨터의 결과는 isqrt는 890ms, isqrt2는 390ms로 60%에 가까운 속도향상을 보이는군요 훗훗.