54

(-1)^n多くのアルゴリズムでは、通常は系列の因数として (両方とも整数)を計算する必要があります。つまり、-1奇数 n と偶数 nの係数です1。C++ 環境では、次のことがよく見られます。

#include<iostream>
#include<cmath>
int main(){
   int n = 13;
   std::cout << std::pow(-1, n) << std::endl;
}

どちらが良いですか、それとも通常の慣習ですか? （または、他の何か）、

std::pow(-1, n)
std::pow(-1, n%2)
(n%2?-1:1)
(1-2*(n%2))  // (gives incorrect value for negative n)

編集：

さらに、ユーザー @SeverinPappadeux は、(グローバル?) 配列ルックアップに基づく別の代替案を提案しました。私のバージョンは次のとおりです。

const int res[] {-1, 1, -1}; // three elements are needed for negative modulo results
const int* const m1pow = res + 1; 
...
m1pow[n%2]

これで問題が解決するわけではありませんが、発行されたコードを使用することで、いくつかのオプションを破棄できます。

最初は最適化なしで、最終候補は次のとおりです。

   1 - ((n & 1) << 1);

(7演算、メモリアクセスなし)

  mov eax, DWORD PTR [rbp-20]
  add eax, eax
  and eax, 2
  mov edx, 1
  sub edx, eax
  mov eax, edx
  mov DWORD PTR [rbp-16], eax

と

   retvals[n&1];

(5 操作、メモリ -- レジスタ? -- アクセス)

  mov eax, DWORD PTR [rbp-20]
  and eax, 1
  cdqe
  mov eax, DWORD PTR main::retvals[0+rax*4]
  mov DWORD PTR [rbp-8], eax

最適化 (-O3) を使用

   1 - ((n & 1) << 1);

(4演算、メモリアクセスなし)

  add edx, edx
  mov ebp, 1
  and edx, 2
  sub ebp, edx

.

  retvals[n&1];

(4 つの操作、メモリ -- レジスタ? -- アクセス)

  mov eax, edx
  and eax, 1
  movsx rcx, eax
  mov r12d, DWORD PTR main::retvals[0+rcx*4]

.

   n%2?-1:1;

(4演算、メモリアクセスなし)

  cmp eax, 1
  sbb ebx, ebx
  and ebx, 2
  sub ebx, 1

テストはこちらです。操作をすべてまとめて省略しない意味のあるコードを作成するには、いくつかのアクロバットが必要でした。

結論（とりあえず）

したがって、最終的にはレベルの最適化と表現力に依存します。

  • 1 - ((n & 1) << 1);常に良いですが、あまり表現力がありません。
  • retvals[n&1];メモリアクセスには代償を払います。
  • n%2?-1:1;表現力豊かで優れていますが、最適化のみが必要です。
4

7 に答える 7

7

まず、私が知っている最速の isOdd テスト (インライン メソッド)

/**
* Return true if the value is odd
* @value the value to check
*/
inline bool isOdd(int value)
{
return (value & 1);
}

次に、このテストを使用して、奇数の場合は -1、そうでない場合は 1 を返します (これは (-1)^N の実際の出力です)。

/**
* Return the computation of (-1)^N
* @n the N factor
*/
inline int minusOneToN(int n)
{
return isOdd(n)?-1:1;
}

最後に@Guvanteが提案したように、値の符号を反転するだけで乗算を省くことができます（minusOneToN関数の使用を避けます）

/**
* Example of the general usage. Avoids a useless multiplication
* @value The value to flip if it is odd
*/
inline int flipSignIfOdd(int value)
{
return isOdd(value)?-value:value;
}
于 2015-03-19T09:08:25.573 に答える
3

多くのアルゴリズムでは、(-1)^n (両方とも整数) を計算する必要があり、通常は系列の因数として計算されます。つまり、奇数 n の場合は -1、偶数 n の場合は 1 の係数です。

代わりに、シリーズを -x の関数として評価することを検討してください。

于 2015-03-18T20:22:18.210 に答える
1

どうですか

(1 - (n%2)) - (n%2)

n%2ほとんどの場合、一度だけ計算されます

アップデート

実際、最も簡単で最も正しい方法は、テーブルを使用することです

const int res[] {-1, 1, -1};

return res[n%2 + 1];
于 2015-03-18T01:32:44.980 に答える