I am a mathematician who never recovered from the demise of Pascal. This elegant and easy-to-learn programming language won the popularity award at least within the academic community during the 70's and 80's. Together with many colleagues, I used Pascal to create useful programs for a variety of undergraduate mathematics courses, ranging from calculus through number theory to chaos. But although it was well structured, Pascal was not object-oriented and also was never intended to be an industrial strength programming language. Thus it has been superseded as the principal language in both academia and industry by the ungainly but more modern C++. Although I have tried half-heartedly to learn C++ several times, my will and patience always failed, and I never made the transition to this current language standard.
Another development in the last fifteen years has been the ready availability of good mathematical software such as Mathematica, Maple, and MATLAB. These packages are quite powerful in the hands of experts and can do some things very easily (graphing functions, symbolic manipulation, and matrix operations), but I have never found it easy to remember how to implement basic programming structures and algorithms with them. Thus, although some may argue there is much less need for a mathematician to learn to program in a general purpose language now, I have missed the ease and degree of control that Pascal once allowed me.
For a mathematician like myself, Scheinerman’s new book is ideal. It concentrates on the portion of C++ that will be most useful to a mathematician. While developing the necessary tools and syntax of C++, the book presents example programs relevant to interesting and somewhat sophisticated mathematical problems. The reader can proceed as far as he/she wants. Even just reading the first few chapters of the book and writing some programs using the constructs introduced there is sufficient for many purposes within undergraduate mathematics. I will illustrate the interest and utility of this approach by discussing the first extended example in this book, which is utilized to illustrate the basics of loops, auxiliary procedures, and arrays. This is a sequence of programs designed to gather data relevant to the mathematical question of determining the probability that two randomly selected natural numbers are relatively prime. First solved by Dirichlet in 1849, this classic problem marks the beginning of probabilistic number theory.
The most naive approach to estimating this probability is to survey all pairs of integers less than a top value n and then to compute the proportion of pairs which are relatively prime. We are then interested in the behavior of this proportion as n gets large. A simple program to perform this calculation can be built using a nested loop construction with the Euclidean algorithm employed to calculate the greatest common divisor of a candidate pair. On a current PC this program runs quickly if n no greater than a few thousand, but since the loop requires O(n2 log n) operations, this program is not suitable for n of size 1 million. The version given in the book also illustrates the idea of a separately compiled procedure to implement the Euclidean algorithm.
To study the proportion for larger n, the book explores the Monte Carlo idea of examining a set of m randomly chosen pairs with both entries less than n, rather than all of the n2 pairs. Using the Central Limit Theorem, it is easy to show that a 95% confidence integral for the true proportion has width .0001 if m is of size 1 million. Since the complexity of this algorithm is O(m) for fixed n, running it with m of size 1 million is quite practical. Of course, this algorithm is computing a probabilistic approximation of the desired deterministic quantity, an idea which leads to a discussion of pseudo-random number generation.
If we are willing to use more mathematics, it is possible to write a program to determine the exact proportion for n equal to 1 million. The proportion can be expressed in terms of the Euler totient function, hence if this function can be calculated rapidly, so can the proportion. This circle of ideas leads to a discussion of computational approaches to the sieve of Erathosthenes and factoring. The book presents a nice example program which uses a sieve to find all primes less than n and then computes φ(k) for all k less than n using the primes as candidate divisors of k. This program uses an array to hold the primes and, at least on my laptop running Windows, needs dynamic memory allocation to cope with the large size of the array. The complexity turns out to be O(n2/ log n) and the program does run for n of size 1 million in a few minutes. In passing, let me observe that the log n factor in the complexity makes a real difference here (as it usually does not). This version of the program can cope with n = 1 million, while the original naive version cannot, and the only difference in the complexities is the placement of the factor log n.
One consequence of considering such sophisticated examples early in the book is that better structures are sometimes not available when they would be useful. The sophisticated program just discussed used an array, which is not a very common C++ structure. In this language the array structure has largely been supplanted by the vector structure, which is fully a C++ object and can be passed either by value or by reference. A large array can be awkward in a way that a vector is not, since it requires either static allocation of main memory before compilation or dynamic memory allocation at runtime. This book does discuss the use of vectors for creating a big list of primes but not until after the conclusion of the substantial example under discussion.
The data obtained from these programs provides numerical evidence for the convergence as n grows of these proportions to a value of about 0.607927. To arrive at a conjecture for the significance of this value, Scheinerman suggests checking the sequence of digits in Sloane’s On-Line Encyclopedia of Integer Sequences. It reports a match with the initial digits of 6/ π 2, the reciprocal of the sum of Euler’s famous series for ∑ 1/k2. He then concludes this extended example by sketching the classical argument that the exact value of this probability is 6/π 2.
The strength of this book is the intermingling of interesting mathematics with the ideas and syntax of the C++ language. The examples, drown mostly from discrete mathematics, are very attractive to a mathematician and provide motivation to learn the syntax. In addition to the most basic structures of C++, the book explains and uses objects, classes, and packages. There are separate chapters devoted to structures and examples pertinent to Pythagorean triples, modular arithmetic, the projective plane, permutations, and polynomials. The book includes an appendix, which offers a brief C++ reference guide, and a CD containing all of the example programs. I think that the book is most useful as a self-teaching text for a reader who knows a reasonable amount of mathematics and has had some experience is programming before. The discussions of C++ issues are (thankfully!) brief and are intended for somewhat experienced readers. However, it would be possible for a knowledgeable instructor to use this book as text for a course devoted to C++ programming for a mathematical audience.
The writing is very fluent and does not bog down in endless detail as so many programming books do. Of course, the book does not pretend to be a full text for the C++ language, a choice which makes this brevity possible. Occasionally there is some sloppiness in exposition or in code. An example of the former is the sketch of the proof that two natural numbers are relatively prime with probability 6/π2 on page 87. It is asserted that given two numbers a and b, the probability that neither has a factor of p is (1 – 1/p2), when what is meant is that this is the probability that at least one fails to have a factor of p. An example of the latter is some inconsistency with the increment operator. The Monte Carlo program mentioned above uses both the var++ and ++var versions of this operator, which have slightly different effects. When I showed this example to a computer scientist, he was appalled. In his opinion it is never a good appropriate to use the var++ version, and certainly never a good idea to use both versions in the same program.
In summary, I recommend this book highly to frustrated mathematicians wishing to learn C++ programming. You will really enjoy the well chosen examples and the light touch in the exposition.
Jeffrey Nunemacher is Professor of Mathematics at Ohio Wesleyan University in Delaware, Ohio.
List of Programs
List of Figures
What is C++?
The Integer Types
The Real Number Types
The bool and char Types
Checking the Size and Capacity of the Different Types
Comparisons and Boolean Operations
Greatest Common Divisor
A First Approach
Looping With for, while, and do
An Exhaustive Approach to the GCD Problem
Extended GCD, Call by Reference, and Overloading
Pseudo Random Number Generation
Uniform Random Values
More on Pseudo Random Number Generation
A Monte Carlo Program for the GCD Problem
Normal Random Values
A Procedure to Factor Integers
A Procedure to Calculate Euler's Totient
The Sieve of Eratosthenes
A Faster Totient
Computing pn for Large n
Points in the Plane
Data and Methods
Declaring the Point Class
Assignment and Conversion
Procedures using Arguments of Type Point
Generating Pythagorean Triples
Designing a Primitive Pythagorean Triple Class
Implementation of the PTriple Class
Finding and Sorting the Triples
Adjustable Arrays Via the Vector Class
Lists, Stacks, and Assorted Queues
Designing the Mod Type
The Default Modulus: Static Class Variables and Methods
Constructors and Get/Set Methods
Writing Mod Objects to Output Streams
A Main to Demonstrate the Mod Class
The Projective Plane
Introduction to the Projective Plane, RP2
Designing the Classes PPoint and PLine
Protected Class Members
Class and File Organization for PPoint and PLine
The Parent Class PObject
The Classes PPoint and PLine
Discovering and Repairing a Bug
Designing the Permutation Class
Finding Monotone Subsequences
The Polynomial Class Template
The GCD Problem Revisited
Working in Binary
Using Other Packages
Arbitrary Precision Arithmetic: the GMP Package
Strings, Input/Output, and Visualization
The String Class
Command Line Arguments
Reading and Writing Data in Files
A Class to Parse Files
Odds and Ends
The switch Statement
Labels and the goto Statement
Other Ways to Create Types
A. Your C++ Computing Environment
Programming with a Command Window and a Text Editor
Programming with an Integrated Development Environment
General Advice on Debugging
B. Documentation with Doxygen
C. C++ Reference
Variables and Types