4. Computation

"If [a program] doesn't have to produce correct results, I can make it arbitrarily fast." -- Gerald M. Weinberg

4.1 Computation
  • All programs "compute": they run on computers, after all! And all they do can be called computation.
  • But: we can usefully break down this truism and say that different parts of a program compute based on input from another part, and then output the result to be used by some other part.
  • So we can view our programs as pockets of computation connected by I/O channels.
  • Inside a program, the inputs are often called arguments and the outputs are called results.
  • So our refined view of our programs is:
4.2 Objectives and tools

We want to express computations:

  • Correctly
  • Simply
  • Efficiently

These are the requirements of professionalism! And the order matters: no one cares if a program is fast at getting the wrong answer. And it can be correct and fast, but if it is too complex to understand, no one will be able to maintain it.

Our chief tool for organizing our programs is to break up large problems into smaller ones. This divides into two variations:

  • Abstraction: hide messy details behind a simple interface.
  • "Divide and conquer": break up the problem we have to solve into smaller problems, each of which is easier to solve then the big problem.

We break up our code into discrete "chunks" because a 1000-line chunk of code will have far more than 10 times the bugs as ten 100-line chunks of code. Also, we should use existing tools, such as libraries, whenever possible: someone else wrote and debugged it for us! iostream is a great example of this: if we had to deal with the I/O hardware directly, we might be writing hundreds of lines of code to do so.

4.3 Expressions
  • An expression computes a value from a number of operands.
  • The simplest expression is a literal value, such as 10, "Hello NYU students", or 2.71828.
  • The names of variables are also expressions.
    int length = 20;
    In the above, a literal (20) is used to initialize a variable.
A variable is a box, labeled by its name.
4.3.1 Constant expressions

We often have the idea of some constant value we want to name, but we don't want ever to be changed; for instance, pi can't change in the course of a program, so we can write:
constexpr double pi = 3.14159;
After that, we can just use pi whenever we need that value. And if we at some point need more precision, we can just add it to the constexpr and not need to roam around our program changing it in many spots.

C++ also has the idea of a const the value of which is not known at compile time, but can't be changed after it is set. So:
const c2 = n + 7;
The value of n won't be known until the code is run, but once c2 is set to n + 7, it can't be changed later on.

4.3.2 Operators

Operators serve to combine literal or variable values to create a new value. Here are the most common operators:

Operator Name Explanation
f(a) function call pass a to f as an argument
++lval pre-increment increment and use the incremented value
--lval pre-decrement decrement and use the decremented value
!a not result is bool
-a unary minus negates a
a*b multiply
a/b divide
a%b modulo (remainder) only for integer types
a+b add
a-b subtract
out<<b write b to out where out is an ostream
in>>b read b from in where in is an istream
a<b less than result is bool
a<=b less than or equal result is bool
a>b greater than result is bool
a>=b greater than or equal result is bool
a==b equal result is bool
a!=b not equal result is bool
a && b logical and result is bool
a || b logical or result is bool
lval = a assignment avoid confusion with ==
lval *= a compound assignment also works with /, + and -
4.3.3 Conversions

We can "mix" different types in expressions: what is the type of the result? There are rules for this. For instance:

  • 5/2 is 2
  • 2.5/2 means 2.5/double(2) == 1.25
  • 'a'+1 means int{'a'}+1

type(value) and type{value} mean "convert value to type. The difference between them is that the version with squiggly braces {} prevents narrowing, but the one with parentheses () does not.

Be careful not to write something like:

double dc;
cin >> dc;
double df = 9/5*dc+32;
                            

9/5 is equal to 1, not 1.8! Write 9.0/5.0 to get the result you want.

4.4 Statements

A statement is the next level of C++ language structure up from an expression. The simplest statement is just an expression followed by a semi-colon:

a=b;
++b;

When statements simply follow each other, the computer executes them in order. We typically want statements to have an effect:
3+3;
is a useless statement, since it has no effect on the state of future computations.

A common error: accidentally create an empty statement, e.g.:
if(x==5);
{ y = 3; }

