[알고리즘] Repeated Squaring : 분할 정복을 이용한 거듭제곱

1. 정리 요약본

2. Repeated Squaring

2.1 정의와 쓰임새

한국어로는 '분할 정복을 이용한 거듭제곱'
어떤 상황에서 이 알고리즘을 쓰냐? x의 y거듭제곱(mod s)을구해야 할 때 주로 쓴다. 
 

2.2 x^(y) : Naive하게 구하기

비효율적이지만 가장 단순하게 구할 수 있는 방법이다.
x를 y번 곱하면 된다.
하지만 이 방법은 최소 y-1번의 연산이 필요하다. 
 
2의 16승을 구해보자. 우리는 2를 16번 곱하면 된다.
하지만 만약 2의 10^9승을 구하고 싶다면? 마찬가지로 10^9번 연산해야 한다.
당신은 이미 시간초과 판정을 받았다...
 

2.3 x^(y) : 효율적으로 구하기

거듭제곱의 성질을 통해 주어진 예시를 이해해보자
마찬가지로 우리는 2^16을 구하려고 한다!

2^16 = 2^8 * 2^8  (지수 : 16 = 8+8)
2^8 = 2^4 * 2^4    (지수 : 8 = 4+4)
2^4 = 2^2 * 2^2    (지수 : 4 = 2+2)
2^2 = 2^1 * 2^1    (지수 : 2 = 1+1)

 
'지수를 쪼개서 계산하기'가 핵심이다
 
~이번에는 지수가 홀수인 경우를 계산해보자~

2^15 = 2^7 * 2^7 * 2  (지수 : 15 = 7+7+1)
2^7 = 2^3 * 2^3 * 2    (지수 : 7 = 3+3+1)
2^3 = 2^1 * 2^1 *2    (지수 : 3 = 1+1+1)

 
핵심은 같은 지수를 가진 두 거듭제곱을 서로 곱해준다는 것이다.
따라서 지수가 홀수인 경우 마찬가지로 같은 지수를 가진 두 거듭제곱을 곱해준다.
그리고 부족한 지수 1은 따로 곱해준다.
 

2.4 x^(y) (mod s)

2.4.1 전제 조건 

모듈러 연산의 성질이다.

a1 (mod m) = r1
a2 (mod m) = r2
라고 할 때, 양변을 각각 곱하면
a1*a2 (mod m) = r1*r2 (mod m)

[예시]
11 (mod 3) = 2, 7 (mod 3) = 1   ->   77 (mod 3) = 2

 

2.4.2 앞서 구한 x^(y) 식에 모듈러 연산 추가

모듈러 연산의 성질을 그대로 적용하면 된다.
우리는 이후 재귀를 통해 구현할 것이기 때문에 가장 깊은 곳, 즉 2^1부터 연산이 시작된다.
모듈러 연산 값도 따라서 2^1부터 시작해보겠다!

// 2^16 (mod 101) 구하기

2^1 (mod 101) = 2
2^2 (mod 101) = 2*2 (mod 101) = 4 (mod 101) = 4
2^4 (mod 101) = (2^2)*(2^2) (mod 101) = 4*4 (mod 101) = 16 (mod 101) = 16
2^8 (mod 101) = (2^4)*(2^4) (mod 101) = 16*16 (mod 101) = 256 (mod 101) = 54
2^16 (mod 101) = (2^8)*(2^8) (mod 101) = 54*54 (mod 101) = 2916 (mod 101) = 88

 
이렇게 타자로 치니까 눈이 좀 어지러운 것 같다. 
정리 요약본 보시면 됩니다...! 
 

3. 코드 작성(C++)

비재귀 코드

long long modpow(long long x, long long y, long long s) {
	long long r = 1;
	for (; y; y >>= 1) {
		// 오른쪽으로 한 비트씩 시프트하는 연산
		// y를 2로 나누는 것과 동일한 효과
		if (y & 1)
			// y is odd : y & 1 == 1
			// y is even : y & 1 == 0
			r = 1LL * r * x % m;
		x = 1LL * x * x % m;
	}
	return r;
}

 

4. 추천 백준 문제

24059번: Function (acmicpc.net)
 

5. 참고 자료

https://youtu.be/5IyqMDg7jN0?si=KM5K-ANnKViSWlDp

https://youtu.be/RkaOkKg-hpM?si=nbucVFMPIy8t4zWR