거듭제곱 빠르게 계산하기

1. Using loop

unsigned long long pow(unsigned long long base, int exp)
{
    long long ans = base;
    for (int i = 1; i < exp; ++i)
    {
        ans *= base;
    }
    return ans;
}

하지만 xnx^nxn에서 nnn이 굉장히 커졌다고 생각했을 때는 이 방법은 굉장히 느리다.

2. Using Recursive Function

unsigned long long pow(unsigned long long base, int exp)
{
    if (exp == 0)
        return 1;
    if (exp & 1)
        return base * pow(base * base, (exp - 1) / 2);
    else
        return pow(base * base, exp / 2);
}

xmn=(xn)mx^{mn} = {(x^n)}^mxmn=(xn)m을 이용한 방법이다.
xnx^nxn을 n이 양수, 짝수 일 때는 (x2)n2{(x^2)}^{\frac{n}{2}}(x2)2n​로 나타낼 수 있고 n이 양수, 홀수 일 때는 x×(x2)n−12x \times {(x^2)}^{\frac{n-1}{2}}x×(x2)2n−1​로 나타낼 수 있다. 이것을 재귀함수로 나타낸 것이고 탈출 조건은 x0=1x^0 = 1x0=1이 있다.

정리를 하면 이렇게 나타낼 수 있다.
f(x,n)={1,n=0x×f(x2,n−12),if  is oddnf(x2,n2),if  is evenn f(x, n) = \begin{cases} 1, & n = 0 \\[2ex] x \times f(x^2, \frac{n-1}{2}), & \text{if $n$ is odd}\\[2ex] f(x^2, \frac{n}{2}), & \text{if $n$ is even} \end{cases} f(x,n)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​1,x×f(x2,2n−1​),f(x2,2n​),​n=0if n is oddif n is even​
재귀함수가 tail recursion이 되지 않는 이상 반복문보다 빠를 수가 없기 때문에 반복문으로도 코드를 작성해 보았다.

3. Using while statement

unsigned long long pow(unsigned long long base, int exp)
{
    if (base == 1)
        return 1;
    long long ans = 1;
    while (exp)
    {
        if (exp & 1)
        { // if exp is odd
            ans = (ans * base);
        }
        base *= base;
        exp >>= 1;
    }
    return ans;
}

exp & 1은 홀수인지 확인하는 것이고 exp >>= 1은 exp /= 2와 같다.