c++ - cmath での pow() の実装と効率的な置換

Question

を実行してcmath計算することを読みました。が整数の場合は使用しないでください。計算が大幅に遅くなるからです。いつどのような代替手段がありますかpow(a,b)exp(b*log(a))b

1. 同じ定数で連続する多くの s を計算するpow()a
2. は間違いなく整数にbなることが事前にわかっていますか?

これらの特定のシナリオで効率的な高速な代替手段を探しています。

Answer 1

私が何年にもわたって集めてきたより高速な代替手段がいくつかあります。これらは通常recursive、関数の実装に依存しており、保証されている場合は乗算を処理するためのビット シフトです。integer以下は、 、 、floatに合わせた機能を提供しますdouble。それらは通常のものですが、disclaimer:可能なすべてのテストが実行されたわけではなく、ユーザーは呼び出し前と戻り時に入力が正常であることを検証する必要があります...何とか、何とか、何とか..しかし、それらは非常に便利です:

ブルームーンで指摘されているように、適切な帰属はGeeks Pow(x,n) の Geeksにあると思います。私は長い間リンクを失っていました..それはそれらのように見えます. （マイナス1つか2つの微調整）。

/* Function to calculate x raised to the power y

    Time Complexity: O(n)
    Space Complexity: O(1)
    Algorithmic Paradigm: Divide and conquer.
*/
int power1 (int x, unsigned int y)
{
    if (y == 0)
        return 1;
    else if ((y % 2) == 0)
        return power1 (x, y / 2) * power1 (x, y / 2);
    else
        return x * power1 (x, y / 2) * power1 (x, y / 2);

}

/* Function to calculate x raised to the power y in O(logn)
    Time Complexity of optimized solution: O(logn)
*/
int power2 (int x, unsigned int y)
{
    int temp;
    if (y == 0)
        return 1;

    temp = power2 (x, y / 2);
    if ((y % 2) == 0)
        return temp * temp;
    else
        return x * temp * temp;
}

/* Extended version of power function that can work
for float x and negative y
*/
float powerf (float x, int y)
{
    float temp;
    if (y == 0)
    return 1;
    temp = powerf (x, y / 2);
    if ((y % 2) == 0) {
        return temp * temp;
    } else {
        if (y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}

/* Extended version of power function that can work
for double x and negative y
*/
double powerd (double x, int y)
{
    double temp;
    if (y == 0)
    return 1;
    temp = powerd (x, y / 2);
    if ((y % 2) == 0) {
        return temp * temp;
    } else {
        if (y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}

Answer 2

非再帰的非浮動小数点の答え

uintmax_t/intmax_tご希望のタイプに交換してください。オーバーフローが検出されませんでした。

uintmax_t powjuu(unsigned x, unsigned y) {
  uintmax_t z = 1;
  uintmax_t base = x;
  while (y) {
    if (y & 1) {  // or y%2
      z *= base;
    }
    y >>= 1; // or y /= 2
    base *= base;
  }
  return z;
}

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;
  while (y) {
    if (y & 1) {
      z *= base;
    }
    y >>= 1;
    base *= base;
  }
  return z;
}

Answer 3

これを確認することをお勧めします。pow 関数を置き換える高速なアルゴリズムです。