pow( ) - 거듭제곱 함수 구현하기(정수 기반)

개요

C언어의 수학 함수 중, 거듭제곱을 구하는 pow( )라는 함수가 있다.

예를들어, 2의 10승을 계산하고 싶다면, pow(2.0, 10.0); 형태로 사용하는 함수이다.

이 함수는 math.h 헤더를 include하면 사용할 수 있는 함수이다.

#include <math.h>

double pow(double x, double y);

x : 거듭제곱의 밑수

y : 거듭제곱의 지수

그런데 이렇게 거듭제곱을 계산하는 함수를 직접 구현해야 하는 경우가 있었다.

매우 큰 수의 거듭제곱을 계산하면서 중간중간에 주어진 특정 값으로 mod 연산(나눗셈 후 나머지 값을 취하여 반환하는 연산)을 해야 하는 알고리즘 풀이 문제였다.

문제 조건 상, pow( )를 직접 사용하면 연산속도가 느려지는 상황이라 직접 구현을 시도해 보았다.

my_pow( ) 직접 구현하기

내가 필요한 것은 math.h 에서 제공하는 함수와는 달리, 밑과 지수가 큰 정수(unsigned long long 타입)이면 충분했다.

아래와 같이 구현했다.

편의상 위에서 언급한 mod 연산 부분은 제외하였다.

또한, 항상 exp >= 1 이고 base >= 1 이라고 가정하였다.

unsigned long long my_pow(unsigned long long base, int exp)
{
    unsigned long long res = 1;
    while (exp)
    {
        if (exp & 1)
            res *= base;
        exp >>= 1;
        base *= base;
    }

    return res;
}

설명

조금만 찾아보면 알겠지만, '제곱에 의한 지수법(?)' 표준 방법이라고 한다.

그러나 이것은 모든 지수 값에 대해 작동하는 일반적인 방법으로 할 수있는 최선의 방법 일 수는 있지만 특정 지수 값에 대해서는 더 적은 곱셈으로도 계산 가능한 더 빠른 해결방법이 존재할 수 있다. 즉, 항상 최적의 해결방법은 아니라는 것이다.

예를들면 x의 15승 (x ^ 15) 를 생각해보자.

x^15 = (x^7)*(x^7)*x 

x^7 = (x^3)*(x^3)*x 

x^3 = x*x*x

위의 구현방법으로는 총 6번의 곱셈을 해야 계산결과를 얻게된다.

그러나, 'Addition-Chain exponentiation^[각주:1]' 방법을 사용하면 5번의 곱셈으로 결과를 얻을 수 있다.

n*n = n^2

n^2*n = n^3

n^3*n^3 = n^6

n^6*n^6 = n^12

n^12*n^3 = n^15

사용 예

아래와 같이 사용하면 된다.

// 2^3
pow(2,3); // 8

// 5^5
pow(5,5); // 3125

1. https://en.wikipedia.org/wiki/Addition-chain_exponentiation [본문으로]