C++ For Mathematicians (2006) [eng]

xx	C++ for Mathematicians

ronments (Windows, UNIX, Macintosh).

What can my computer do for me?

Although the utility of computers in the sciences and engineering is unquestionable, it is not as clear that a computer is useful for mathematics. However, there are several arenas in which a computer can be a mathematician’s best friend.

•Symbolic computation. Mathematical work often requires us to fuss with formidable formulas and solve elaborate equations. Computer algebra systems such as Maple and Mathematica are extremely useful for such work.

•Visualization. The computer can draw precise pictures and diagrams; often these images provide key insights to understanding problems.

•Examples and counterexamples. The computer can run through millions of examples and try myriad possibilities. It is a laboratory in which to perform experiments to see if ideas work and for discovering patterns.

•Contribution to proof. Sometimes, parts of proofs can be relegated to the computer for checking. A celebrated example of this is the 1970s-era proof of the Four Color Theorem by Appel and Haken. More recently, Tom Hales’s announced proof of the Kepler Conjecture required extensive computation.

I have used the computer in all these ways in my research. Allow me to share an amusing anecdote in which the computer contributed to the proof of a theorem. I was working with two colleagues on a problem in discrete mathematics. We knew that we could complete one portion of the proof if we could find a graph with certain specific properties. We carefully wrote down these criteria on a blackboard and set out to find the elusive graph. Although we tried to create the required graph by hand, each example we tried took us several minutes to check. We realized that the criteria could be checked mechanically and so we wrote a program to generate graphs at random until one with the needed properties was found. The first time we ran the program, it asked us for the number of vertices. Because we were unsuccessful with small examples, we typed in 50. Nearly instantly we were rewarded when the computer printed out a few screenfuls of data specifying the graph.

Heartened by this (but not wanting to tangle with such a large graph), we ran the program again asking for a graph with only 20 vertices. Again, we were greeted with near instant success. We started to draw the graph on the blackboard, but it was a nasty random mess (no surprise—our program was designed to examine random graphs one after another). One more run. Shall we be optimistic? Certain this would not work, we ran the program again for graphs on 5 vertices. Success! The graph was actually quite simple and we had a good laugh over how we found our answer.

Preface

xxi

Using this book

This book is ideal either for self-study or as a text for a semester-long course in computer programming (with an emphasis on mathematics). It is important that undergraduate mathematics majors know how to use the computer effectively. This is a skill that will serve them well whether for applied scientific/engineering/financial work, or as a means for forming and testing conjectures in pure research.

We explain how to use C++ from the ground up, however, some experience in writing programs in any language will help. The reader does not need extensive experience in programming. Nor is a deep mathematical background needed to read this book. Our examples are drawn from standard mathematical topics such as Pythagorean triples [integers (a,b,c) such that a2 + b2 = c2] and polynomials.

Whether you are reading this book on your own or in conjunction with a course, the most effective way to learn is to do. Every chapter ends with a collection of exercises; do them all. This is important for two reasons. First and foremost, mastery of any skill requires practice, and learning C++ is no exception. Second, additional ideas and subtle points are explored in the exercises. To assist you, we include complete solutions to nearly every exercise in Appendix D.

Organization

We organize our discussion around mathematical themes. For example, Chapters 3 to 5 cover many central ideas in C++ (from how to write procedures to dynamic allocation of arrays), but a single mathematical problem runs throughout, taking us from Euclid to Riemann.

The main body of the book is divided into three parts: Procedures, Objects, and

Topics.

Procedures focuses on writing C++ procedures (often called functions by our computer science colleagues, but we have a different meaning for that word). Objects introduces the object-oriented method of programming. If you want to solve a problem that involves permutations, Chapter 11 shows how C++ can handle these structures nearly as comfortably as it handles integers. Topics discusses how to use freely available packages that you can use in your programs, more advanced input/output, visualization, and selected special features of the C++ language.

Four appendices provide (A) an overview of computing systems (including Integrated Development Environments), (B) the use of the Doxygen documentation system, (C) a quick reference to the C++ language and supporting libraries, and

(D) answers to nearly every exercise.

No pointers! (almost)

The C++ concepts covered in this book are not exhaustive. There are aspects of the language that are relevant only to computer scientists and software engineers. For example, C++ provides a number of exotic casting operators (such as reinterpret_cast) that are not of interest to mathematicians; we omit those. Nei-

xxii	C++ for Mathematicians

ther multiple inheritance nor pure virtual functions are for us. We do not explain how to make C++ programs work with other languages such as assembly language. We don’t create our own namespaces. For these and other C++ topics that are useful to large software engineering projects, please refer to any of several excellent, comprehensive C++ reference books.

One topic that we touch only gently is the use of pointers. Mostly, we do not need them. We successfully avoid this confusing (and errorprone) concept through the use of call-by-reference and STL container classes. A mathematician shouldn’t be worrying about exotic data structures such as red–black trees; we just want to insert and delete elements in a set and not to worry about how the computer manages the set.

There are, however, a few instances where a rudimentary understanding of pointers is necessary.

•The name of a C++ array is a pointer to its first element. We need to understand this when we pass an array to a procedure and when we dynamically allocate storage for an array.

•Sometimes an object needs to refer to itself (e.g., when a method such as operator+= returns the value of the object). In these instances, the this pointer is useful.

We do not provide an extensive discussion of string processing (but do cover the basics in Chapter 14). As mathematicians, we are interested in getting data into our programs and results out of them; we are not going to construct word processors.

