Exponent Implementation

Exponent 구현 설명

• $a^b$ 를 컴퓨터를 통해 계산하기 위해서는, a를 b번 곱하는 방법이 가장 직관적. 시간 복잡도는 $O(b)$
• 그러나 이 방법은 $b$ 가 아주 큰 경우 비효율적
• 다음과 같은 방법을 통해 시간 복잡도를 $O(lg{b})$ 로 줄일 수 있음
• $b$ 를 이진수로 생각해서, $b = b_k * 2^k + b_{k-1} * 2^{k-1} +…+ b_0 * 2^0$로 표현 가능
• 이러면 $a^b$ 는 다음과 같은 연속곱으로 표현됨

$$a^b = \prod_{b_i=1} (a^{2^i}) ^ {b_i}$$

구현

int a = read();
int b = read();
int result = 1;

while (b != 0) {
    if (b % 2 == 1) {   // b_i 가 1인 경우
        result *= a;    // 결과에 a^2^i 를 곱함
    }
    a *= a;             // a^2^i를 a^2^(i+1) 로 만듦
    b /= 2;
}