C++ For Mathematicians (2006) [eng]

26	C++ for Mathematicians

program does. (The extra * on line 1 is a signal to Doxygen that this is a comment it should read.)

•Lines 7, 8, and 23 are a safeguard against accidental double inclusion. It is easy to #include header files more than once. How can this happen? Some day you might create a header file for handling Mobius¨ transformations, that is, functions of a complex variable of the form f (z) = (az + b)/(cz + d). In your header file mobius.h you need to define various quantities as complex, so you start with the directive #include "complexx.h" to be sure that C and i are defined before you get started.

Now in the main program you might write this:

#include "complexx.h" #include "mobius.h"

Without the double-inclusion safeguards, this would cause the two statements typedef complex<double> C; and const C i = C(0.,1.); to be inserted twice into your program. The compiler would then complain about this and refuse to compile your program.

There are two solutions to this problem. A bad solution is to require you to remember which of your various header files already includes which other and make the programmer (you) responsible for avoiding double inclusion.

The better solution is to build in a mechanism in the header file that prevents double inclusion. Here is how this mechanism works.

Line 7 begins with the directive #ifndef. This is not a C++ statement, but rather an instruction to the preprocessor; it stands for “if not defined.” If what is not defined? If the symbol COMPLEXX_H is not defined, then we should do what follows up to the matching #endif on line 24 (at the end of the file).

If the symbol COMPLEXX_H is not yet defined, we include everything in the file. But if the symbol COMPLEXX_H is already defined, we skip everything through to the #endif.

Suppose COMPLEXX_H is not defined (and it won’t be when we first set out), and we next come to line 8 which reads #define COMPLEXX_H. This line defines the symbol COMPLEXX_H, although it does not specify any particular value for the symbol. (We don’t care whether COMPLEXX_H has a value; we just want to know whether it is defined.)

Suppose we try to #include "complexx.h" a second time. On the first pass through complex.h, we executed the directive #define COMPLEXX_H. Thus, on this second pass, when we reencounter #ifndef COMPLEXX_H the preprocessor notes that COMPLEXX_H is defined and then skips everything in the file until the matching #endif.

•The rest of the file is easier to understand. We need to include the C++ header file complex in order to use complex<double> later. We need the statement using namespace std; so the definitions in <complex> are available.

Numbers

27

The comments before lines 16 and 21 document how C and i are defined. These comments can be processed by Doxygen.

2.8Naming variables

C++ allows you to name your variables more or less whatever you like. The name should begin with one of the 26 letters (lower or upper case). After that, it may contain letters, digits, or the underscore symbol _.

Pick short, easily remembered names for your variables. For example, if your variables are named center_x, center_y, and radius, it is instantly clear to anyone (especially yourself) what these variables hold.

There are some obvious restrictions on your choice of names. You cannot use a C++ keyword as a variable name. So you cannot name your variables if or for or long; these already have meanings in C++. It’s not worth memorizing all of C++’s keywords. If you accidentally try to name a variable with one of C++’s more obscure keywords, the compiler will complain. Unfortunately, it won’t complain in a way that you like. For example, imagine you tried to declare a long variable to be named volatile (perhaps you are working with a chemist trying to model some nasty substance) like this:

long volatile;

It turns out the volatile is a C++ keyword (one that you do not need to know about for mathematical work). What you would like is an error message from the compiler that this is an illegal variable name. Here is what the compiler on my computer says about this line:

warning: declaration does not declare anything

Not particularly helpful, but at least the compiler did complain about the offending line.

Try to develop a consistent style of variable names. I prefer to name variables beginning with lowercase letters. (Later, when we create our own types, I name these beginning with uppercase letters.) Multiword names either can use the underscore as a space (you cannot have a space or hyphen in a variable name) or use capital letters to show the start of each word. Some examples:

left_end_point rightEndPoint geometric_mean upperBound

Some people like to use all capitals for constants, for example, GOLDEN_MEAN.

Variables may be declared anywhere you like as long as they are declared before they are used.

28	C++ for Mathematicians

2.9Exercises

2.1Consider the following program.

#include <iostream> using namespace std; int main() {

float x; int y; double z; x = 3.5; y = x;

z = y;

cout << z << endl; return 0;

}

What is printed to the screen (and why)?

2.2What is the output of the following program and which (if any) of the lines gives a result equal to 403 ?

#include <iostream> using namespace std;

int main() {

cout << (4/3)*10 << endl; cout << 4*(10/3) << endl; cout << (4*10)/3 << endl; cout << (4/3)*10. << endl; cout << (4./3)*10 << endl; return 0;

}

2.3What is the output of the following program? How does C++’s % operator differ from the mathematical mod operation?

#include <iostream> using namespace std;

int main() {

cout << (-5) % 3 << endl; cout << 5 % 3 << endl;

cout << (-5) % (-3) << endl; cout << 5 % (-3) << endl; return 0;

}

