Volume Number: 14 (1998)
Issue Number: 12
Column Tag: MacTech Online

Advanced C++ Algorithms

by Jeff Clites, online@mactech.com

Algorithms are at the very heart of programming. Fortunately, the C++ standards committee saw fit to include an algorithms library to work in conjunction with the container classes of the STL. Although immensely useful, this library really covers only the most commonly used, general purpose tasks, and for specialized applications you have to look elsewhere. This month we are going to take a tour of some powerful algorithm libraries that pick up where the STL leaves off.

There are a number of printed references for learning about algorithms and the theory behind them. Algorithms in C++, 3rd ed., by Robert Sedgewick, is a new version of a classic reference, full of lucid explanations and copious illustrations, and there is a freeware program, MacBalsa, which animates many of the algorithms from the book. The Art of Computer Programming series by Donald E. Knuth is the definitive work on almost all things computing, and it is referenced by just about any writing which mentions the word "algorithm." Numerical Recipes in C by William H. Press, et al, is another classic, with an emphasis on practicality, and the full text is available in pdf form for preview on the web. On the other hand, a page at JPL warns against using the code from Numerical Recipes as-is, so you might want to check out these sites in tandem. For your general algorithm needs, check out Netlib, Codepage, and Programmer's Oasis - they have descriptions and links to a plethora of code sources.

MacBALSA

http://www.eg.bucknell.edu/~zaccone/MacBALSA/MacBALSA.html

Don Knuth's Home Page

http://www-cs-staff.stanford.edu/~knuth/

Numerical Recipes Home Page

http://www.nr.com/

Why not use Numerical Recipes?

http://math.jpl.nasa.gov/nr/

Netlib

http://www.netlib.org/c++/

{Codepage 2.2}

http://www.iro.umontreal.ca/~ratib/code/

Programmer's Oasis: Algorithms, Data Structures

http://www.utu.fi/~sisasa/oasis/oasis-algo.html

Finite-State Machines (or FSMs for short) are based on a mechanical model of computing, originating with the Turing Machine. Although conceptually simple, they are the natural way to express many computational processes, such as string searching or parsing. Object Mentor has code available for an FSM compiler, which allows you to define an FSM with a simple notation and then compile it into code for a set of C++ classes. (Also be sure to check out the cool "Game of Life" applet, Wator, on their home page.) Conveniently, Michael Schürig has done the work of preparing a Mac version of the compiler as a droplet, and it is posted on his web site.

Object Mentor Freeware by Email

http://www.oma.com/Offerings/catalog.html

Michael Schürig's Home Page

http://www.schuerig.de/michael/

Genetic algorithms are a class of algorithms for solving minimization or best-fit problems, and are especially useful for situations in which classic optimization techniques fail. They are so-named because their basic strategy mimics biology: to find the optimal solution, generate a pool of candidate solutions, take a selection of the best ones and "combine" these to generate a new pool of candidates, and repeat. Unlike other optimization techniques, their successful use often depends heavily on finding the right way to encode the problem, but if used correctly they can succeed despite the presence of local minima which plague other approaches. MIT's GAlib makes it easy to implement a variety of different genetic algorithm strategies, and TimGA is a program which graphically demonstrates the optimization process and lets you experiment with how various parameters effect performance. TimGA is PowerPlant-based, and the code is available online.

GAlib: Matthew's C++ Genetic Algorithms Library

http://lancet.mit.edu/ga/

TimGA Source Code

http://hyperarchive.lcs.mit.edu/cgi-bin/NewSearch?key=TimGA

A surprisingly difficult task in compiled languages is to allow the user to input a mathematical expression in text form and then evaluate it. This is a trivial one-liner in interpreted languages such as Perl, Python, and Tcl, but C and C++ don't have access to their own parsers and compilers at runtime, so if you want to do this sort of thing you have to write an interpreter yourself. A helpful starting point is the Chipmunk Basic Home Page, which has a large collection of links to source code. In particular, check out interp2num, an expression evaluator which gives you a choice of allowing C-like or BASIC-like syntax for the expressions it evaluates. Also, the STL-Compliant Software Components Collection page has a tokenizer which can help if you want to start from scratch.

Chipmunk Basic Home Page

http://www.rahul.net/rhn/cbas.page.html

STL-Compliant Software Components Collection

http://corp.metabyte.com/~fbp/stl/components.html

Fortran is famous for high-performance computation, and there a number of well-known libraries for numerical and scientific applications. Although many of these may be available to C and C++ programmers as compiled libraries or by way of the Fortran-to-C compiler, you probably prefer to find true C++ implementations. These allow you to peek under the hood when necessary, and they make it easier to integrate with the rest of your application by providing an object-based interface.

Most of these libraries fall under the general heading of linear algebra, since many problems are naturally expressed in terms of matrices. NIST has developed a library called TNT, the Template Numerical Toolkit, which tackles the difficult problem of developing an efficient yet elegant library for matrix math. One of its design criteria is compatibility with the STL, so that its matrices can act as generic container classes. Oleg Kiselyov's library, called simply LinAlg, is worth a look as well. Even if you do not use it directly, it uses a number of clever programming techniques, such as lazy evaluation and specialized constructors, which are instructive in their own right. Finally, Newmat, by Robert Davies, is a large and well-documented library, and is suitable for working with larger matrices.

Mac F2C

http://www.alumni.caltech.edu/~igormt/Mac_F2C.html

TNT Home Page

http://math.nist.gov/tnt/

Oleg Kiselyov's LinAlg Library

http://hyperarchive.lcs.mit.edu/cgi-bin/NewSearch?key=LinAlg

Newmat09: C++ matrix library

http://webnz.com/robert/nzc_nm09.html

It's pretty common for programs to use random number generators, and some are more serious about it than others. (Are you designing a solitaire game or trying to predict tornadoes?) If you need something a little more random than rand() or QuickDraw's Random(), there are alternatives out there. It's ironic, if you think about it, that the better implementations call themselves pseudorandom rather than random, to explicitly acknowledge that you can't really generate truly random numbers on a computer without some extra hardware making quantum measurements. UltraLib is a fast random-number generator, with implementations available in 68K and PPC assembly. It claims to be random even at the bit level, and to have an extremely long period ( 10^356). Agner Fog has another implementation of the same algorithm, as well as an algorithm of his own invention, on his page. Robert Davies, mentioned above, has a random number class library, Newran, which can generate sequences following a number of distributions. Donald E. Knuth's page, also mentioned above, has a public domain random number generator, with code in C or Fortran for single or double precision.

UltraLib

http://hyperarchive.lcs.mit.edu/cgi-bin/NewSearch?key=RandomNumberLib

Agner Fog's Pseudo random number generators

http://announce.com/agner/random/

Newran02A: C++ random number generator library

http://webnz.com/robert/nr02doc.htm

Knuth: Programs

http://www-cs-staff.stanford.edu/~knuth/programs.html

I could certainly write an entire column (or several) on the topic of cryptography, so I will just give a brief pointer here. Bruce Schneier's Applied Cryptography is the definitive reference on the subject, and his Counterpane web site has information on two freely available encryption schemes which he invented, as well as a pseudorandom number generator.

Counterpane Homepage

http://www.counterpane.com/

None of these libraries are Mac-specific; some are fully cross-platform, some have Mac versions available, and some may require tweaking (although less tweaking, now that CodeWarrior has support for member templates). In any case, I hope they are useful starting points.

These and armfuls of other links are available from the MacTech Online web pages at www.mactech.com/online/.