CSCI 2610 Lecture Notes 2

Loop design

The while loop is the most basic looping construct in C++. It is used to do repetitive actions. To master the use of while loops, you need to understand how to think about what a loop is doing. There are two common ways to do that.

  1. Action-oriented loop design has the programmer concentrate on the actions that the loop performs.

  2. Data-oriented loop design has the programmer concentrate on the values that the loop computes.
Here is an example of a problem that can be solved by a loop, with two solutions, one based on action-oriented design and the other based on data-oriented design.

An action-oriented design example

The problem is to compute s = 1 + 2 + 3 + ... + n, where n is given to you by somebody else. Think about the process as follows. To compute s = 1 + 2 + ... + n, you can start with s = 0. Then successively add 1 to s, add 2 to s, ..., add n to s. The actions to be performed in the loop are

Add 1 to s
Add 2 to s
Add 3 to s
...
Add n to s

There is a problem with this. A while loop will do one thing over and over. But the lines that you have so far keep changing; no two of them are exactly the same. There first says to add 1 to s, the second says to add 2 to s, etc. You need a variable to hold the value to be added. Let's call that variable k. Set k = 1 initially. Then the actions to be performed are

Add k to s
Add 1 to k
Add k to s
Add 1 to k
Add k to s
Add 1 to k
...
Add k to s (where k is n at this line)
Add 1 to k

Now you see exactly the same thing over and over. Just repeat

Add k to s
Add 1 to k
over and over. As long as k <= n, you want to do this. Here is a completed loop that computes s = 1 + 2 + ... + n. 
      int k,s;
      s = 0;
      k = 1;
      while(k <= n) {
        s = s + k;
        k = k + 1;
      }

A data-oriented design example

Now let's solve the same problem in a different way. Instead of thinking primarily about the actions to be performed, think about the values to be computed. When you compute 0 + 1 + 2 + 3 + ... + n, you compute more and more of the sum. You start with 0, then 0 + 1, then 0 + 1 + 2, then 0 + 1 + 2 + 3, and so on, until you have the entire value 0 + 1 + 2 + ... + n.

To see what is going on, make a table showing two variables. One variable holds the partial sum, and the other tells how much of the sum you have.

k    s
0    0
1    1   (= 0 + 1)
2    3   (= 0 + 1 + 2)
3    6   (= 0 + 1 + 2 + 3)
4    10   (= 0 + 1 + 2 + 3 + 4)
...
n    0 + 1 + 2 + 3 + ... + n

Now you are ready to think about writing the loop. Clearly, you need two variables, k and s. Each should have initial value 0 (given by the first line of the table). The loop should stop when k == n, so it should only keep going as long as k != n.

What about updating the values of k and n, going from one line to the next? To get from

k    s
2    3   (= 0 + 1 + 2)
to
k    s
3    6   (= 0 + 1 + 2 + 3)
you clearly add 1 to k (making it 3) and then add the updated value (3) of k to s. This will work to get from any line to the next line. The loop looks like this. 
      int k,s;
      k = 0;
      s = 0;
      while(k != n) {
        k = k + 1;
        s = s + k;
      }

Loop invariants

Notice that, for every line in the table for computing 1 + 2 + ... + n, the following assertion is true.
s = 1 + 2 + ... + k
For example, when s = 3 and k = 2, the assertion is true. When s = 10 and k = 4 the assertion is true. No matter what line of the table you choose, the assertion is true. Since this assertion is true at every line, it is invariantly true. It is therefore called a loop invariant.

A loop invariant is a kind of assertion. We will use a special, technical definition of the word assertion. An assertion is a statement that is true or false, and is based solely on the current values of variables. Think of taking a snapshot of the variables at a certain point in the program. An assertion can only talk about what is seen in the snapshot. It cannot talk about what happened before or after the snapshot. For example, if i and j are variables, then

i > j
is an assertion, since whether it is true or false depends only on the current values of i and j. On the other hand,
1 has been added to i
is not an assertion, since this statement is trying to relate the current value of i to a former value of i.

When you try to write a loop invariant, make sure that your loop invariant is an assertion.

Another loop design example

This example uses a function. We will see more on functions in the next lecture. Problem. Write a function called power so that power(x,n) is x to the n-th power. For this function, n must be a nonnegative integer, and x must be a real number.

Solution 1: action-oriented design

First think about how you would solve the problem by hand. To compute 2 to the fourth power, you compute 2*2*2*2. You could write that as 1*2*2*2*2. This can be computed by starting with 1 and multiplying by 2 a total of 4 times.

In general, you can set s = 1, and then multiply s by x a total of n times. To do this, you need a counter (k) telling how many times you have multiplied x into s. The function definition looks like this. 

   double power(double x, int n)
   {
     double s;
     int k;
     s = 1.0;
     k = 1;
     while (k <= n) {
       s = x * s;
       k++;
     }
     return s;
   }

Solution 2: data-oriented design

The action-oriented design is simple if you see it, but it offers little help if you don't see it. Data-oriented design offers a little more help.

To compute s = xn, you compute higher and higher powers of x. You will want a value k telling us what power you have so far. The loop invariant is

s = xk
Let's write a table showing the values that k and s will take on as the loop progresses. You need an example, so choose x = 2.0 and n = 5. Notice that, for each line of the table, the loop invariant is true. (In fact, the loop invariant tells you what to write in the table.) 
         k        s
         0       1.0
         1       2.0
         2       4.0
         3       8.0
         4      16.0
         5      32.0
Check that s = xk at each line. Now you need to write the loop. Clearly, k should initially be 0 and s should initially be 1. (Read this from the first line of the table.)

The last line is special because k == n. So only keep looping as long as k != n. Also notice that, in the last line, the desired value is in variable s.

Now think about how to get from one line to the next. Evidently, you add 1 to k and multiply s by x. The function definition goes as follows. 

   double power(double x, int n)
   {
     double s;
     int k;
     s = 1.0;
     while (k != n) {
       s = x * s;
       k = k + 1;
     }
     return s;
   }
  }
Notice how the data-oriented design leads you to a correct solution. Once you have chosen the invariant, everything else falls out quite easily. With this approach, you often get a loop that works the first time.

Synopsis

The two loop design methods yielded slightly different definitions of function addup. Both work. We just used a different way of thinking to get them.

In some situations, action-oriented loop design is simple and natural. If you see how to solve a problem using action-oriented design, use that. In more complex situations, you can find it difficult to think of the actions to perform. In those cases, switch to data-oriented loop design. It will often lead you in the right direction.

Experience by professional programmers has shown that data-oriented loop design combined with loop invariants is more reliable, and tends to lead to correct programs more often than action-oriented design.