c++ - (-1)^n c++ 中的幂运算

Question

考虑以下形式的收敛级数：

sum(((-1)^n)*something)

哪里n是迭代的索引（n从1到infinity）。

如果我们直接实现公式，我们有std::pow(-1, n)但是有一个更“快速”的算法技巧来实现它吗？

score 13 · Accepted Answer

检查n是偶数还是奇数，

(n % 2 == 0) ? 1 : -1;

可以。如果你想避免分支，

1 - 2*(n & 1)

score 6 · Accepted Answer

我假设这sum(((-1)^n)*something)是伪代码，并且n是一个受总和约束的变量。

让我们将该符号扩展到sum(n <- [0,1,2,3..], ((-1)^n)*f(n)). 您最好的选择可能是首先将其分成两个总和，然后将它们加在一起：

sum(n <- [0,2..], ((-1)^n)*f(n)) + sum(n <- [1,3..], ((-1)^n)*f(n))

在第一个术语中，n总是偶数，所以(-1)^n总是+1。类似地，在第二个任期内，它将永远是-1。我们现在可以重写如下：

sum(n <- [0,2..], f(n)) + sum(n <- [1,3..], -f(n))

由于第二个总和中的每一项都乘以一个常数，因此我们可以将该常数移出总和：

sum(n <- [0,2..], f(n)) - sum(n <- [1,3..], f(n))

现在，让我们确保这些总和采用相同的索引序列，并替换2*m和：2*m+1n

sum(m <- [0,1..], f(2*m)) - sum(m <- [0,1..], f(2*m+1))

现在我们可以再次合并这些总和：

sum(m <- [0,1..], f(2*m) - f(2*m+1))

或者，如果你想要伪 C：

T result = 0;
for(m = 0; m < limit; m+=2) {
    result += f(m);
    result -= f(m+1);
}

正如大多数人似乎在这里所建议的那样，这可以为您节省乘以+1or 。-1由于您的序列是收敛的，因此采用额外的术语不应对答案的正确性产生负面影响。

score 1 · Accepted Answer

是的，有一个魔术：(-1)^n == 1当且仅当n是偶数，(-1)^n == -1当且仅当n是奇数。因此：

int p = (n % 2 == 0) ? 1 : -1;
sum(p*something)

score 1 · Accepted Answer

该术语((-1)^n)*something计算-something为奇数n或something偶数n：

n & 1 ? -something : something

Ifsomething是一个常数值，则sum(((-1)^n)*something)计算-something的最后一个值为n奇数或被0加数为偶数的时间：

n & 1 ? -something : 0

在这种情况下，意甲不会收敛。

score 1 · Accepted Answer

如果您在循环中执行此操作，您可以简单地执行以下操作：

x = 1;   // Assuming we start on n = 0
for(...)    // or while(...)
{
   sum += x * something;

   x = -x;
}

这很可能比对 n 进行检查要快得多 - 当然，它确实假设所有 n 值都被迭代，并且您不会在这里和那里跳过一些......

5 回答 5