No. 116

#### Summing up integers to a given limit

 Q: Suppose an arbitrary number n is given e.g n=5. We want to compute the sum of all integers ranging from 1 to 5: 1 + 2 + 3 + 4 + 5 = 15 Implement the following method by using a loop:/** * Summing up all integers starting from 0 up to and including a given limit * Example: Let the limit be 5, then the result is 1 + 2 + 3 + 4 + 5 * * @param limit The last number to include into the computed sum * @return The sum of 1 + 2 + ... + limit */ public static long getSum (int limit) { ... }For the sake of getting used to it write some unit tests beforehand. BTW: Is it possible to avoid the loop completely achieving the same result? A: The solution's class de.hdm_stuttgart.de.sd1.sum.Summing is being contained within: Maven module source code available at sub directory P/Sd1/summing/V1 below lecture notes' source code root, see hints regarding import. Online browsing of API and implementation. We start by defining unit tests beforehand:/** * Testing negative values and zero. */ @Test public void testNonPositiveLimits() { assertEquals(0, Summing.getSum(-5)); assertEquals(0, Summing.getSum(0)); } /** * Testing positive values. */ @Test public void testPositiveLimits() { assertEquals(1, Summing.getSum(1)); assertEquals(3, Summing.getSum(2)); assertEquals(15, Summing.getSum(5)); assertEquals(5050, Summing.getSum(100)); // Carl Friedrich Gauss at school assertEquals(2147450880, Summing.getSum(65535));// Highest Integer.MAX_VALUE compatible value }The crucial part here is determining 1 + 2 + ... + 65535 being equal to 2147450880. Legend has it the young Carl Friedrich Gauss at school was asked summing up 1 + 2 + ... + 99 + 100. His teacher was keen for some peaceful time but the young pupil decided otherwise: $\underbrace{1 + \underbrace{2 + \underbrace{3 + \dots + 98}_{101} + 99}_{101} + 100}_{101}$ Since there are 50 such terms the result is $50 × 101 = 5050$. Generalizing this example we have: $∑ i = 1 n i = n ⁢ ( n + 1 ) 2$ For the current exercise we do not make use of this. Instead we implement Summing.getSum(...) by coding a loop: /** * Summing up all integers starting from 0 up to and including a given limit * Example: Let the limit be 5, then the result is 1 + 2 + 3 + 4 + 5 * * @param limit The last number to include into the computed sum * @return The sum of 1 + 2 + ... + limit */ public static long getSum (int limit) { int sum = 0; for (int i = 1; i <= limit; i++) { sum += i; } return sum; } }This passes all tests.

No. 117

#### Summing up, the better way

Q:

The previous solution of Summing up integers to a given limit suffers from a performance issue. When dealing with large values like 65535 looping will take some time:

long start = System.nanoTime();
System.out.println("1 + 2 + ... + 65535" + "=" + getSum(65535));
long end = System.nanoTime();
System.out.println("Elapsed time: " + (end - start) + " nanoseconds");
1 + 2 + ... + 65535=2147450880
Elapsed time: 1169805 nanoseconds

Barely more than one millisecond seems to be acceptable. But using the method for calculations inside some tight loop this might have a serious negative performance impact.

Thus implement a better (quicker) solution avoiding the loop by using the explicit form. When you are finished re-estimate execution time and compare the result to the previous solution.

Provide unit tests and take care of larger values. What is the largest possible value? Test it as well!

### Tip

A:

The solution's class de.hdm_stuttgart.de.sd1.sum.Summing is being contained within:

Since only our implementation changes we reuse our existing unit tests. Our first straightforward implementation attempt reads:

public static long getSum (int limit) {
return limit * (limit + 1) / 2;
}

This fails both unit tests. The first error happens at:

assertEquals(0, Summing.getSum(-5));
java.lang.AssertionError:
Expected :0
Actual   :10

We forgot to deal with negative limit values. Our sum is supposed to start with 0 so negative limit values should yield 0 like in our loop based solution:

public static long getSum(int limit) {
if (limit < 0) {
return 0;
} else {
return limit * (limit + 1) / 2; // Order of operation matters
}
}

This helps but one test still fails:

assertEquals(2147450880, Summing.getSumUsingGauss(65535));
java.lang.AssertionError:
Expected :2147450880
Actual   :-32768

This actually is a showstopper for large limit values: The algebraic value of limit * (limit + 1) / 2 might still fit into an int. But limit * (limit + 1) itself not yet divided by 2 may exceed Integer.MAX_VALUE. Since the multiplication happens prior to dividing by 2 we see this overflow error happen.

Solving this issue requires changing the order of operations avoiding arithmetic overflow. Unfortunately the following simple solution does not work either:

public static long getSum(int limit) {
if (limit < 0) {
return 0;
} else {
return limit / 2 * (limit + 1);
}
}

This is only correct if limit is even. Otherwise division by 2 leaves us with a remainder of 1.

However if limit is uneven the second factor limit + 1 will be even. This observation leads us to the final solution:

public static long getSum(int limit) {
if (limit < 0) {
return 0;
} else if (0 == limit % 2){       // even limit, divide by 2
return limit / 2 * (limit + 1); // Avoiding arithmetic overflow
} else {                          // uneven limit, divide (limit + 1 ) by 2
return (limit + 1) / 2 * limit; // Avoiding arithmetic overflow
}
}

This passes all tests. We finally reconsider execution time:

1 + 2 + ... + 65535=2147450880
Elapsed time: 25422 nanoseconds

Thus execution is roughly 46 times faster compared to the loop based approach. This is not surprising since loop execution is expensive in terms of performance.