a^n 계산을 O(log n)으로 하는 법 (분할정복을 이용한 거듭제곱)

(출처: https://cp-algorithms.com/algebra/binary-exp.html)

 

\(a^n = a\times a\times a\times \cdots \times a\) 이렇게 a를 n번 곱해서 구하면 O(n)의 시간복잡도를 갖습니다.

Binary exponentiation(또는 Exponentiation by squaring)이라는 기법을 써주면 O(log n)의 시간복잡도로 a^n을 구할 수 있습니다. 이 방법은 분할정복을 이용한 거듭제곱이라고 부를 수 있겠습니다.

 

이 게시물에서는 n이 자연수일 때만 다루겠습니다. 그리고 (a*b)*c = a*(b*c) (결합법칙, Associativity)이 성립하는 원소만 적용 가능합니다.

 

\[3^{13} = 3^{1101_2} = 3^8 \cdot 3^4 \cdot 3^1\]

예를 들어 3^13을 구한다고 했을 때 13을 이진법으로 나타내면 1101이고, 13 = 1+4+8 입니다.

이 점을 보면 3을 squaring, 즉 이런식으로 3, 3^2, 3^4, 3^8, ... base를 제곱을 해가면서 결과에 포함되는 경우만 곱하면 답을 구할 수 있다는 걸 알 수 있습니다.

 

typedef long long ll;

ll binpow(ll a, ll b) {
	ll res = 1;

	while (b > 0) {
		if (b & 1)
			res *= a;

		a = a * a;
		b >>= 1;
	}

	return res;
}

반복문으로 짠 버전입니다. a(base)를 squaring을 하고, 동시에 b는 오른쪽 쉬프트를 해서 절반씩 줄여나갑니다. b&1일 때 해당 base를 곱해줍니다.

 

\[a^n = \begin{cases}
1 &\text{if } n == 0 \\
\left(a^{\frac{n}{2}}\right)^2 &\text{if } n > 0 \text{ and } n \text{ even}\\
\left(a^{\frac{n - 1}{2}}\right)^2 \cdot a &\text{if } n > 0 \text{ and } n \text{ odd}\\
\end{cases}\]

재귀 식으로 나타내면 위와 같습니다. 개념은 같습니다.

 

ll binpow_recur(ll a, ll b) {
	if (b == 0) return 1;

	ll res = binpow_recur(a, b/2);
	if (b & 1)
		return res * res * a;
	else
		return res * res;
}

재귀 버전입니다. 호출스택때문에 반복문 버전보단 약간 느릴 수도 있겠지만 호출스택이 터지거나 할 일은 없으니 걱정 안하셔도 됩니다. 스택 터지기 전에 오버플로우가 날겁니다.