(-1)^k is +1 if k is even and -1 if k is odd. Now, we have k = i + 1. I.e., whenever i is even, then k is odd and vice versa.
Or, in other words, (-1)^(i+1) is -1 if i even and +1 if i is odd.
You can test whether an int is even by looking at the remainder of the division by 2. C#'s Modulus operator % is yielding this remainder.
static double SumSequenceElements(int n)
{
int i = 1;
double sum = 0;
while (i <= n)
{
double power = i % 2 == 0 ? -1 : +1;
sum += power / (i * (i + 1));
i++;
}
return sum;
}
By avoiding the inner loop, the computational complexity decreases from O(n^2) to O(n), i.e., from quadratic to linear. A made a little benchmark on my PC. With n = 1 million, both of my methods (above and below) take 2 ms to run, your method takes about 16 minutes on my PC. This is exactly the expected speed increase of 1/2 a million which corresponds to the average number of times the inner loop is running for 1 iteration of the outer loop.
Btw., ?: is the ternary conditional operator.
Since the sign of this +/-1 power is switching between + and - at each iteration. You can also write:
static double SumSequenceElements(int n)
{
int i = 1;
double power = 1; // Since we start with i = 1
double sum = 0;
while (i <= n)
{
sum += power / (i * (i + 1));
power *= -1; // Change the sign of power
i++;
}
return sum;
}
This does the same calculation as you did, but instead of using a nested loop which starts at power = 1 every time, we calculate it continuously in the outer loop.
power *= -1 uses a Compound assignment to calculate power = power * -1.
Update: Source of numerical errors
As part of the calculation, we compute i * (i + 1). i is an int with a range of ~ -2 billions to +2 billions. We get an arithmetic overflow when i is >= 46340 (which is ~sqrt(2^31)).
There are two possibilities to fix the error:
- Declare
i as long. Works with n < ~ 3 billions ~ sqrt(2^63).
- Calculate
i * (i + 1.0) instead. Note that we add 1.0 instead of 1. This switches from int arithmetic to double arithmetic with Max(double) = ~1.7 × 10^308.
Another improvement we can make is to reverse the loop. Adding small numbers to a much larger number leads to loss of precision for floating point numbers. Therefore we should start by adding the small fractions.
By using long and 1.0 we are not limited by the 2 billions limit for n and not for the ~3 billions limit for i * (i + 1). My ultimate solution also uses the reversed loop for increased precision:
static double SumSequenceElements(long n)
{
long i = n;
double power = i % 2 == 0 ? -1 : +1;
double sum = 0;
while (i >= 1) {
sum += power / (i * (i + 1.0));
power *= -1; // Change the sign of power
i--;
}
return sum;
}
This version is somewhat faster than the forward loop, because the loop conditions tests i versus the constant value 1, where as the forward loop tests it versus the variable n.
Tested for n = 10,000,000,000. Result: 0.38629436111989063 in ~21.8 seconds.