We omit the exotic and focus on those aspects that make C++ a formidable weapon in the mathematician’s arsenal. With your brain and this book, your problem doesn’t stand a chance. Enjoy!

Additional resources

The CD-ROM that comes with this book includes the code for all the numbered programs (see the List of Programs on page xiii). The programs are free for you to use under the terms of the GNU General Purpose License. (See the CD-ROM for details.) The disk also includes solutions to some of the lengthier exercises.

Please visit the Web site for this book www.ams.jhu.edu/˜ers/cpp4m/ where we maintain a list of errata and submissions for Exercise 1.1.5.

Acknowledgments

Many thanks to my editor Sunil Nair and his helpful staff at Taylor & Francis/CRC Press. They helped with everything from LATEX issues to copy editing to securing permissions.

Promit Roy is an undergraduate computer science major at Johns Hopkins University. He read through the entire manuscript checking for accuracy and compatibility

Preface

xxiii

with Microsoft Visual Studio. In addition, he prepared the MS Visual Studio project files for the accompanying CD-ROM. Thank you, Promit!

At various points in this book I recommend that the reader consult a “friendly computer science colleague.” I am fortunate to have such a colleague. Thank you, Joanne Houlahan for your help (and patience) with getting me unstuck from computer woes.

I greatly appreciate my department chair, Daniel Naiman, for his support and encouragement for this project.

It gives me great joy to acknowledge the contributions of my father, Ira, and my son Jonah to the front cover. Grandpa took the cover photo and grandson provided the design concept.

Most important, thank you to my wife, Amy, and our children, Jonah, Naomi, Danny, and Rachel, for the world of love and happiness I share with them.

Ed Scheinerman

Baltimore

May 24, 2006

Part I

Procedures

Chapter 1

The Basics

1.1What is C++?

C++ is a computer programming language.

Computers are electronic information-processing machines. Data and programs in these machines are saved, moved, and transformed in the form of electrical voltages. These electrical voltages can be interpreted as a zeros and ones. The zeros and ones can be aggregated and interpreted as words, numbers, images, sounds, and so on. Long ago, information—be it data or programs—could be entered into the

Figure 1.1: A PDP-8 computer with front panel switches for entering instructions and data. (Image courtesy of the Computer Museum at the University of Stuttgart. Photograph by Klemens Krause.)

3

4	C++ for Mathematicians

computer by manipulating switches on the front of the machine. Today, there are better methods. Computer programming languages convert text into the requisite binary instructions.

C++ is a compiled language. This means that before the program is run, it is first translated into a form that the machine can use directly. The C++ files (and a typical project contains several) are called the source files. You create the source files by typing them using a program called a text editor.

The translation of the source files into a program proceeds in two phases. First, the individual source files are translated by a program called the compiler into socalled object files. Next, a second program, called a linker (or loader) combines the individual object files into an executable file, that is, a program you can execute (run).

The precise manner in which is all this is done (source file creation/editing, compiling, linking, and execution) varies among different computing platforms. In Appendix A we discuss how this is done for some common computing platforms (Windows, Macintosh, UNIX).

Ideally, you have already done some programming, say in C, and so you are familiar with the general flow of this process. If not, your best option is to have someone show you how to perform these basic steps. In theory, your computer contains documentation that explains all this. However, such documentation is most useful to someone who already knows what to do, but needs reminders on specifics.

With the help of Appendix A, a friendly neighbor knowledgeable in programming, and documentation (if any) you will get past this first, often frustrating hurdle. Rest assured that the process is simple once you know what it is. The hard part is knowing just which menu to select or what command to type to set the process in motion. For example, on many computers you translate your C++ files into a working program with the single command:

g++ *.cc

and then run your program by typing this:

./a.out

If you are using an integrated development environment (also called an IDE) compiling your C++ files may be as simple as clicking on a button that says “build” and then running your program by clicking on a button that says “run”.

1.2Hello C++

To begin we need to write a program; it’s time to present our first example. It is traditional to start with a program that does nothing more than type the words Hello, world onto the computer screen. Instead, we opt for a bit of (bad) poetry.

The Basics

5

Program 1.1: The classic “Hello, world” program updated for the mathematics world.

1 #include <iostream>

2using namespace std;

3

4/**

5* A simple program for demonstrating the basics of a C++ project.

6*

7* It does a good job of demonstrating C++ fundamentals, but a

8* terrible job with the poetry.

9 */

10

11int main() {

12cout << "Don’t you just feel like a louse";

13cout << endl;

14

15cout << "To learn that your \"new\" theorem was proved by Gauss?";

16cout << endl;

17

18return 0;

19}

There are naming conventions for C++ program files. The name of the file that contains this code is poem.cc. The name has two parts: poem is called the base name and .cc is called the extension. The base name can be more or less anything you like, but the extension should be .cc. Other extensions that are permissible for C++ programs are .C, .cpp, and .cxx. The extension is important because this is what the compiler uses to recognize that your file contains C++ code.

Let’s analyze poem.cc to understand the purpose of its various parts.

The core of this program is in lines 12–16, so we begin our discussion there. Line 12 contains four important components.

•The cout object: This is an object to which we send information that we want written on the computer screen. The word cout is an abbreviation of “console output.”

•The << operation: This is an operation that acts on the objects immediately to its left and right: in this case, the cout object on its left and the character array (described next) on its right.

•The character array enclosed in quotation marks: These are the words Don’t you just feel like a louse. The quotation marks mark the beginning and end of the character array. Note that the single quote (apostrophe) is a valid character.

•The statement terminator: The semicolon at the end of the line denotes the end of the statement.