임의의 숫자가 제곱수인지 빠르게 판별하는 법

0. 발아점

@chiw00k 님께서 트윗에 올린 질문을 해결하는 과정에서…

@zaeku 님의 솔루션을 공부하면서 의문점이 생겼다.

제곱수인지를 식별하는데 갑자기 아래의 식이 튀어나온 것이다.

h = n & 0xF

1. 기본형

임의의 숫자가 제곱수인지 판별하는 건 사실 그리 어렵지 않다.
대략 아래와 같은 함수만 하나 만들면 된다.

bool IsSquare(unsigned int num) {
  unsigned int temp = (unsigned int)(sqrt((double)num)+0.5);
  return temp*temp == num;
}

하지만, 아무리 컴퓨팅 파워가 좋아져도 sqrt()는 느린 함수다.

위의 함수를 돌리기 전에 제곱수가 아닌 경우를 배제하는 방법을 찾아봤다.

2. 10진수

두 수를 곱한 결과의 1자리수는 원래 숫자의 1자리 숫자의 곱과 같다.
그러니까…

1'2462 x 8'7263 = 10'8747'1506

에서, 1자리 숫자인 6은 2x3의 결과인 것이다.

그런데, 0~9의 숫자를 각각 제곱하면 아래와 같다.

여기서 1자리 숫자만 다 뽑아보면 아래와 같다.
0, 1, 4, 5, 6, 9

이 말의 의미는 이런 것이다.

임의의 숫자의 1자리가 위의 6개 중 하나가 아니면 결코 제곱수가 될 수 없다.

즉, 어떤 숫자가 3으로 끝난다면 이건 제곱수가 아니라는 것이다.
(2, 7, 8도 마찬가지다)

다시 말해, 1자리 숫자가 저 6개일 때만 1.의 함수를 사용하면 함수 사용을 40% 줄일 수 있다.
그것을 식별하려면 나머지(mod) 함수를 사용해야 되지만, 실수 연산에 비할 바는 못된다.

3. 16진수

2.의 방식을 16진수에 적용하면 어떨까?
훨씬 더 우아한 결과가 나온다.

우선, 4진수부터 시작해보자.
0~3을 각각 제곱하면 아래와 같다.

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;
  }
}

4. 테이블 구성

switch-case는 그렇게 느린 함수는 아니다.
하지만, 내부적으로 계속 비교 프로세스가 벌어지는데, 성능에 영향을 미치는 건 사실이다.
이러한 비교 과정을 제거하는 가장 손쉬운 방법은 테이블을 간단히 구성하는 것이다.

또한, 함수 호출시 발생하는 오버헤드를 제거하기 위해 함수 형태는 inline으로 선언할 수 있다.

64진수 기반으로 테이블을 간단히 만들어 처리하려면 아래와 같이 하면 된다.

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

덕분에 많이 배웠습니다.

10진수에서의 나머지 연산이 불필요하다는 뜻임 [본문으로]

'IT > 알고리즘' 카테고리의 다른 글

네이버에 올라온 모 회사 입사 테스트 문제 풀이 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