[분할정복]Power a^n

문제

aⁿ을 구하는 함수인 power(a,n)을, O(log(n))의 실행시간을 갖도록 구현하시오.

풀이

aⁿ은 직관적으로 풀면 O(n)이다.

         private long power_naive(int a, int n){

                  if(a==0) return 0;

                                                    

                  long result=1;

                  for(int i=0;i<n;i++){

                           result = result * a;

                  }

                  return result;

         } 

근데, 이것을 실행시간이 O(log(n))이 되게, Divide and Conquer를 이용해서 풀수 있다. 

원리는 아래와 같은 거듭제곱의 성질을 이용한 것

a⁸은 다음과 같이 풀 수 있다.

a⁸ = a⁴ x a⁴ 

      a⁴ =a²  x a²

          a² = a x a

일반화하면,

if n이 짝수라면,

   aⁿ = a^n/2 x a^n/2

else

  aⁿ = a^(n-1)/2 x a^(n-1)/2 x a

이것을 구현하면 다음과 같이 될 것이다.

         private long power_divide(int a, int n) {

                  if (a == 0)

                           return 0;

                  if (n == 0)

                           return 1;

                  if (n == 1)

                           return a;

 

                  long y;

                  if ((n & 0x01) == 0x00) {

                           y = power_divide(a, n / 2);

                           return y * y;

                  } else {

                           y = power_divide(a, (n - 1) / 2);

                           return y * y * a;

                  }

         }

이렇게 하면, 이론적으로는 0(n)이 O(log(n))이 되어서, 실행시간이 짧아지나, 현실적으로는 차이가 거의 없다. long형 변수에 대해서 멱승 할 수 있는게, 2를 밑수로 했을 때 최대 power(2,62)정도인데, 이것을 수행하는 데는 O(n)이면 대략 62회, O(long(n))이면 6회정도로, 둘 다 나노 세컨드 단위에 종료된다. 해서, 어느정도 차이나는 지를 보려면 power(2,62)를 수 천번 해야 겨우 2~3ms 정도 차이남을 볼 수 있을 것이다.

그렇다면 어떤 때에 멱승에 대한 구현을 divide and conquer로 해서 효과를 제대로 볼 수 있을 까?

암호 라이브러리 등에 사용되는 BigInteger를 구현할 때다. 이 때는 powr(2,1024) 등을 구현해야하는데, 이 경우는 O(n)과 O(log(n))이 꽤 차이가 난다. 

소스

package divideandconquer;

 

public class Power {

         public static void main(String[] args) {

                  Power power = new Power();

                  power.test();

         }

 

         public Power() {

         }

 

         public void test() {

                  long start, end;

                  long t1 = 0, t2 = 0, t3=0;

 

                  int count = 6000;

                  int a = 2;

                  int n = 61;

 

                  long result = 0;

 

                  // 1. naive

                  start = System.currentTimeMillis();

                  for (int i = 0; i < count; i++) {

                           result = power_naive(a, n);

                  }

                  System.out.println("power_naive(" + a + "," + n + ")=" + result);

                  end = System.currentTimeMillis();

                  t1 = end - start;

 

                  // 2. divide and conquer

                  start = System.currentTimeMillis();

                  for (int i = 0; i < count; i++) {

                           result = power_divide(a, n);

                  }

                  System.out.println("power_divide(" + a + "," + n + ")=" + result);

                  end = System.currentTimeMillis();

                  t2 = end - start;

 

                  // 3. divide and conquer - use table

                  start = System.currentTimeMillis();

                  for (int i = 0; i < count; i++) {

                           result = power_divide2(a, n);

                  }

                  System.out.println("power_divide2(" + a + "," + n + ")=" + result);

                  end = System.currentTimeMillis();

                  t3 = end - start;

 

                  // print

                  System.out.println("naive: " + t1 + "ms");

                  System.out.println("divide: " + t2 + "ms");

                  System.out.println("divide_table: " + t3 + "ms");

 

         }

 

         private long power_naive(int a, int n) {

                  if (a == 0)

                           return 0;

 

                  long result = 1;

                  for (int i = 0; i < n; i++) {

                           result = result * a;

                  }

                  return result;

         }

 

         private long power_divide(int a, int n) {

                  if (a == 0)

                           return 0;

                  if (n == 0)

                           return 1;

                  if (n == 1)

                           return a;

 

                  long y;

                  if ((n & 0x01) == 0x00) {

                           y = power_divide(a, n / 2);

                           return y * y;

                  } else {

                           y = power_divide(a, (n - 1) / 2);

                           return y * y * a;

                  }

         }

 

         long[][] powerTable = new long[10][64];

 

         private long power_divide2(int a, int n) {

                  if (a == 0)

                           return 0;

                  if (n == 0)

                           return 1;

                  if (n == 1)

                           return a;

 

                  long y;

                  if ((n & 0x01) == 0x00) {

                           y = (powerTable[a][n / 2] != 0) ? powerTable[a][n / 2] : power_divide(a, n / 2);

                           return y * y;

                  } else {

                           y = (powerTable[a][(n - 1) / 2] != 0) ? powerTable[a][(n - 1) / 2] : power_divide(a, (n - 1) / 2);

                           return y * y * a;

                  }

         }

}

 

수행결과

power_naive(2,61)=2305843009213693952

power_divide(2,61)=2305843009213693952

power_divide2(2,61)=2305843009213693952

naive: 6ms

divide: 2ms

divide_table: 1ms

-끝-