Introduction

문제해결자체재수강 중 거듭제곱을 빠르게 계산하는 방법에 대해 교수님이 짧게 언급을 하셔서 따로 더 찾아서 공부를 해보았다.

$a^n$을 계산하는 가장 쉬운 방법은 $a$를 $n$번 곱하는 $O(n)$이 걸리는 방식이다.
그러나 지금부터 설명할 방법은 $O(\log n)$에 거듭제곱 계산이 가능하다.

Idea

가령, $3^9$의 지수를 이진수로 표현하면 ${1001}$이다. 그리고 이걸 다시쓰면, ${1001}={1000}+{0001}$이고, ${1000}$은 비트연산으로 세번만에 구해낼 수 있다. 밑을 포함하여 다시 써보면, $3^{1001}=3^{1000}\cdot3^{0001}$이다.

Explanation

$3^{9}$을 계산하기 위해 $3^{8}$과 $3^{1}$을 구하고 이 둘을 곱해보자.

실제 거듭제곱 계산 결과($3^{8}$과 $3^{1}$)를 표시할 변수 a는 3, 지수를 표시할 변수 n은 9, 최종 결과값을 담게될 변수 res는 1로 초기화한다.

int a = 3, n = 9;
int res = 1;

우리가 갖고 있는 변수 a를 계속 제곱하면, $\displaystyle{3\to3^2\to3^4\to3^8\to\cdots}$

while (...)
    {
    ...
        a *= a;
    }

그리고 위 a를 언제 res에 곱해야 할까 생각해보면,
$3^8$과$3^1$일 때 즉, 지수가 1000, 0001일때다.
변수 n을 오른쪽 쉬프트로 컨트롤하면서 1과 bitwise AND연산을 수행하면 우리가 원하는 때에만 res에 a값을 곱해줄 수 있다.

    while (n > 0)
    {
        if ((n & 1) != 0) res *= a;
        a *= a;
        n >>= 1;
    }

#1) a=$3$인 상황, 1001&1==1!=0이므로 res가 3으로 업데이트 된다. ($3^{0001}$을 곱해준 격)
#2) a=$3^2$인 상황, 100&1==0이므로 if문 실행 안됨. ($3^{0010}$은 곱해주지 않은 격)
#3) a=$3^4$인 상황, 10&1==0이므로 if문 실행 안됨. ($3^{0100}$은 곱해주지 않은 격)
#4) a=$3^8$인 상황, 1&1==1!=0이므로 res가 $3^9$으로 업데이트 된다. ($3^{1000}$을 곱해준 격)

Solution

#include <stdio.h>
int func(int a, int n);

int main()
{
    int a = 3, n = 9;
    printf("%d\n", func(a, n));
    return 0;
}

int func(int a, int n)
{
    int res = 1;

    while (n > 0)
    {
        if ((n & 1) != 0) res *= a;
        a *= a;
        n >>= 1;
    }
    return res;
}

Complexity

• Time Complexity : while문의 횟수는 n에 의해 컨트롤 되고, n은 쉬프트연산에 의해 컨트롤 된다. 이때, n을 binary로 변환했을 때의 자릿수는 $\lfloor\log_2n\rfloor+1$이다. 따라서, $O(\log n)$의 시간복잡도를 갖는다.
  또는, 그냥 쉬프트연산이 나누기 2이기 때문이라고 생각해도 무방하다.
• Space Complexity : $O(1)$

지적 및 질문 환영합니다.