018. 거듭제곱

2.12 거듭제곱

이번 장에서는 A가 BIGINT, e가 양의정수일 때, A^e를 구한는 알고리즘을 알아본다.

 

A¹⁶을 구하기 위해서는 A를 15번 곱해도 된다. 그러나, 더 좋은 방법이 있다. 아래처럼 구하는 것이다.

A¹⁶ = (((A²)²)²)²

즉, A², A⁴, A⁸, A¹⁶의 차례로 구하는 것이다.

 

일반화해서 지수가 e일 때 어떻게 간략화할 수 있을까?

아래표를 보자

거듭제곱	지수(십진수)	지수(이진수)	향상된 계산방법	공식(1:SX 0:S) (첫째 비트1 제외)
A2	2	10	A2	S
A3	3	11	A2A	SX
A4	4	100	(A2)2	S S
A5	5	101	(A2)2A	S SX
A6	6	110	(A2A)2	SX S
A7	7	111	(A2A)2A	SX SX
A8	8	1000	((A2)2)2	S S S
A9	9	1001	((A2)2)2A	S S SX

 

지수를 이진수로 나타낸 것과 계산방법을 보면 규칙성이 있다. 가장 왼쪽편의 1을 무시하면, 그다음 부터 1이면 A²A이고 0이면 A².

예를 들어 A⁶은 지수가 6이고, 6을 이진수로 나타내면 (110)₂이다. 이것은 (A²A)²이다. 이진수의 1이 A²A가 되고, 그 다음 0에 의해 (A²A)²가 되었다.  이것을 1인 경우는 SX, 0인 경우는 S로 나타내면 (SX S)가 된다.

이를 프로그램화할 때는, 뒤에서부터 처리하는게 편하다. A⁶의 경우 지구 110에 대해서 오른편 끝에서 왼쪽으로 처리. 즉, 지수를 오른쪽으로 쉬프트 시키면서(2로 나누는 것과 동일), 끝 자리가 1인지 0인지 확인하면서(짝/홀수로 구분해도 동일), 제곱만 하던지 아니면 제곱에 밑수를 곱하는 것까지 하던지를 계속해 나가면 된다. 소스는 아래와 같다.

long long power(long long a, int e){

         long long y = 1;

        

         while (e){

                  if (e & 1) y *= a;

                  a *= a;

                  e >>= 1;

         }

         return y;

}

소스를 보면, 

 - e를 계속해서 오른쪽으로 쉬프트 시키면, 언젠가는 zero가 될것이다. 그 전까지 계속 수행.

 - A⁶에 대해 수행되는 과정을 보면 다음과 같다.

    e      y     a

   -------------------

    110   1     a

    110   1     a²

     11   a²   a²a

      1   a²a  (a²a)²

      0

-끝-