2.4Explain why the expression ’3’==3 is legal C++ and what it means. What value does this expression have?

Numbers

2.5 Consider this program.

#include <iostream> using namespace std; int main() {

int a, b; a = 5;

b = 10;

cout << (a==b) << endl; cout << (a=b) << endl; cout << (a==b) << endl; return 0;

}

This program gives the following output.

0

10

1

Explain.

29

2.6Write a program to explore division by zero. Include the cases 00 and 10 . Consider the variants in which the numerator and denominator are float or int

(or one of each).

2.7What is the output of this program?

#include <iostream> using namespace std; int main() {

int a = 10; a += a;

a *= a;

cout << a << endl; return 0;

}

2.8All of the following are illegal names for variables in a C++ program. Explain what is wrong with each.

(a)2nd_coord

(b)y-val

(c)double

(d)x:y_ratio

(e)purple&orange

(f)1e-2

Chapter 3

Greatest Common Divisor

3.1The problem

For integers a and b, the greatest common divisor of a and b is the largest integer d such that d is a factor of both a and b. The greatest common divisor is denoted gcd(a,b). We say a and b are relatively prime provided gcd(a,b) = 1. In this chapter we develop many C++ concepts by studying a particular problem involving the gcd of integers.

Here is the classic problem: Let n be a positive integer. Two integers, a and b, are selected independently and uniformly from the set {1,2,...,n}. Let pn be the probability that a and b are relatively prime. Does limn→∞ pn exist and, if so, what is its value?

The computer cannot solve this problem for us, but it can help us to formulate a conjecture. We try a number of approaches including exhaustive enumeration, generating pairs of numbers at random and recording the results, and the use of Euler’s totient.

The first order of business, however, is to develop a procedure to compute the greatest common divisor of two integers.

3.2A first approach

In this section we develop a correct, but highly inefficient, procedure for calculating the greatest common divisor of two integers. Our goal is to introduce a number of C++ concepts as well as to create the gcd procedure. This procedure takes two integers and returns their greatest common divisor. Later, we replace this inefficient procedure with a much more efficient method.

Before we begin, however, we need to address a bit of terminology. Mathematicians and computer programmers use the word function differently. A mathematician’s function assigns to each value x a unique value y = f (x). Suppose we calculate, say f (8) and the result is 17. Then if we calculate f (8) a few minutes later, we are guaranteed that the result is still 17.

31

32	C++ for Mathematicians

By contrast, for a C++ programmer, it is natural that a function might return different values (even with the identical arguments) at different times! This is because C++ functions can access data beyond their arguments; for example, there is a C++ function that reports the current time. Clearly, the value of this function changes from one minute to the next.

As a mathematician, my bias is, of course, for the mathematical use of the word. Therefore, in this book, we use a different word for C++ functions; we call them procedures. This nomenclature ought not upset our computer science colleagues, but when you read other books or documentation about C++ procedures, be aware that they are likely to be called functions. (Some books may refer to methods and we introduce that terminology later.)

With issues of nomenclature behind us, we now develop a procedure to compute greatest common divisors.

We need to name the procedure. We could name it greatest_common_divisor, but there is no loss of clarity in simply naming it gcd. We want gcd to accept two arguments (inputs) of type long and return an answer that is also of type long.

The code for the gcd procedure is written in two files named gcd.h and gcd.cc. The header file, gcd.h, is used to describe the procedure (both in C++ and in English comments). The file gcd.cc contains the actual instructions for calculating the greatest common divisor.

This organization is similar to declaring versus assignment variables. The declaration announces the variable’s type and the assignment gives the variable a value. Likewise, the header file announces the type of the procedure (two long inputs and return a long) and the .cc file gives the actual instructions to be carried out.

The file gcd.cc does not have a main() procedure; the main() is found in another file. The latter file includes the directive #include "gcd.h".

The first gcd algorithm we present is terribly inefficient. When we develop a better algorithm, we replace the file gcd.cc, but the file gcd.h does not change. The file gcd.h looks like this.

Program 3.1: The header file gcd.h.

1 #ifndef GCD_H

2#define GCD_H

3

4/**

5* Calculate the greatest common divisor of two integers.

6* @param a the first integer

7* @param b the second integer

8* @return the greatest common divisor of a and b

9 */

10

11 long gcd(long a, long b);

12

13 #endif

Line 11 is the most important line of this file. The statement

Greatest Common Divisor

33

long gcd(long a, long b);

declares gcd to be a procedure. This procedure takes two input arguments (named a and b) that are both of type long. The first long on this line (to the left of gcd) is the return type of the procedure; this indicates that the procedure returns a value of type long.

