Goal: This activity, based on an article in SIGSCE by Henry Walker, Grinnell College, discusses the reasoning underlying a solution to a problem.

Problem: Read a nonzero integer r from the keyboard and compute without using the built-in power function and print r^0, r^1, r^2, r^3, …, r^10.

Program "invlab.cpp" shows two correct solutions to this problem, illustrating that even a simple problem may be solved in different ways. Since each code segment represents a somewhat different way of thinking about problem solving and loops, this lab reasons about each solution in some detail.

1. Make a copy of the program "invlab1.cpp" . Then compile and run it with a few values of r to check how the program works.

In this first approach, at the top of the loop, i represents an exponent and prod represents an r^ i value that is ready to be printed. Initially, i = 0 and prod = 1, which sets up the values for the first pass through the loop. Within the loop, the previously computed values are printed, and then both i and prod are updated for the next time.

//Code Segment 1 cout << "First Approach" << endl; long prod = 1; int i = 0; while (i <= 10) {     cout << prod << endl;     prod *= r;     i++; } cout << endl;

To review, the code works correctly because the following ideas work together properly.

A. At the start of each time through the loop, i represents a current exponent of r and prod represents r -- a value that has not yet been printed. (loop invariant)

B. i and prod are correctly initialized for r^0 , so statement A is true when the loop first begins. (pre condition)

C. Both i and prod are updated correctly during each time through the loop, so statement A is true whenever the loop starts again. (post condition)

D. The exit condition (i <= 10) is consistent with the values i represents, so the loop terminates at the correct time. (exit condition or loop variant)

Statement A above is called a loop invariant. A loop invariant is a statement about variables and relationships among them, where the statement is to be true before and after each iteration of the loop. For a while loop, therefore, a loop invariant is a statement that is true every time the Boolean expression is evaluated.

2. Check your understanding of the term loop invariant by explaining the difference between a loop invariant and an exit condition.

3. For Code Segment 1 above, state the loop invariant and state the loop's exit condition.

Checking the Validity of an Invariant
Within a C++ program, it is possible to check that an invariant is true by placing an appropriate condition in an assert statement which evaluates whether the assertion about the data is true or false. To use such a statement, add the statement

    #include

at the beginning of your program . Then add the assertion for this code segment

    assert( prod == pow(r,i));

just before the loop, at the end of the loop, and just after the loop is over

4. Run the revised program to check that your invariant concerning the values of prod, r and i remain true each time through the loop and after the loop is completed.

5. Change the initialization of i to a value that is invalid according to your invariant, and rerun the program. Describe what happens when a condition is false within an assert statement.

Debugging Hint: When you are finished debugging, an easy way to turn off the asserts is to add the #define NDEBUG directive before the #include directive. All assert statements will then be commented out.

Now, apply what you have learned about loop invariants to code segment 2.

	//Code Segment 2
	cout << "Second Approach" << endl;
	cout << 1 << endl;
	long prod = r;
	int i = 0;
	while (i < 10)
	{	
		cout << prod << endl;
		i++;
		prod *= r;
	}
	cout << endl;

7. Add your loop invariant assertion just before the loop, at the end of the loop, and just after the loop is over to make sure it is correct.