- Membership
- MAA Press
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

Publisher:

Chapman & Hall/CRC

Publication Date:

2006

Number of Pages:

496

Format:

Paperback with CDROM

Price:

59.95

ISBN:

158488584X

Category:

Monograph

[Reviewed by , on ]

Jeffrey Nunemacher

10/31/2007

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(*n*^{2} 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 n^{2} 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(*n*^{2}/ 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/k^{2}. 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/*p*^{2}), 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

Preface

I. PROCEDURES

The Basics

What is C++?

Hello C++

Numbers

The Integer Types

The Real Number Types

The bool and char Types

Checking the Size and Capacity of the Different Types

Standard Operations

Comparisons and Boolean Operations

Complex Numbers

Naming Variables

Greatest Common Divisor

The Problem

A First Approach

Euclid's Method

Looping With for, while, and do

An Exhaustive Approach to the GCD Problem

Extended GCD, Call by Reference, and Overloading

Random Numbers

Pseudo Random Number Generation

Uniform Random Values

More on Pseudo Random Number Generation

A Monte Carlo Program for the GCD Problem

Normal Random Values

Arrays

Euler's Totient

Array Fundamentals

A Procedure to Factor Integers

A Procedure to Calculate Euler's Totient

The Sieve of Eratosthenes

A Faster Totient

Computing pn for Large n

The Answer

II. OBJECTS

Points in the Plane

Data and Methods

Declaring the Point Class

Data Hiding

Constructors

Assignment and Conversion

Methods

Procedures using Arguments of Type Point

Operators

Pythagorean Triples

Generating Pythagorean Triples

Designing a Primitive Pythagorean Triple Class

Implementation of the PTriple Class

Finding and Sorting the Triples

Containers

Sets

Set Iterators

Multisets

Adjustable Arrays Via the Vector Class

Ordered Pairs

Maps

Lists, Stacks, and Assorted Queues

Modular Arithmetic

Designing the Mod Type

The Code

The Default Modulus: Static Class Variables and Methods

Constructors and Get/Set Methods

Comparison Operators

Arithmetic Operators

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

Inheritance

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

Pappus Revisited

Permutations

Ulam's Problem

Designing the Permutation Class

Finding Monotone Subsequences

Exercises

Polynomials

Procedure Templates

Class Templates

The Polynomial Class Template

The GCD Problem Revisited

Working in Binary

III. TOPICS

Using Other Packages

Arbitrary Precision Arithmetic: the GMP Package

Linear Algebra

Other Packages

Strings, Input/Output, and Visualization

Character Arrays

The String Class

Command Line Arguments

Reading and Writing Data in Files

String Streams

Formatting

A Class to Parse Files

Visualization

Odds and Ends

The switch Statement

Labels and the goto Statement

Exception Handling

Friends

Other Ways to Create Types

Pointers

IV. APPENDICES

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

Doxygen Comments

Using Doxygen

C. C++ Reference

Variables and Types

Operations

Control Statements

Procedures

Classes

Standard Functions

D. Answers

Index

- Log in to post comments