분할 정복을 이용한 거듭제곱 최적화

  아마 다음은 이미 알고 있을 것이다.

예를들어 거듭제곱되는 수치가 짝수일 때와 홀수일 때를 예로들면 다음과 같다.

A^4 = (A^2)^2 (짝수일때)
A^5 = A * A^4 = A * (A^2)^2 (홀수일때)

 

만약 A^8이 있다면 원래는 A*A*A*A*A*A*A*A 으로 곱셈 연산을 7번 해야 하지만, A^8을 ((A^2)^2)^2 으로 변경하면 A*A=A', A'^2=A'' 이라 할 시 최종적으로 A'을 구하는데에 A*A로 곱셉 한번, A''=A'*A'을 구하는데도 마찬가지로 곱셈 한번, 최종적으로 A''*A''을 구하는데 곱셈 한 번이 들어간다. 즉 7번의 연산이 3번의 연산으로 줄어든다!

 

즉, 거듭제곱을 위와 같이 계산한다면 원래 N번의 연산이 O(logN)으로 줄어든다. 여기서 분할정복을 활용한다는 말은 위의 공식을 코드로 짤 때 분할정복을 활용하면 쉽게 짤 수 있기 때문이다. 예를들어 위의 방법을 활용해 자바로 짠 A^N을 구하는 코드는 다음과 같다.

private static long pow(long a, long n) {
    if (n == 1)
        return a;
    long tmp = pow(a, n/2);
    if (n%2==0)
        return tmp*tmp;
    else
        return a*tmp*tmp;
}

 

또한 단순히 정수의 거듭제곱 계산에만 활용한다면 큰 의미는 없겠지만, 이 방법을 활용하면 행렬의 거듭제곱 등 다른 부분에도 응용할 수 있다. 예를들어 피보나치수의 경우 원래 알고 있는 f(n) = f(n-1) + f(n-2) (n>=2, f(0)=0, f(1)=1) 를 계속해서 구하는 것 보다 더 빠르게 다음의 행렬 거듭제곱으로 구할 수 있는 공식이 있다.

여기에도 마찬가지로 행렬의 거듭제곱을 계산하기 위해 위에서 말한 분할정복을 활용해 거듭제곱을 계산할 수 있다. 자바 코드로 구현해보면 다음과 같다. (MOD의 경우는 값이 너무 커지므로 해당 값으로 나눈 나머지를 출력한 것이다.)

private static final long MOD = 1000007l;

    private long[][] matrixMult(long[][] a, long[][] b) {
        long[][] arr = new long[2][2];
        arr[0][0] = (a[0][0]*b[0][0]%MOD + a[0][1]*b[1][0]%MOD)%MOD;
        arr[1][0] = (a[0][0]*b[0][1]%MOD + a[0][1]*b[1][1]%MOD)%MOD;
        arr[0][1] = (a[1][0]*b[0][0]%MOD + a[1][1]*b[1][0]%MOD)%MOD;
        arr[1][1] = (a[1][0]*b[0][1]%MOD + a[1][1]*b[1][1]%MOD)%MOD;
        return arr;
    }

    private long[][] fibo(long n) {
        if (n == 1) {
            long[][] arr = {{1,1},{1,0}};
            return arr;
        }
        long[][] tmp = fibo(n/2);
        if (n%2==1) {
            return matrixMult(matrixMult(tmp, tmp), fibo(1));
        } else {
            return matrixMult(tmp, tmp);
        }
    }

위의 로직을 사용할 시, 1,000,000,000,000,000,000 번째 피보나치조차도 O(logN)을 하면 사실 60번의 행렬 곱셈만으로 구할 수 있다(2^60 = 1,152,921,504,606,846,976). 진짜 저걸 다 곱해보면 대략 317년정도 걸릴 연산(대략 1억번 연산에 1초정도로 잡았다.)이 로직 좀 변경했다고 0.1초도 안되서 끝나는 것이다.