CODEWITHSUNDEEP
c++mathoptimization
Vincent
Vincent

Reputation: 60341

(-1)^n exponentiation in c++

Consider a convergent serie in the form:

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

where n is the index of iteration (n goes from 1 to infinity).

If we implement direclty the formula, we have std::pow(-1, n) but is there a more "rapid" algorithmic trick to implement that ?

Upvotes: 2

Views: 322

Answers (5)

GOTO 0
GOTO 0

Reputation: 47614

The term ((-1)^n)*something evaluates to -something for odd n, or something for even n:

n & 1 ? -something : something

If something is a constant value, then sum(((-1)^n)*something) evaluates to -something when the last value of n is odd, or 0 for an even number of summands:

n & 1 ? -something : 0

In this case, the serie would not be convergent.

Upvotes: 1

user824425
user824425

Reputation:

I'm assuming that sum(((-1)^n)*something) is pseudocode, and n is a variable bound by sum.

Let's extend that notation to sum(n <- [0,1,2,3..], ((-1)^n)*f(n)). Your best option would probably be to first split this into two sums, that you add together:

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

In the first term, n is always even, so (-1)^n will always be +1. Analogously, in the second term, it will always be -1. We can now rewrite this as follows:

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

Since every term in the second sum is multiplied by a constant, we can move that constant out of the sum:

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

Now, let's make sure these sums take the same sequences of indices, and substitute 2*m and 2*m+1 for n:

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

Now we can unite these sums again:

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

Or, if you want pseudo-C:

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

This saves you a multiplication by +1 or -1, as most seem to suggest here. Since your sequence is convergent, taking an extra term should not negatively influence the correctness of the answer.

Upvotes: 6

Mats Petersson
Mats Petersson

Reputation: 129314

If you are doing this in a loop, you could simply do:

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

   x = -x;
}

This is most likely a lot faster than doing checks on n - of course, it DOES assume that all n values are iterated over, and you are not skipping a few here and there...

Upvotes: 1

Lumen
Lumen

Reputation: 3574

Yeah, there is a magic trick: (-1)^n == 1 if and only if n is even, and (-1)^n == -1 if and only if n is odd. Thus:

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

Upvotes: 1

Daniel Fischer
Daniel Fischer

Reputation: 183873

Check whether n is even or odd,

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

does it. If you want to avoid a branch,

1 - 2*(n & 1)

Upvotes: 13

Related Questions