From: Dana Dahlstrom To: cse15L@ucsd.edu Subject: report X ddahlstr Dana Dahlstrom Report for 2nd failure in Lab X (eXample) Intended Behavior: 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. After fixing an off-by-one defect in the sieving loop that caused failures for any value of max except squares of non-primes, we continued testing the program for successively larger values until we encountered a failure. Failure: At max=64, only primes less than 64 were printed, but not all of them. We tried max=63 and 62 and got the same results. We knew the output for max=32 was correct, so we tried 33, and that output was correct too. But for max=34 it printed every prime less than 34 except the first prime: 2! Lacking any explanation for this, we proceeded to test successive input values using diff to show us what changed from one to the next. For max=35 through max=38 it printed all the primes except 2 and 3. Then at max=39 it printed all the primes except 2, 3, and 7. So it appeared each prime p was dropping out at 32+p. This was highly suggestive because we were already suspicious of the tricky use of bitwise operators, mostly on 64-bit longs, and there are 32 bits in an int! We went looking for an int in place of a long, and it didn't take us long to find int. First Hypothesis: Line 129, the body of FixedSizedBitSet.mask, produces the method's return value by left-shifting the literal 1 by the input modulo 64. But the literal 1 is of type int, and in Java shifting a 32-bit int by 34 bits is the same as shifting it by 2, shifting it by 35 the same as by 3, and so on. This hypothesis accounted for those primes dropping out, because instead of adding 34, 35, and 39 to the sieve, it would mistakenly add 2, 5, and 7, respectively. Since 37 is a prime the code never added 5 to the sieve. First Prediction, Experiment, Results, and Conclusion: We predicted 11 wouldn't be removed for max>=43 because 43 is prime, but 13 would be removed for max>=45 because 45 is composite. Indeed 11 had appeared in our results for max=64, but 13 had not. The results of experiments for max=43 and max=45 also matched our predictions. Second Prediction, Experiment, Results, and Conclusion: Predicting this would result in correct behavior for the examples just discussed, in line 129 we added a cast to coerce the literal 1 to type long. After the program was recompiled, it produced correct lists of primes up to 127. We checked its output for max=128 against a published list of primes and surmised that was convincing evidence the program behaved correctly. Reflections: In retrospect, instead of casting the int literal 1 to a long, we could more simply have used a long literal 1L, but this didn't occur to us at the time.