Helpful Junit methods


Figure 322. Caution comparing float / double !! Slide presentation
Caution comparing float / double !!

Figure 323. Weird arithmetics? Slide presentation
java.lang.AssertionError: Use assertEquals(expected, actual, delta)
  to compare floating-point numbers

at org.junit.Assert.assertEquals(Assert.java:656)
at qq.doubleCompareTest.test1_3(doubleCompareTest.java:15)
...

Figure 324. Limited representation precision Slide presentation
System.out.println("3.6 - 3 * 1.2 == " + (3.6 - 3 * 1.2));

Result:

3.6 - 3 * 1.2 == 4.440892098500626E-16

Figure 325. Solving the issue Slide presentation
public class doubleCompareTest {
  static final double delta = 1E-15;
  /**
   * Comparing 3.6 and 3 * 1.2 within delta's limit
   */
  @Test
  public void test1_3() {
    Assert.assertEquals(3.6, 3 * 1.2 , delta);
  }
}

exercise No. 119

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:

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.

exercise No. 120

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!

A:

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.