Unit testing

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:

Since there are 50 such terms the result is $\mathrm{50}\times \mathrm{101}=\mathrm{5050}$. Generalizing this example we have:

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.

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.