정수 기반 거듭제곱 함수 pow(int, int)를 구현하는 가장 효율적인 방법

https://stackoverflow.com/questions/101439

01-07-2019
|

문제

C에서 정수를 다른 정수의 거듭제곱으로 올리는 가장 효율적인 방법은 무엇입니까?

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

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

해결책

제곱에 의한 지수화.

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

이는 비대칭 암호화에서 거대한 숫자에 대해 모듈러 지수화를 수행하는 표준 방법입니다.

다른 팁

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

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

이 최적의 곱셈 시퀀스를 찾는 효율적인 알고리즘은 없습니다.에서 위키피디아:

가장 짧은 덧셈 사슬을 찾는 문제는 동적 프로그래밍으로 해결할 수 없습니다. 왜냐하면 최적의 하위 구조에 대한 가정을 만족하지 않기 때문입니다.즉, 더 작은 거듭제곱에 대한 덧셈 체인이 (계산을 공유하기 위해) 관련될 수 있으므로 거듭제곱을 더 작은 거듭제곱으로 분해하는 것만으로는 충분하지 않습니다. 각 거듭제곱은 최소로 계산됩니다.예를 들어, 위의 a1⁵에 대한 최단 덧셈 체인에서 a⁶에 대한 하위 문제는 a3가 재사용되므로 (a⁶ = a²(a²)²와는 반대로 3번의 곱셈이 필요하므로 (a³)²로 계산되어야 합니다. ).

2를 거듭제곱해야 하는 경우.가장 빠른 방법은 전력에 따라 비트를 이동하는 것입니다.

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

Java의 메소드는 다음과 같습니다.

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);
}

2의 정수 값을 어떤 것의 거듭제곱으로 구하려면 항상 Shift 옵션을 사용하는 것이 좋습니다.

pow(2,5) 로 대체될 수 있다 1<<5

이것이 훨씬 더 효율적입니다.

매우 특수한 경우는 2^(-x to the y)가 필요한 경우입니다. 여기서 x는 물론 음수이고 y는 int에서 이동하기에는 너무 큽니다.플로트를 조이면 일정한 시간에 2^x를 수행할 수 있습니다.

struct IeeeFloat
{

    unsigned int base : 23;
    unsigned int exponent : 8;
    unsigned int signBit : 1;
};


union IeeeFloatUnion
{
    IeeeFloat brokenOut;
    float f;
};

inline float twoToThe(char exponent)
{
    // notice how the range checking is already done on the exponent var 
    static IeeeFloatUnion u;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

기본 유형으로 double을 사용하면 2의 거듭제곱을 더 많이 얻을 수 있습니다.(이 게시물을 정리하는 데 도움을 주신 댓글 작성자에게 많은 감사를 드립니다.)

에 대해 더 많이 배울 가능성도 있습니다. IEEE 수레, 지수화의 다른 특별한 경우가 나타날 수 있습니다.

제곱에 의한 지수화의 효율성에 대한 의견에 대한 후속 조치와 같습니다.

이 접근 방식의 장점은 log(n) 시간에 실행된다는 것입니다.예를 들어 x^1048575 (2^20 - 1)과 같은 거대한 것을 계산하려는 경우 순진한 접근 방식을 사용하면 루프를 100만 번 이상 통과하지 않고 20번만 루프를 통과하면 됩니다.

또한 코드 복잡성 측면에서 La Pramod의 제안에 따라 가장 최적의 곱셈 시퀀스를 찾는 것보다 간단합니다.

편집하다:

누군가가 나를 오버플로 가능성으로 태그하기 전에 명확히 해야 할 것 같습니다.이 접근 방식은 일종의 hugeint 라이브러리가 있다고 가정합니다.

power() 일하는 기능 정수만

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;

}

복잡도 = O(log(exp))

power() 일하는 기능 음수 exp 및 float 기본.

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 
    }

}

복잡도 = O(log(exp))

파티에 늦었습니다:

다음은 다음을 다루는 솔루션입니다. y < 0 가능한 한 최선을 다합니다.

의 결과를 사용합니다. intmax_t 최대 범위를 위해.적합하지 않은 답변에 대한 규정은 없습니다. intmax_t.
powjii(0, 0) --> 1 이것은 일반적인 결과 이 경우.

pow(0,negative), 정의되지 않은 또 다른 결과가 반환됩니다. INTMAX_MAX

intmax_t powjii(int x, int y) {
  if (y < 0) {
    switch (x) {
      case 0:
        return INTMAX_MAX;
      case 1:
        return 1;
      case -1:
        return y % 2 ? -1 : 1;
    }
    return 0;
  }
  intmax_t z = 1;
  intmax_t base = x;
  for (;;) {
    if (y % 2) {
      z *= base;
    }
    y /= 2;
    if (y == 0) {
      break; 
    }
    base *= base;
  }
  return z;
}

이 코드는 무한 루프를 사용합니다 for(;;) 결승전을 피하기 위해 base *= base 다른 루프 솔루션에서는 일반적입니다.그 곱셈은 1) 필요하지 않으며 2) 그럴 수 있습니다. int*int UB인 오버플로입니다.

음수 지수를 고려한보다 일반적인 솔루션