Other features of this file: lines 1, 2, and 13 are the mechanism to prevent double inclusion (see the discussion on page 26). Lines 4–9 are a description of the gcd procedure. This description includes a sentence that explains what the procedure does, an explanation of the parameters passed to the procedure, and an explanation of the value returned by the procedure. The tags @param and @return are read by Doxygen to produce a nice Web page for this procedure.

We are ready to get to work on the file gcd.cc. This file has the following structure.

#include "gcd.h"

long gcd(long a, long b) {

.......

return d;

}

The definition of the gcd procedure looks nearly identical to the declaration in the header file. The semicolon on line 11 of gcd.h is replaced by an open brace. The open brace is followed by the instructions to calculate the greatest common divisor of a and b, and that value eventually ends up in a variable named d. The return d; statement causes the value in d to be the “answer” returned by this procedure.

Our strategy is to test successive integers to see if they are divisors of a and b, and keep track of the largest value that divides both.

There are a few things we need to worry about first.

•What happens if the gcd procedure is given negative values for a or b? There is nothing wrong with allowing a or b to be negative. After all,

gcd(a,b) = gcd(−a,b) = gcd(a,−b) = gcd(−a,−b).

•What happens if one (or both) of a or b is zero? If only one of these is zero, then there is no mathematical problem because gcd(a,0) = |a| provided a 6= 0.

However, gcd(0,0) is undefined. We need to decide what to do in this case. We could have the program immediately stop (this is done by the statement exit(1);). A better solution, however, is to print a warning message and return a value, say zero.

We need to revise the documentation in gcd.h to reflect this.

34	C++ for Mathematicians

Program 3.2: Revised documentation for gcd in the header file gcd.h.

4/**

5* Calculate the greatest common divisor of two integers.

6* Note: gcd(0,0) will return 0 and print an error message.

7* @param a the first integer

8* @param b the second integer

9	* @return the greatest common divisor of a and b.
10	*/
	Now we work on gcd.cc. The file begins as follows.
	Program 3.3: Beginning of the file gcd.cc.
1	#include "gcd.h"
2	#include <iostream>

3using namespace std;

4

5long gcd(long a, long b) {

6

7 // if a and b are both zero, print an error and return 0

8if ( (a==0) && (b==0) ) {

9cerr << "WARNING: gcd called with both arguments equal to zero."

10<< endl;

11return 0;

12}

We require #include <iostream> on line 2 because we may need to write an error message (in case gcd(0,0) is invoked). Line 5 starts the definition of the gcd procedure.

The first thing we check is if both arguments are equal to zero; this occurs at line 8. The general structure of an if statement is this:

if ( condition ) { statements;

}

If the condition (an expression that evaluates to a bool) is true, then the statements in the enclosing braces are executed. Otherwise (the condition is false), all the statements in the enclosing braces are skipped.

For our program, if both a and b are zero, then the condition is true and the two enclosing statements are executed. The first writes a warning message to an object named cerr. The cerr object is similar to the cout object. It would not have been a mistake to use cout here instead. However, computers provide two output streams, cout and cerr, and both write to the screen. The cout is usually used for standard output and cerr for error messages.

The second statement controlled by this if is return 0;. When this statement is executed, the procedure ends and the value 0 is returned; the rest of the program is not executed.

Next, we ensure that a and b are nonnegative.

Greatest Common Divisor

35

Program 3.4: Ensuring a and b are nonnegative in gcd.cc.

14// Make sure a and b are both nonnegative

15if (a<0) {

16a = -a;

17}

18if (b<0) {

19b = -b;

20}

The code is reasonably straightforward. If a is negative, it is replaced by -a; and likewise for b. However, there is something to worry about. Do these statement have a side effect? We are changing the arguments to the gcd procedure. Does this change the values of a and b in the procedure that called gcd?

The answer is that no change is made to any values outside the gcd procedure; there are no side effects. The reason is that when another procedure (say, main()) calls gcd, the arguments are copied to a and b. We say that C++ procedures call by value; the arguments are copies of the originals. For example, suppose the main() contains this code:

long x = -10; long y = 15;

cout << gcd(x,y) << endl;

When gcd is invoked, the computer sets a equal to −10 and b equal to 15; the values a and b are private copies of these values. Eventually gcd reaches line 16 where it replaces a with -a (i.e., sets a to 10). However, the original x in main is unaffected by this.

Next we get to the heart of the matter. We test all possible divisors from 1 to a and see which divides both a and b. There’s one slight mistake, though. If a is zero, then the answer should be b. We treat that as a special case. Here is the last part of the program.

Program 3.5: The last part of the gcd.cc program.

22// if a is zero, the answer is b

23if (a==0) {

24return b;

25}

26

27 // otherwise, we check all possibilities from 1 to a

28

29 long d; // d will hold the answer

30

31for (long t=1; t<=a; t++) {

32if ( (a%t==0) && (b%t==0) ) {

33d = t;

34}

35}

36