整数ベースのべき乗関数 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

この最適な乗算シーケンスを見つけるための効率的なアルゴリズムはありません。からウィキペディア:

最短の加算チェーンを見つける問題は、最適な部分構造の仮定を満たさないため、動的計画法では解決できません。つまり、より小さなべき乗の加算チェーンが（計算を共有するために）関連している可能性があるため、べき乗をより小さなべき乗に分解し、それぞれが最小限に計算されるだけでは十分ではありません。たとえば、上記の a¹5 の最短の加算チェーンでは、a⁶ の部分問題は (a3)² として計算する必要があります。これは、a3 が再利用されるためです (たとえば、a⁶ = a²(a²)² ではなく、これには 3 つの乗算も必要です)。）。

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 の累乗値を取得したい場合は、常にシフトオプションを使用することをお勧めします。

pow(2,5) で置き換えることができます 1<<5

これははるかに効率的です。

非常に特殊なケースは、たとえば 2^(-x から y) が必要な場合です。ここで、x は当然負であり、y は int でシフトするには大きすぎます。float をねじ込むことで、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) などの巨大なものを計算する場合、ループを 20 回実行するだけでよく、単純なアプローチでは 100 万回以上ループする必要はありません。

また、コードの複雑さの点でも、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);
}

もう 1 つの実装 (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