빠른 거듭제곱 Fast Exponentiation (+ 피보나치 수)

빠른 거듭제곱 : O(log(exp))

 a^b을 구할 때, simple하게는 a를 b번 곱하면 된다. 그러나 b가 너무 커져버릴 경우에는 시간 안에 연산을 끝내지 못할 수도 있다. 이 때 사용하는 게 빠른 거듭제곱 알고리즘이다.

 divide and conquer 방식을 사용하는 것으로, $a^{b}$에서

b가 홀수라면 $a^{b} = a^{\tfrac{b}{2}} \times a^{\tfrac{b}{2}} \times a$
b가 짝수라면 $a^{b} = a^{\tfrac{b}{2}} \times a^{\tfrac{b}{2}}$

를 반복해, b가 0이 될 때까지 반복하는 알고리즘이다.

 top case부터 b=0인 base case까지 귀납적으로 보이면 되고, $\tfrac{b}{2} + \tfrac{b}{4} + ... + 1$ = logb이므로, logb만큼의 시간에 $a^{b}$를 계산할 수 있게 된다.

 master theorem으로 표현하자면 $T\left(n\right)\ =\ T\left(\frac{n}{2}\right)\ +\ c$와 같으므로 $T(n) = O(log(exp))$이다.

 

long long fast_power(long long base, long long exp){
    long long answer = 1; // 연산의 identity
    while(exp){
        if(exp & 1){ // exp % 2 == 1
            answer *= base;
        }
        base *= base; // base = base * base
        exp >>= 1; // exp = exp / 2
    }
    return answer;
}

 만약 문제에서 특정 수로 나누라고 하는 경우는 곱셈이 들어가는 부분에 % 연산을 취해주면 된다.

 

 

 

응용 - 행렬에서 빠른 거듭제곱

 행렬도 똑같이 표현할 수 있다. 다만, 행렬의 경우 행렬 곱 부분이 많이 지저분하기 때문에, 행렬 곱 부분만 따로 떼어내서 operator overloading으로 정리한 후 표현하는 것이 편하다.

 조심할 점은, 정수에서는 identity가 1이지만 행렬에서는 identity matrix를 이용해 주어야 한다는 것

typedef vector<vector<int>> matrix;
int MOD = 1000000007; // 나눌 값

// return result of matrix a * matrix b
// 성능을 위해 kij 순서로 곱
matrix operator*(const matrix& a, const matrix& b){
	int ar = a.size(), bc = b[0].size(), acbr = b.size();
	matrix result(ar, vector<int>(bc, 0));
	for(int k = 0; k<acbr; k++){
		for(int i = 0; i<ar; i++){
			int temp = a[i][k];
			for(int j = 0; j<bc; j++){
				result[i][j] = (temp * b[k][j] + result[i][j]) % MOD;
			}
		}
	}
	return result;
}

int main(){
	...
    matrix base; cin>>base; // 행렬의 입력은 2중 for loop로 입력받겠지만, 편의상 이렇게 표현했다.
    long long factor; cin>>factor; // 몇 번 제곱할 것인지
    matrix result = MATRIX_IDENTITY; // 기본 수는 해당 연산의 identity로 설정
    
    // 방법은 정수의 것과 동일하다.
    while(factor != 0){
        if(B & 1LL){
            result = (result * m);
        }
        m = (m * m);
        B >>= 1;
    }
}

 

 

 

응용 - 피보나치 수 구하기 : O(log(exp))

 

$\begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix} ^{n} =  \begin{bmatrix}F_{n+1} & F_{n} \\F_{n} & F_{n-1} \end{bmatrix}$

 

 위 수식을 이용해 DP로는 O(n)에 풀리는 피보나치 수를 O(logn)에 풀 수 있다. 위 수식의 좌항을 n제곱 한 것이 $F_{n}$이고, 우리는 이미 행렬의 고속 거듭제곱을 알고 있기 때문에 왼쪽 행렬을 n번 거듭제곱 하고, arr[0][1] 또는 arr[1][0]을 리턴하기만 하면 된다.

 

ll factor; cin>>factor;

matrix m(2, vector<ll>(2, 1));
m[1][1] = 0;
// [[1, 1]
//  [1, 0]]

matrix result(2, vector<ll>(2, 0));
result[0][0] = result[1][1] = 1; // result : identity of matrix
// [[1, 0]
//  [0, 1]]

// m^factor
while(factor != 0){
	if(factor & 1LL){
		result = (result * m);
	}
	m = (m * m);
	factor >>= 1;
}

cout<<result[0][1];