No. 121

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: 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. 122

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 nanosecondsBarely 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! A: Maven module source code available at sub directory P/Sd1/summing/V2 below lecture notes' source code root, see hints regarding import. Online browsing of API and implementation. 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 :10We 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 :-32768This 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 nanosecondsThus 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.