Binary Exponentiation

 

Binary Exponentiation(exponentiation by squaring)은 a의 n제곱을 O(n) 대신 O(logn) 의 곱셈만 사용하여 계산할 수 있는 트릭이다.

이 트릭은 수리적인 일 이외의 다양한 분야에 적용할 수 있고, 때문에 결합법칙을 갖는 모든 연산에 사용될 수 있다.

알고리즘

a의 n제곱은 단순히 a에 a를 n-1번 만큼 곱해주는 것으로 표현할 수 있다. 하지만 이런 방식은 a나 n이 큰 경우 효율적이지 못하다.

Binary Exponentiation의 핵심은, 제곱수 n의 이진표현이다.

다음은 n을 이진수로 변경을 한 예시이다.

적용

기존의 재귀 방식으로 제곱을 계산하는 코드.

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

 

재귀를 사용하지 않고 Binary Exponentiation 을 사용하는 코드.

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}