이진 거듭제곱

이진 거듭제곱은 임의의 수를 $O(\log n)$번의 곱셈(일반적인 방법에서는 $n$번의 곱셈)으로 $n$제곱하는 기법입니다.

#기본 아이디어

임의의 수 $a$와 짝수 $n$에 대해 다음 항등식이 성립함에 주목하십시오:

결국 임의의 짝수 $n$에 대해 곱셈 연산 단 한 번만으로 문제를 절반 크기($n’ = \frac{n}{2}$)의 문제로 줄일 수 있습니다.

반면 $n$이 홀수이면 다음이 성립합니다:

결국 홀수 $n$에 대해서는 크기가 $(n-1)$인 문제로 환원할 수 있으며, 이 문제는 이미 짝수가 됩니다.

사실상 우리는 $a^n$을 계산하는 점화식을 찾았습니다:

두 번 전이할 때마다 $n$은 최소 절반으로 줄어드는 것이 보장되므로, $n = 0$에 도달하기 전까지 전이는 모두 $2 \cdot \log_2 n$번을 넘지 않습니다. 각 전이에는 정확히 한 번의 곱셈이 필요하므로, 결과적으로 $O(\log n)$번의 곱셈으로 동작하는 알고리즘을 얻었습니다.

#구현

이 알고리즘은 곧바로 재귀적으로 구현할 수 있습니다:

int binpow(int a, int n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1)
        return binpow(a, n - 1) * a;
    else {
        int b = binpow(a, n / 2);
        return b * b;
    }
}

이 구현은 재귀적이어서 실행 시간이 오래 걸립니다. 재귀를 ‘펼쳐서’ 반복적인 구현을 만들어 봅시다.

수 $n$의 이진 표현을 살펴봅시다. 결과 $a^n$은 $a$를 2의 거듭제곱인 어떤 지수들로 거듭제곱한 값들의 곱으로 나타낼 수 있습니다. 예를 들어 $n = 42 = 32 + 8 + 2$이면 다음과 같습니다.

이 곱을 반복적으로 계산하기 위해, 두 개의 변수를 유지하면서 수 $n$의 모든 비트를 순회합시다. 하나는 결과 자체이고, 다른 하나는 $a^{2^k}$의 현재 값입니다. 여기서 $k$는 현재 반복의 번호입니다. 각 단계에서 수 $n$의 $k$번째 비트가 1이면 $a^{2^k}$를 현재 결과에 곱하고, 어떤 경우든 이 값을 제곱하여 다음 반복을 위한 $a^{2^k \cdot 2} = a^{2^{k+1}}$를 얻습니다.

int binpow(int a, int n) {
    int res = 1;
    while (n != 0) {
        if (n & 1)
            res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

많은 프로그래밍 언어에는 이진 거듭제곱이 이미 구현되어 있다는 점을 짚고 넘어갈 필요가 있습니다. 하지만 C++은 그렇지 않습니다. 표준 라이브러리의 pow 함수는 실수에 대해서만 구현되어 있고 근사적인 방법을 사용하므로, 정수 인자에 대해서는 정확한 결과를 내지 못합니다.

#일반화

이진 거듭제곱은 수의 곱셈뿐만 아니라 일반적으로 모든 결합법칙을 만족하는 연산, 즉 임의의 $a$, $b$, $c$에 대해 다음이 성립하는 연산에 적용할 수 있습니다:

가장 명백한 일반화는 모듈러 나머지로의 일반화입니다:

const int mod = 1e9 + 7;

long long binpow(long long a, int n) {
    long long  res = 1;
    while (n != 0) {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

두 번째로 가장 «인기 있는» 일반화는 행렬 곱셈이며, 이에 대해서는 다음 글에서 더 자세히 다루겠습니다.

#등비수열

어떤 객체를 거듭제곱해야 하는 경우는 조합론의 맥락에서 자주 등장하며, 이 밖에도 때로는 다음과 같은 형태의 합을 계산해야 합니다: