279

Cで整数を別の整数で累乗する最も効率的な方法は何ですか?

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

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

19 に答える 19

428

二乗によるべき乗。

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

    return result;
}

これは、非対称暗号で膨大な数の剰余累乗を行うための標準的な方法です。

于 2008-09-19T12:54:36.193 に答える
83

二乗による指数化は最適な方法ではないことに注意してください。すべての指数値に対して機能する一般的な方法として実行できるのがおそらく最善ですが、特定の指数値については、より少ない乗算を必要とするより良いシーケンスがある可能性があります。

たとえば、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¹⁵の最短の加算チェーンでは、a³が再利用されるため（たとえば、a⁶=a²（a²）²とは対照的に、a⁶のサブ問題は（a³）²として計算する必要があります。 ）。

于 2008-09-20T18:43:33.227 に答える
28

2 を累乗する必要がある場合。これを行う最も速い方法は、べき乗でビット シフトすることです。

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
于 2011-03-17T21:17:42.417 に答える
12

これが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;
}
于 2012-05-09T13:55:18.637 に答える
8

非常に特殊なケースは、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);
}

ダブルをベースタイプにすると、2の累乗が増えます。（この投稿を二乗するのを手伝ってくれたコメント投稿者に感謝します）。

IEEEフロート、その他のべき乗の特殊なケースについてさらに学習する可能性もあります。

于 2008-09-19T12:35:15.927 に答える
8 
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);
}
于 2008-09-19T14:34:02.023 に答える
6

整数の 2 の累乗を取得したい場合は、常にシフト オプションを使用することをお勧めします。

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

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

于 2012-05-14T07:03:27.027 に答える
4

二乗による累乗の効率に関するコメントのフォローアップとして。

このアプローチの利点は、log(n) 時間で実行されることです。たとえば、x^1048575 (2^20 - 1) などの巨大なものを計算する場合、単純なアプローチを使用して 100 万回以上ループする必要はなく、20 回ループするだけで済みます。

また、コードの複雑さに関しては、最も最適な乗算シーケンスを見つけようとするよりも簡単です。これは、Pramod の提案です。

編集：

オーバーフローの可能性について誰かが私にタグを付ける前に、明確にする必要があると思います。このアプローチは、ある種の hugeint ライブラリがあることを前提としています。

于 2008-10-02T17:39:02.740 に答える
2

パーティーに遅れる:

以下は、可能なy < 0限り最善の解決策でもあります。

  1. intmax_t最大範囲の結果を使用します。に当てはまらない回答の規定はありませんintmax_t。
  2. powjii(0, 0) --> 1これは、この場合の一般的な結果です。

  3. 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*intUBであるオーバーフローの可能性があります。

于 2015-04-01T17:11:11.153 に答える
1

負の指数を考慮したより一般的なソリューション

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);
}
于 2014-06-19T05:30:19.703 に答える
0

計算されたすべてのパワーを記憶し、必要に応じて使用するアルゴリズムを実装しました。たとえば、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);
}
于 2015-08-12T21:16:27.137 に答える
-1

私の場合は少し異なり、力からマスクを作成しようとしていますが、とにかく見つけた解決策を共有したいと思いました.

明らかに、それは 2 のべき乗に対してのみ機能します。

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;
于 2016-08-16T20:55:32.453 に答える