algorithm

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

예를 들어, 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 
    }

}