Loops - Multimedia Introduction to Programming Using Java - page 240

invariant: roach population after w weeks is population and
week w- 1's roach volume < apartmentVolume
The postcondition and the invariant differ only in that the postcondition has
one more piece: the roach volume has exceeded the apartment volume.
We now develop the loop using our methodology.
How does it start? The roach population after 0 weeks is 100 . So, we use
the assignments:

w= 0;
population= 100;
When does it stop? When the roach volume is big enough: the roach vol-
ume ≥ apartmentVolume . So the loop condition is the complement of this rela-
tion. Remember, the roach volume is the product of a single-roach volume and
the number of roaches.
How does it make progress? The postcondition requires that apartment-
Volume ≤ roach volume. In order to make progress toward this, the number of
roaches has to increase. According to the roach-population-growth rule at the
beginning of this section, this means adding population * 1.25 to population
(because the population increases by 125 percent). Here, we do the equivalent:
multiply by 5 and divide by 4 , so that all the operations are of type int .
How does it fix the invariant? Because the roach population grows week-
ly, the week number increases by 1.

/* Calculate the number w of weeks it takes a roach infestation to
completely fill an apartment */
int w= 0;
int population= 100; // roach population after w weeks
/* invariant: roach population after w weeks is population and
week w-1 's roach volume < apartmentVolume */
while (apartmentVolume > population * .001) {
population= population + (5 * population) / 4;
w= w + 1;

See lesson
page 7-2 to ob-
tain this loop

}

7.3.2 Exponentiation

Figures. 7.1a and 7.1b contain two loops that compute the value b c ( b multiplied
by itself c times) where b and c are int s. For example, 2 3 = 2 * 2 * 2=8 ; and
2 0 = 1 . We use the second loop to illustrate the power of loop invariants because
it is very hard to understood and develop without an invariant, and it is a much
faster algorithm for computing an exponent.

Activity
7-2.3

The straightforward approach
In the first loop, y is the remaining number of times to multiply by b . Each