TEUS.me

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

0 → 0
1 → 1
2 → 4
3 → 9
4 → 16
5 → 25
6 → 36
7 → 49
8 → 64
9 → 81

임의의 숫자의 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 님께서 의견들을 주셨다.

덕분에 많이 배웠습니다.