The programmer meant to assign 3 to y only if x equaled 5, but the "extra" semi-colon means y is set to 3 regardless.

Code that just executes statements in order is a bit... boring. We want to be able to select what statements to execute, and excute some statements many times. Let's see how to do those things.

4.4.1 Selection

The simplest form of selection is an if statement, which selects between two alternatives; for instance, here is code that returns the maximum of two values:

int max(int a, int b)
{
    if(a<b)
        return b;
    else
        return a;
}
                            

The notion is simple: if a condition is true, do one thing, else if it is false, do another. If the class you want is available, register for it, else, choose a different class:
if(my_choice==available) choose_it();
else choose_another();

When we have many alternatives to choose among, it may be clearer to express them in a switch statement, like this:

switch (grade) {
case 'A':
    cout << "You done great!"
    break;
case 'B':
    cout << "That's pretty good."
    break;
case 'C':
    cout << "Not bad, but we hope for better."
    break;
case 'D':
    cout << "Consider retaking the course."
    break;
case 'F':
    cout << "You're going to have to retake the course."
    break;
}
                            

When many cases should result in the same behavior, then omitting the break statement can merge those cases:

                                switch (num) {
                                case '0': case '2': case '4': case '6': case '8':
                                    cout << "Digit entered was even.";
                                    break;
                                case '1': case '3': case '5': case '7': case '9':
                                    cout << "Digit entered was odd.";
                                    break;
                                default:
                                    cout << "That wasn't a digit".
                                }
                            

Switch technicalities:

  1. The value switched on must be a character, integer, or enumeration type. You can't switch on strings or other more complex objects.
  2. The values in the case labels must be constants.
  3. No two case labels can have the same value.
  4. You can use several case labels for a single case.
  5. Typical source of bugs: forgetting to use a break when you don't want to drop through to the next case. The compiler will think you meant to do 4. above.
Drill

Write a program that accepts some input from a range, like letter grades, and then uses a switch statement to reply with a message based on the input.

4.4.2 Iteration

Iteration executes the same (block) of statements repeatedly. (Hopefully, this stops at some point!) The two C++ looping constructs are:

The while statement

A while loop that prints the first 100 squares of integers:

int main()
{
    int i=0;
    while(i<100) {
         cout << i << '\t' << square(i) << '\n';
         i++;
    }
}
                            

Drill

Write a program that uses a while loop to print the ASCII value of all lowercase letters, relying on the fact that 'b' is 'a' + 1.

Blocks

Blocks in C++ are set off by { some code; }: we often call those "squiggly braces". They delimit what is done inside an if, for, while statement, or a function. They aren't needed when what is to be done is only a single statement. (See for loop below for an example.)

The for statement

When we want to loop over a sequence of numbers, C++ offers a more concise form than the while statement: the for statement:

int main()
{
    for(int i=0; i<100; ++i)
        cout << i << '\t' << square(i) << '\n';
}
                            

Drill

Write a program like the previous one, but that uses a for loop to print the ASCII value of all letters, both upper and lower.

4.5 Functions

What was square() in the code above? It is a function. A function is a named sequence of statements, that may accept one or more arguments and it may return a value. Here is a possible definition of square:

int square(int x)
{
    return x*x;
}
                        

What does all that mean? Well, the first bit says this function will return an int value to its caller. square is the name of the function, the name that can be used to call it. And int x says that the function will require and only accept a single argument, x, that must be an integer. And the function body is the block between the squiggly braces, here return x*x, that actually does the work.

4.5.1 Why bother with functions?
  • Makes the computation logically separate
  • Make the program logically clearer (by naming the computation)
  • Makes it possible to use the function in more than one place
  • Eases testing (we can test functional units separately)

Why use square() instead of a function named print_square() that both squares a number and then prints it?
Basically, we want a function to do one thing, not two, as then we can use it in more places: e.g, where we just want to square a number but then use the result in another computation without printing it.

4.5.2 Function declarations

