0. 발아점
@chiw00k 님께서 트윗에 올린 질문을 해결하는 과정에서…
@zaeku 님의 솔루션을 공부하면서 의문점이 생겼다.
제곱수인지를 식별하는데 갑자기 아래의 식이 튀어나온 것이다.
h = n & 0xF
bool IsSquare(unsigned int num) {
unsigned int temp = (unsigned int)(sqrt((double)num)+0.5);
return temp*temp == num;
}
1'2462 x 8'7263 = 10'8747'1506에서, 1자리 숫자인 6은 2x3의 결과인 것이다.
0 → 0여기서 1자리 숫자만 다 뽑아보면 아래와 같다.
1 → 1
2 → 4
3 → 9
4 → 16
5 → 25
6 → 36
7 → 49
8 → 64
9 → 81
즉, 어떤 숫자가 3으로 끝난다면 이건 제곱수가 아니라는 것이다.임의의 숫자의 1자리가 위의 6개 중 하나가 아니면 결코 제곱수가 될 수 없다.
0 → 0(4)
1 → 1(4)
2 → 10(4)
3 → 21(4)
이 말은 임의의 숫자를 4진수로 표기했을 때 1자리가 2/3이면 제곱수가 아니란 뜻이다.
10진수 40%에 비해 배제할 수 있는 가능성도 50%로 증가했다.
게다가, 이 연산은 간단히 (num & 0x03) 한 방으로 할 수 있다. 1
같은 연산을 8진수로 해보면 1자리 숫자는 0, 1, 4의 3가지로 62.5%를 배제할 수 있다.
16진수로 해보면 0, 1, 4, 9의 4가지로 무려 75%를 배제할 수 있다.
4~128진수에서 배제할 수 있는 비율은 아래 표와 같다.
즉, 아래와 같은 코드를 사용하면 좀 더 효율적인 판별을 할 수 있는 것이다.
bool IsSquare(unsigned int num) {
unsigned int temp;
switch (num & 0x0f) {
case 0:
case 1:
case 4:
case 9:
temp = (unsigned int)(sqrt((double)num)+0.5);
return temp*temp == num;
default:
return false;
}
}
#define BASENUM 64
bool bBase[BASENUM] = {false,};
void prepareToCheckSquare() {
for (int i=0; i<BASENUM; i++) {
bBase[i*i % BASENUM] = true;
}
}
inline bool IsSquare(unsigned int num) {
if (bBase[(int)(num & (BASENUM-1))]) {
unsigned int temp = (unsigned int)(sqrt((double)num)+0.5);
return (temp*temp == num);
} else return false;
}
void main(void) {
prepareToCheckSquare();
}
덧. @chiw00k 님의 질문에 대해 @zaeku, @knauer0x, @NextSocialParty 님께서 의견들을 주셨다.
덕분에 많이 배웠습니다.
네이버에 올라온 모 회사 입사 테스트 문제 풀이 3/4 (0) | 2014.10.12 |
---|---|
네이버에 올라온 모 회사 입사 테스트 문제 풀이 2/4 (2) | 2014.10.12 |
네이버에 올라온 모 회사 입사 테스트 문제 풀이 1/4 (0) | 2014.10.12 |
페북에 올라온 Zig-zag scan 풀이… (0) | 2014.10.09 |
박치욱 님이 트위터에 올린 문제에 대한 솔루션 정리 (4) | 2012.06.30 |
임의의 숫자가 제곱수인지 빠르게 판별하는 법 (1) | 2012.06.27 |
본문과 관련 있는 내용으로 댓글을 남겨주시면 감사하겠습니다.