Exponentiation by Squaring

거듭제곱 (Exponentiation)

거듭제곱 연산은 특정 숫자(밑)를 정해진 횟수(지수)만큼 반복해서 곱하는 연산이다. 가장 기본적인 방법은 지수의 크기만큼 반복문을 돌려 곱셈을 수행하는 것이지만, 지수가 매우 커질 경우 연산 시간이 급격히 늘어난다는 단점이 있다.

분할 정복(Divide and Conquer)을 이용한 거듭제곱은 지수를 절반씩 줄여나가며 계산함으로써 이 효율성을 획기적으로 개선한다. 지수가 $N$일 때 연산 횟수를 $O(N)$에서 $O(\log N)$으로 단축할 수 있기 때문에, 아득히 큰 범위의 숫자를 다루는 BigInteger 연산 등에서 필수적으로 사용된다.

알고리즘 원리

분할 정복의 핵심은 큰 문제를 작은 문제로 쪼개는 것이다. $x^n$을 계산할 때, $n$의 상태에 따라 다음과 같이 수식을 전개할 수 있다.

1. $n$이 짝수일 때: $x^n = (x^{n/2})^2$
2. $n$이 홀수일 때: $x^n = x \times (x^{(n-1)/2})^2$

이 방식을 사용하면 매 단계마다 지수가 절반으로 줄어든다. 예를 들어 $x^8$을 구할 때, 기존 방식은 $8$번의 곱셈이 필요하지만 분할 정복을 이용하면 $x^2$, $x^4$, $x^8$ 순으로 단 $3$번의 곱셈만으로 결과를 얻을 수 있다.

구현 방법

알고리즘 문제 풀이에서는 거듭제곱의 결과가 자료형의 범위를 초과하는 경우가 많으므로, 보통 특정 수로 나눈 나머지(mod)를 구하는 모듈러 거듭제곱 형태로 구현한다.

반복문을 이용한 구현

이 방식은 지수를 이진수 형태로 보며 각 비트가 $1$인 경우에만 결과값에 밑을 곱해주는 원리를 가진다.

typedef long long ll;

ll modular_power(ll x, ll y, ll mod) {
    ll res = 1;
    x %= mod;    // 밑에 미리 mod 연산 적용
    
    while (y > 0) {
        if (y % 2 == 1) { // 지수가 홀수인 경우
            res = (res * x) % mod;
        }
        x = (x * x) % mod; // 밑을 제곱하여 지수를 절반으로 줄이는 효과
        y /= 2;            // 지수를 2로 나눔
    }
    return res;
}

---

활용 분야

• 소수판별법 :: 밀러-라빈 알고리즘: 소수 판별 시 $a^{d \times 2^r} \equiv -1 \pmod{n}$ 등의 연산을 수행하기 위해 매우 큰 수의 거듭제곱 나머지를 빠르게 계산해야 한다.
• 페르마의 소정리: $p$가 소수일 때 모듈러 역원을 구하기 위해 $a^{p-2} \pmod{p}$를 계산할 때 핵심적인 역할을 한다.
• BigInteger 연산: long long 범위를 뛰어넘는 큰 수의 거듭제곱을 구현할 때 분할 정복을 활용하여 시간을 단축한다.
• 행렬 거듭제곱: 피보나치 수열을 $O(\log N)$으로 구하거나 그래프의 경로 개수를 셀 때 행렬 곱셈과 결합하여 사용한다.

---

시간 복잡도

• 기본 반복문: $O(N)$ (여기서 $N$은 지수)
• 분할 정복 이용: $O(\log N)$