We must differentiate between function declarations and function definitions. The declaration of a function need only announce the type it returns, its name, and the types of its arguments. The function definition must include how it carries out its work. Often in our programs, we just want to mention the declaration part of a function, so the compiler knows if we are using it wrongly, and not include the definition, which may live in some third-party library. We typically do that in header files, with the extension ".h".
A function declaration looks like:
int square(int);

4.6 vector

Programs typically need a collection of data to work on, say, to calculate the average shooting percentage of all NBA basketball players, we need a list of how many shots each player took, and how many he made. To catalogue a library, we need a list of books in it.

A vector is one of the simplest and most useful ways of storing data. It is a sequence of elements you can access by an index, like this:

We access the elements by "indexing" the vector, starting from position 0, so in the above case, v[0] is 5, v[1] is 7, and so on.

4.6.1 Traversing a vector

We can traverse a vector as follows:

vector<int> v = {5, 7, 9, 4, 6, 8};
for(int i = 0; i<v.size(); i++)
    cout << v[i] << '\n';  
                            

To traverse a vector we need to traverse the half-open sequence v[0] to v[v.size()-1].

C++ has a built-in way to loop over everything in a half-open sequence:

vector<int> v = {5, 7, 9, 4, 6, 8};
for(int x : v)
    cout << x << '\n';  
                            

This is called a range-for-loop, since range is a synonym for "a sequence of elements."
More complicated loops involving vectors are tyoically better coded in the traditional for-loop style listed above.

4.6.2 Growing a vector

We grow a vector by using its push_back() method. For instance, this code:

vector<double> v; // empty vector! 
v.push_back(2.7);
v.push_back(5.6);
v.push_back(7.9);

                            

Results in:

push_back() is a member function of the class vector.

Drill

Write a program that uses a while loop to accept a series of integers from the user, adds them as new elements to a vector, and then, once the user ends input, prints out the vector with a for loop.

4.6.3 A numeric example

To illustrate a somewhat realistic example of growing a vector, we're going to read in a series of values and calculate their mean.

#include "std_lib_facilities.h"

int main()
{
    cout << "Enter recent temperatures and we will calculate their average:\n";

    vector<double> temps;
    for(double temp; cin>>temp; )
        temps.push_back(temp);
    double total = 0.0;
    for(double temp : temps)
        total += temp;
    double mean = total / temps.size();
    cout<<"Your mean temperature for the last "<<temps.size()<<" days was "<<mean<<'\n';
    keep_window_open();
    return 0;
}
                            

Drill

Modify the above program, using the sort() facility to also get the median temperature.

4.6.4 A text example: Drill

Write a program that accepts a series of words as input and writes out a concordance, a list of all the words in the text, in alphabetical order, along with how many times each word occurred.
Hint: Use the sort function provided in std_lib_facilities.h to do this.

Drill

Modify the mean temperature program to produce a concordance of words, listing each word in a text in alphabetical order, along with the number of times it occurred in the text. (Hint: You will find sort() useful here as well.)

4.7 Language features

We were able to do a lot using a few fundamental language features: if, while, for, cout, cin, and a few functions and variables. That's the idea!

Test Yourself!
  1. Which of these operators can be used on integers but not floating point numbers?
    1. /
    2. +
    3. %
    4. -
    5. *
  2. Which of the following operators requires an lvalue?
    1. +=
    2. %
    3. +
    4. /
  3. Which of the following operations can be used on an int but not a string?
    1. +
    2. /
    3. +=
  4. The first part of the header of a for loop...
    1. is done each time around the loop.
    2. initializes the loop variable.
    3. determines when the loop terminates.
  5. We should prefer a switch statement to if and else statements when...
    1. we only have two options to consider.
    2. there are many cases to consider.
    3. the conditions for the branches are string comparisons.
  6. What is the index of the third element of a vector?
    1. 4
    2. 2
    3. 3
    4. can't say
  7. If a function is declared as int f(double x); that means...
    1. it doubles the value of its argument x and then converts it to an int.
    2. the name of the function is int and it applies the operator f to a double.
    3. it returns an int and accepts a double as an argument.
Answers

1. c; 2. a; 3. b; 4. b; 5. b; 6. b; 7. c;

Drill