자연수 승수 연산에 한해, 비트연산 트릭을 활용하여 C++에서 기본으로 제공하는 pow() 함수보다 빠르게 계산하는 방법을 알아봅니다.

TL;DR

double pow_int(double base, int exp)
{
    double result = 1.;
    while (exp)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }
    return result;
}

원리

실수 $a$와 자연수 $n$에 대하여, $a^n$을 계산하는 경우를 살펴보겠습니다.

여기서 $n$은 2진법 변환을 통해 다음과 같이 표현할 수 있습니다.

$n = \sum_{i=0} b_i 2^i \text{, where }b_i=0 \text{ or }1$

위 식을 이용하면 $a^n$은 다음과 같이 변형됩니다.

이 식의 의미를 해석해보면 다음과 같습니다.

1. $n$을 2진법으로 나타내었을 때 낮은 자리수부터 확인($b_0, b_1, ...$

2. 매 $b_i$

3. $b_i$

   $b_i$

예시

$3^5$를 계산해보겠습니다. 여기서 $a=3$

1. 먼저, $n$을 2진법으로 변환하여 $b_i$

   $n=5=1+4=1\times2^0+0\times2^1+1\times2^2$

   $\text{i.e. }b_0=1 \text{, } b_1=0 \text{, } b_2 = 1 \text{, and } b_k = 0 \text{ for }k>=3$

2. 이제 낮은 자리 수부터 확인하며 누적곱 작업을 수행합니다. 누적곱의 초기 값은 곱셈의 항등원인 1로 설정합니다.

   • $a$는 3입니다.

     $b_0$

     결과는 3이 됩니다.

   • $a^2$는 9입니다.

     $b_1$

     결과는 여전히 3입니다.

   • $(a^2)^2$

     $b_2$

     결과는 243이 됩니다.

   • 이후의 $b_k$

코드로의 적용(C++)

위 내용을 코드로 변환하면 다음과 같습니다.

변수명의 의미를 고려하여, 위 식에서 $a$를 base로, $n$을 exp로 명명하였습니다.

double pow_int(double base, int exp)
{
    double result = 1.;
    while (exp)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }
    return result;
}

1. 누적곱을 수행하기 위한 result 변수의 초기 값을 곱셈의 항등원인 1로 설정합니다.

2. exp 값이 유효한 동안 while 반복문을 수행합니다.

   1. exp를 2진법으로 표현하였을 때 의 가장 낮은 자리수를 구합니다. (exp & 1)

      만약 이 값이 1이라면, $b_i$

      만약 이 값이 0이라면, $b_i$

      예를 들어, exp의 $b_0$

   2. exp를 오른쪽으로 한 칸 비트시프트를 수행합니다. (exp >>= 1;)

      이를 통해, 방금 살펴본 $b_i$

   3. base를 제곱합니다. (base *= base;)

      이를 통해 $(...(a^2)^2)...)^2$

3. 최종적으로 누적곱이 수행된 결과를 반환합니다. (return result;)

pow() 함수와의 비교용 예시 코드

코드

#include <iostream>

double pow_int(double base, int exp)
{
    double result = 1.;
    while (exp)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }
    return result;
}

int main()
{
    const int N = 100000000;
    double base = 12.345;
    int exp = 67;
    double result1, result2;

    std::cout << base << "^" << exp << "\n\n";

    auto startT1 = clock();
    for (int i = 0; i < N; ++i)
        result1 = pow(base, exp);
    auto endT1 = clock();
    std::cout << "Calculated by pow() function\n";
    std::cout << "Answer: " << result1 << "\n";
    std::cout << "Elapsed time: " << (endT1 - startT1) << " ms\n\n";
    
    auto startT2 = clock();
    for (int i = 0; i < N; ++i)
        result2 = pow_int(base, exp);
    auto endT2 = clock();
    std::cout << "Calculated by pow_int() function\n";
    std::cout << "Answer: " << result2 << "\n";
    std::cout << "Elapsed time: " << (endT2 - startT2) << " ms\n\n";

    return 0;
}

결과

i5-9500 @ 3.00GHz 기준