[Algorithm] Repeated Squaring

Repeated Squaring은 a의 p승을 log 시간에 계산하는 알고리즘이다.
define 된 MOD 는 알고리즘 풀 때 너무 큰 값이 나오는 것을 방지하기 위한 모듈러 값이다.

알고리즘 이해를 해보자.
모든 p는 2의 배수로 나타낼수 있다. 12를 소인수분해 한 나머지를 생각해보자.
8(2의3승) + 4(2의2승) 으로 나타낼 수 있다. 그외의 모든 수가 그러하다. 왜냐하면 모든 수가 2진수로의 변환이 가능하기 때문이다. 12를 소인수 분해한 나머지를 나열해보면 1100이 나온다. 이게 12의 2진수를 의미한다. 그리고 그때마다 해당하는 2의 승수를 곱해주면 된다.

이해가 안갈테니 3의 36승이 있다고 하자. 이 때 36을 소인수분해 후 나머지를 나열해보면
100100 이 나온다. 이 값은 2의 5승 + 2의 2승이며 각각 32와 4이다.
이 때 1의 값이 나올 때의 2의 승수를 계속 곱해주면 값이 나오는 것이다. 이해하기 어려울 것인데....ㅜㅜ

아래 코드를 참고해서 말해 보면.

    a         p       v
3의1승    36      1
3의2승    18      1
3의4승     9       1
3의8승     4    3의4승
3의16승   2    3의4승
3의32승   1    3의4승
3의64승   0    3의4승 * 3의 32승

맨마지막의 v값이 결과다.


#include <stdio.h>
#include <iostream>

#define MOD 1000000007

using namespace std;

int pow(int a, int p)
{
int val = 1;
while (p > 0){
if (p % 2 == 1) val = (val * a) % MOD;
p /= 2;
a = (a *a) % MOD;
}
return val;
}

int main()
{
long long int ret = pow(2, 20);
printf("%lld\n", ret);
return 0;
}