Java Reference
In-Depth Information
that k n . For example, if s initially contains 2 values, then initially k+1=n ,
and incrementing k and decrementing n makes k>n .
Off-by-one errors
An off-by-one error occurs when a loop iterates once too many or once too few
times. Many people will tell you that off-by-one errors arise from carelessness,
but that is all they say. They do not tell you how to develop the loop condition so
that off-by-one errors do not occur.
If you follow the guidelines given in this text, you will rarely make off-by-
one errors. As we have said earlier, to find a suitable condition for the loop, com-
pare the invariant, for example:
invariant: The i smallest circles have been drawn
with the postcondition, for example:
postcondition: The n smallest circles have been drawn
and determine a relation that, together with the invariant, implies the postcondi-
tion, for example”
relation: i=n
The complement of this relation is then the loop condition:
loop condition: i!=n
Follow this little methodology and you will rarely make off-by-one errors.
The bound function of a loop
We have been rather informal about checking that a loop makes progress toward
termination. We now look in more detail at what it takes to determine this. We
illustrate the technique using this loop:
// Draw n circles with centers (x , y) and radii of 4 , 8 , 12 , …
int i= 0;
// { invariant: i smallest circles were drawn and 0≤i<n }
while (i != n) {
int r= 5+5*i; // radius of circle i
g.drawOval(x - i , y-i , 2*i , 2 * i);
i= i + 1;
We introduce what we call a bound function , in this case:
Bound function: n-i
This is an integer expression that gives an upper bound on the number of itera-
Search WWH ::

Custom Search