TEUS.me

 
 

주어진 수보다 크거나 같은 최소의 2의 제곱수를 찾아야 될 경우가 있다.

대표적으로 FFT를 기반으로 하는 신호처리의 준비단계.

적절한 개수를 지정해놓고 DFT를 할 수도 있지만, 역시 미친듯한 속도를 내려면 2의 제곱수가 짱짱맨이다.

 

https://en.wikipedia.org/wiki/Power_of_two 에서 빌려옴

 

사실, 요즘 컴퓨팅 환경에서는 이를 위한 가장 빠른 방법[...] 따윈 알아볼 의미가 크게는 없다.

x86/x64 환경이라면 어셈블리 단위에서 LZCNT(Count Leading Zeros) 명령을  지원하기 때문이다.

Visual C++라면 __lzcnt64() 등의 함수로, GCC라면 __builtin_ia32_lzcnt_u64() 등의 함수로 사용할 수 있다.

 

하지만, 세상은 언제나 그렇게 만만하진 않은 법.

파이썬이나 매틀랩 같은 언어에서는 이런 계열의 함수를 지원하지 않고 있다[각주:1].

 

그래서 네 가지의 방식들을 C++와 C#으로 각각 구현하여 약 20억번씩(정확히는 0x8000000 회) 수행한 시간을 측정해봤다.

  • 1. 단순 shift: 0이 될 때까지 우측으로 shift하여 횟수 카운트
  • 2. 우측으로 shift 하면서 or로 합침
  • 3. 수학적 방법: \( log_2 {n}  \)을 활용
  • 4. CPU의 LZCNT 명령 활용

 

실제 수행해본 결과[각주:2]는 아래와 같았다.

 

3번의 경우 C++는 long double로, C#은 double로 구현하여 성능 차이가 발생함

 

당연히 4번(LZCNT)가 가장 빠르지만, 놀랍게도 2번 방식 역시 상당히 쓸만한 수준의 성능을 보여줬다.

20억회 정도 돌린 결과라는 점을 생각해보면 LZCNT 등의 명령을 못 쓰는 경우엔 바로 2번으로 가야 한다.

게다가, C# 에서는 2번이 4번보다 오히려 약간 빠른 성능을 보여줬다.

 

C++ 버전으로 작성된 코드들은 아래와 같다.

 

//1. 단순 shift 연산
uint64_t FindPower2_1(const uint64_t n)
{
    uint64_t p = 1;
    while (p < n) {
        p <<= 1;
    }

    return p;
}

//2. 우측으로 shift 하면서 or로 합침
uint64_t FindPower2_2(const uint64_t n)
{
    if (!n) {
        return 1;
    }
    uint64_t ret = n - 1;
    ret |= (ret >> 1);
    ret |= (ret >> 2);
    ret |= (ret >> 4);
    ret |= (ret >> 8);
    ret |= (ret >> 16);
    ret |= (ret >> 32);

    return ret + 1;
}

//3. log2()
uint64_t FindPower2_3(const uint64_t n)
{
    if (!n) {
        return 1;
    }
    const long double p = ceill(log2l((long double)n));
    return (uint64_t)powl(2, p);
}

//4. leading zero
uint64_t FindPower2_4(const uint64_t n)
{
    return 0x8000000000000000ULL >> (__lzcnt64(n - 1) - 1);
}

 

 

  1. 어쩌면 있는데 내가 못 찾았을 수도 있음 [본문으로]
  2. AMD Ryzen9 5900X, 64GB [본문으로]

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

CMap vs std::map  (4) 2022.09.13
Visual C++에서 Epoch time 계산하기  (0) 2022.08.28
Visual C++의 rand()에 대체 무슨 일이 있는 거냐?  (2) 2022.05.19
memcpy() 계열 최적화?  (0) 2022.02.14
조건에 맞는 기약분수의 갯수  (0) 2021.08.22

공유하기

facebook twitter kakaoTalk kakaostory naver band

댓글

비밀글모드