[c] 정수 기반의 전력 함수를 구현하는 가장 효율적인 방법 pow (int, int)

참고 제곱에 의해 지수가 가장 최적의 방법은 아닙니다. 모든 지수 값에 대해 작동하는 일반적인 방법으로 수행하는 것이 가장 좋을 수도 있지만 특정 지수 값의 경우 곱셈이 덜 필요한 더 나은 시퀀스가있을 수 있습니다.

예를 들어, x ^ 15를 계산하려는 경우, 제곱 법에 의한 지수 방법은 다음을 제공합니다.

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

이것은 총 6 곱셈입니다.

이것은 추가 사슬 지수 를 통한 “그냥”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

이 최적의 곱셈 시퀀스를 찾기위한 효율적인 알고리즘은 없습니다. 에서 위키 백과 :

가장 짧은 덧셈 체인을 찾는 문제는 최적의 하위 구조의 가정을 만족시키지 않기 때문에 동적 프로그래밍으로는 해결할 수 없습니다. 즉, 전력을 더 작은 전력으로 분해하는 것만으로는 충분하지 않으며, 각각의 전력은 최소로 계산되는데, 더 작은 전력에 대한 추가 체인이 (계산을 공유하기 위해) 관련 될 수 있기 때문이다. 예를 들어, 위의 a¹ for에 대한 가장 짧은 덧셈 체인에서, a³가 재사용되기 때문에 a a의 하위 문제는 (a³) ²로 계산되어야합니다 (예 : a⁶ = a² (a²) ²). ).

답변

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)

private int ipow(int base, int exp)
{
    int result = 1;
    while (exp != 0)
    {
        if ((exp & 1) == 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}

int pow( int base, int exponent)

{   // Does not work for negative exponents. (But that would be leaving the range of int) 
    if (exponent == 0) return 1;  // base case;
    int temp = pow(base, exponent/2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}

int power(int base, unsigned int exp){

    if (exp == 0)
        return 1;
    int temp = power(base, exp/2);
    if (exp%2 == 0)
        return temp*temp;
    else
        return base*temp*temp;

}

float power(float base, int exp) {

    if( exp == 0)
       return 1;
    float temp = power(base, exp/2);
    if (exp%2 == 0)
        return temp*temp;
    else {
        if(exp > 0)
            return base*temp*temp;
        else
            return (temp*temp)/base; //negative exponent computation 
    }

}