From: Dana Dahlstrom To: cse15L@ucsd.edu Subject: report X ddahlstr Dana Dahlstrom Report for 1st failure in Lab X (eXample) The Example program takes a single command-line parameter max, an integer, and is intended to print all the prime numbers up to (and possibly including) max. The primes are to be printed one per line in increasing order starting with 2. As always we attempted to predict the results of our initial experiments on the hypothetical assumption the code would behave as intended. Given 0 or 1 as input, the program terminated with a reasonable error message indicating max had to be at least 2. For 2 and 3 it behaved correctly, but given max=4 it incorrectly included 4, a non-prime, in its output. This was the first failure result we encountered. Looking for a hypothesis to explain the failure we'd observed, we began manually tracing through the code for input max=4. We noted max is passed to the method PrimeFinder.getPrimes, which appeared to implement the sieve of Eratosthenes and return an array of integers containing the primes. We didn't identify any apparent defects in the method. We considered scrutinizing the code in the FixedSizedBitSet class it relies on, but first we decided to do more experiments to better characterize the failure. We tried running the program for max=8, and it printed all the integers from 2 to 8, suggesting the sieve simply wasn't removing any composite numbers. Based on this tentative hypothesis we predicted running the program for max=16 would print all the integers from 2 to 16, but when we tried it, it printed only the primes (2, 3, 5, 7, 11, and 13)! This result invalidated our first hypothesis. Lacking a hypothesis again, we decided to try max=12, midway between 8 and 16. The program printed the primes up to 12, but also printed 9! For max=10 and max=9 it also printed the primes in the range, plus 9 again. We were stumped. We returned to inspecting the code. We saw some opportunities to improve its clarity, efficiency, and exception-handling, but nothing causing a failure. We didn't see anything conspicuously wrong in FixedSizedBitSet, but we sensed there was room for error with all the tricky bitwise operators it uses. We needed a lead. Looking again at our previous results, we decided to trace through the code again thinking about the cases max=8 and max=9 since those results were so different. When we got to line 59 we saw the square root of max was being cast to an int, which effectively takes the floor. For a moment we thought maybe it should be taking the ceiling, and thought about adding 1 or using Math.ceil, but then we remembered how this works: we don't need to sieve out multiples of numbers greater than the square root of max because those are all also multiples of factors less than the square root. Since we need only to sieve out multiples of numbers up to and possibly including the square root of max, the floor of the square root is indeed what we want. Then we noticed the loop-termination condition on line 63 was stopping not at the floor of the square root of max, but just before! This looked like our culprit. It worked as a hypothesis because it explained our prior observations and correctly predicted the result for max=15. For max<9 the sieving loop doesn't even execute once, so every number is printed. For 9<=max<=15 the loop runs once for i=2 and adds multiples of 2 to the sieve, so all the odd numbers are printed, including 9. For max=16 the multiples of 2 and 3 are sieved out, leaving only the primes. (This works only for squares of non-primes.) Our hypothesis seemed solid. We predicted changing the loop to execute one more time for i=stop would add the remaining composites to the sieve in the cases we'd already tried. Indeed, after we made that change, the program behaved correctly for values of max as large as 32; the failure we'd characterized was gone, lending more support to our hypothesis. However, we encountered another failure for larger values, first with max=64.