CSCI 2610 Lecture 4 Notes

Note. Material in brown below is provided for information, but can be skipped if it confuses you. It is not critical.

Conditions

If statements and while loops both test conditions. The following general forms are available for writing conditions.

Simple conditions
x == y    (true if x and y are equal)
x != y    (true if x and y are not equal)
x < y    (true if x is less than y)
x > y    (true if x is greater than y)
x <= y    (true if x is less than or equal to y)
x >= y    (true if x is greater than or equal to y)

For example, the following are conditions. 

    a == b
    y + 4 < x
    z != n + 1

Complex conditions

Suppose that A and B are arbitrary conditions. Then the following are also conditions.
A && B    (true if A and B are both true)
A || B    (true if either A or B or both are true)
!(A)    (true if A is false)

For example, the following are conditions. 

  n > m and m > 0
  x == 0 || y == 0
  !(x > y || y != 0)

Conditions and integers

A condition is a kind of expression. A condition computes an integer in C++. A true condition has value 1 and a false condition has value 0. For example, expression 5 > 2 has value 1, but expression 2 > 5 has value 0.

If statements and while loops test these conditions. Normally, the value that is tested is either 0 or 1. In unusual circumstances, you end up using an integer that is not 0 or 1 as a condition. The rule is that 0 is treated as false, and all other numbers are treated as true. So 

   int y;
   int x = 3;
   if(x) {
     y = 0;
   }
   else {
     y = 1;
   }
sets y = 0, since 3 is treated as true.

Warning

The equality test operator is two consecutive equal signs. If you use just one equal sign, you get an assignment, not an equality test. So 

  if(x = y) {
    ...
  }
does not do what you expect it to do. Pay attention to this, and guard against it in your program.

A loop design example

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;
   }
The following material was not covered on Thursday, but will be discussed on Tuesday.

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.

For convienience, I will write x^k to mean x to the k-th power. Note that this in NOT C++ syntax.

To compute s = x^n, we compute higher and higher powers of x. We will want a value k telling us what power we have so far. The loop invariant is

s = x^k
Let's write a table showing the values that k and s will take on as the loop progresses. We 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 us 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 = x^k at each line. Now we 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, we 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.