private static int pow(int base, int exponent) {

    int result = 1;
    if (exponent == 0)
        return result; // base case;

    if (exponent < 0)
        return 1 / pow(base, -exponent);
    int temp = pow(base, exponent / 2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}

또 하나의 구현(Java).가장 효율적인 솔루션은 아닐 수 있지만 반복 횟수는 지수 솔루션과 동일합니다.

public static long pow(long base, long exp){        
    if(exp ==0){
        return 1;
    }
    if(exp ==1){
        return base;
    }

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

exp가 짝수이면 재귀를 사용합니다. 5^10 =25^5.

int pow(float base,float exp){
   if (exp==0)return 1;
   else if(exp>0&&exp%2==0){
      return pow(base*base,exp/2);
   }else if (exp>0&&exp%2!=0){
      return base*pow(base,exp-1);
   }
}

부호 있는 정수로 구현할 때 정의되지 않은 동작을 발생시키는 Elias의 답변과 부호 없는 정수로 구현할 때 높은 입력에 대한 잘못된 값 외에도,

다음은 부호 있는 정수 유형에서도 작동하고 잘못된 값을 제공하지 않는 제곱에 의한 지수화의 수정된 버전입니다.

#include <stdint.h>

#define SQRT_INT64_MAX (INT64_C(0xB504F333))

int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
    int_fast64_t    base_;
    int_fast64_t    result;

    base_   = base;

    if (base_ == 1)
        return  1;
    if (!exp)
        return  1;
    if (!base_)
        return  0;

    result  = 1;
    if (exp & 1)
        result *= base_;
    exp >>= 1;
    while (exp) {
        if (base_ > SQRT_INT64_MAX)
            return  0;
        base_ *= base_;
        if (exp & 1)
            result *= base_;
        exp >>= 1;
    }

    return  result;
}

이 기능에 대한 고려사항:

(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0

넘치거나 포장이 일어날 경우, return 0;

나는 사용했다 int64_t, 그러나 약간의 수정으로 모든 너비(부호 있는 또는 부호 없는)를 사용할 수 있습니다.그러나 고정 너비가 아닌 정수 유형을 사용해야 하는 경우 다음을 변경해야 합니다. SQRT_INT64_MAX ~에 의해 (int)sqrt(INT_MAX) (사용하는 경우 int) 또는 유사한 것으로 최적화되어야 하지만 더 추악하고 C 상수 표현식이 아닙니다.또한 결과를 캐스팅 sqrt() 에 int 완전 제곱의 경우 부동 소수점 정밀도로 인해 그다지 좋지는 않지만 구현 방법을 모르기 때문에 INT_MAX -또는 모든 유형의 최대값은 완전제곱수이므로 그대로 사용할 수 있습니다.

모든 계산된 능력을 기억하고 필요할 때 사용하는 알고리즘을 구현했습니다.예를 들어 x^13은 (x^2)^2^2 * x^2^2 * x와 같습니다. 여기서 x^2^2는 다시 계산하는 대신 테이블에서 가져왔습니다.이것은 기본적으로 @Pramod 답변의 구현입니다(그러나 C#에서는).필요한 곱셈 횟수는 Ceil(Log n)입니다.

public static int Power(int base, int exp)
{
    int tab[] = new int[exp + 1];
    tab[0] = 1;
    tab[1] = base;
    return Power(base, exp, tab);
}

public static int Power(int base, int exp, int tab[])
    {
         if(exp == 0) return 1;
         if(exp == 1) return base;
         int i = 1;
         while(i < exp/2)
         {  
            if(tab[2 * i] <= 0)
                tab[2 * i] = tab[i] * tab[i];
            i = i << 1;
          }
    if(exp <=  i)
        return tab[i];
     else return tab[i] * Power(base, exp - i, tab);
}

내 경우는 조금 다릅니다. 전원으로 마스크를 만들려고 하는데 어쨌든 찾은 솔루션을 공유해야겠다고 생각했습니다.

분명히 이것은 2의 거듭제곱에 대해서만 작동합니다.

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;

컴파일 타임에 지수(그리고 정수)를 알고 있는 경우 템플릿을 사용하여 루프를 풀 수 있습니다.이는 더 효율적으로 이루어질 수 있지만 여기서는 기본 원칙을 보여주고 싶었습니다.

#include <iostream>

template<unsigned long N>
unsigned long inline exp_unroll(unsigned base) {
    return base * exp_unroll<N-1>(base);
}

템플릿 전문화를 사용하여 재귀를 종료합니다.

template<>
unsigned long inline exp_unroll<1>(unsigned base) {
    return base;
}

지수는 런타임에 알려져야 합니다.

int main(int argc, char * argv[]) {
    std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl;
}

2의 거듭제곱이라는 특수한 경우를 무시하고 가장 효율적인 방법은 간단한 반복이 될 것입니다.

int pow(int base, int pow) {
  int res = 1;
  for(int i=pow; i<pow; i++)
    res *= base;

  return res;
}

편집하다:지적했듯이 이것은 가장 효율적인 방법은 아닙니다 ...효율성을 CPU 사이클로 정의하기만 하면 충분히 공평하다고 생각됩니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow