Helpful Junit methods
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) ...
System.out.println("3.6 - 3 * 1.2 == " + (3.6 - 3 * 1.2));
Result:
3.6 - 3 * 1.2 == 4.440892098500626E-16
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);
}
}
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:
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:
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 . 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:
This passes all tests. |
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:
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: |
Since only our implementation changes we reuse our existing unit tests. Our first straightforward implementation attempt reads:
This fails both unit tests. The first error happens at:
java.lang.AssertionError: Expected :0 Actual :10 We forgot to deal with negative
This helps but one test still fails:
java.lang.AssertionError: Expected :2147450880 Actual :-32768 This actually is a showstopper for large Solving this issue requires changing the order of operations avoiding arithmetic overflow. Unfortunately the following simple solution does not work either:
This is only correct if However if
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. |