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

0. 발아점

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

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

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

?

1	h = n & 0xF

1. 기본형

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

?

1 2 3 4

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	1'2462 x 8'7263 = 10'8747'1506

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

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

?

1 2 3 4 5 6 7 8 9 10

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

여기서 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을 각각 제곱하면 아래와 같다.

?

1 2 3 4

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진수에서 배제할 수 있는 비율은 아래 표와 같다.

 

 

 

즉, 아래와 같은 코드를 사용하면 좀 더 효율적인 판별을 할 수 있는 것이다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

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진수 기반으로 테이블을 간단히 만들어 처리하려면 아래와 같이 하면 된다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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

덕분에 많이 배웠습니다.

 

 

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