Dec 98 Online
Volume Number: 14
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.
Algorithms in General
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++/
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
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
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
Linear Algebra and Matrix Manipulation
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
(Pseudo) Random Numbers
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
Cryptography
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
http://www.mactech.com/online/.