TweetFollow Us on Twitter

Dec 98 Online

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.

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++/
{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

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

Parsing

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 www.mactech.com/online/.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

PushPal 3.0 - Mirror Android notificatio...
PushPal is a client for Pushbullet, which automatically shows you all of your phone's notifications right on your computer. This means you can see who's calling or read text messages even if your... Read more
Logic Pro X 10.1.1 - Music creation and...
Apple Logic Pro X is the most advanced version of Logic ever. Sophisticated new tools for professional songwriting, editing, and mixing are built around a modern interface that's designed to get... Read more
VLC Media Player 2.2.0 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Sound Studio 4.7.8 - Robust audio record...
Sound Studio lets you easily record and professionally edit audio on your Mac. Easily rip vinyls and digitize cassette tapes, or record lectures and voice memos. Prepare for live shows with live... Read more
LibreOffice 4.4.1.2 - Free, open-source...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
Freeway Pro 7.0.3 - Drag-and-drop Web de...
Freeway Pro lets you build websites with speed and precision... without writing a line of code! With its user-oriented drag-and-drop interface, Freeway Pro helps you piece together the website of... Read more
Cloud 3.3.0 - File sharing from your men...
Cloud is simple file sharing for the Mac. Drag a file from your Mac to the CloudApp icon in the menubar and we take care of the rest. A link to the file will automatically be copied to your clipboard... Read more
Cyberduck 4.6.5 - FTP and SFTP browser....
Cyberduck is a robust FTP/FTP-TLS/SFTP browser for the Mac whose lack of visual clutter and cleverly intuitive features make it easy to use. Support for external editors and system technologies such... Read more
Firefox 36.0 - Fast, safe Web browser. (...
Firefox for Mac offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals and... Read more
Thunderbird 31.5.0 - Email client from M...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more

Get The Whole Story – Lone Wolf Complete...
Get The Whole Story – Lone Wolf Complete is Now Available and On Sale Posted by Jessica Fisher on February 27th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Who Wore it Best? The Counting Dead vs....
Like it or not, the “clicker” genre, popularized by cute distractions like Candy Box and Cookie Clicker, seems like it’s here to stay. So Who Wore it Best? takes a look at two recent examples: The Counting Dead and AdVenture Capitalist. | Read more »
Card Crawl, the Mini Deck Building Game,...
Card Crawl, the Mini Deck Building Game, is Coming Soon Posted by Jessica Fisher on February 27th, 2015 [ permalink ] Tinytouchtales and Mexer have announced their new game, | Read more »
Witness an all new puzzle mechanic in Bl...
Well, BlastBall MAX is not one of those games and is bucking trends such as timers, elements of randomness, and tacked-on mechanics in favor of pure puzzle gameplay. When you first boot up the game you’ll see a grid made up of squares that are each... | Read more »
This Princess Has a Dragon and She isn’t...
This Princess Has a Dragon and She isn’t Afraid to Useit. | Read more »
Mecha Showdown Review
Mecha Showdown Review By Lee Hamlet on February 27th, 2015 Our Rating: :: IN A SPINUniversal App - Designed for iPhone and iPad Mecha Showdown replaces traditional buttons with a slot machine mechanic in this robot fighting game,... | Read more »
Reliance Games and Dreamworks Unveil Rea...
Reliance Games and Dreamworks Unveil Real Steel Champions Posted by Ellis Spice on February 27th, 2015 [ permalink ] Reliance Games and Dreamworks have announced that a third game in | Read more »
Sum Idea Review
Sum Idea Review By Jennifer Allen on February 27th, 2015 Our Rating: :: TAXING NUMBERSUniversal App - Designed for iPhone and iPad Sum Idea is a fairly charming but taxing puzzle game.   | Read more »
A New Badland Update Brings Daydream Lev...
A New Badland Update Brings Daydream Levels to Co-Op Posted by Ellis Spice on February 27th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Slashing Demons Review
Slashing Demons Review By Lee Hamlet on February 27th, 2015 Our Rating: :: IT'S A LONG WAY TO THE TOPUniversal App - Designed for iPhone and iPad Slashing Demons lacks the depth or scope to take it beyond the point of being just... | Read more »

Price Scanner via MacPrices.net

Apple Launches Free Web-Based Pages and Other...
Apple’s new Web-only access to iWork productivity apps is a free level of iCloud service available to anyone, including people who don’t own or use Apple devices. The service includes access to Apple... Read more
Survey Reveals Solid State Disk (SSD) Technol...
In a recent SSD technology use survey, Kroll Ontrack, a firm specializing in data recovery, found that while nearly 90 percent of respondents leverage the performance and reliability benefits of SSD... Read more
Save up to $600 with Apple refurbished Mac Pr...
The Apple Store is offering Apple Certified Refurbished Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Updated Mac Price Trackers
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers: - 15″ MacBook Pros - 13″ MacBook... Read more
Apple CEO Tim Cook to Deliver 2015 George Was...
Apple CEO Tim Cook will deliver the George Washington University’s Commencement address to GWU grads on May 17, at which time he will also be awarded an honorary doctorate of public service from the... Read more
Apple restocks refurbished Mac minis for up t...
The Apple Store has restocked Apple Certified Refurbished 2014 Mac minis, with models available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz... Read more
Save up to $50 on iPad Air 2s, NY tax only, f...
 B&H Photo has iPad Air 2s on sale for $50 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $469.99 $30 off - 64GB iPad Air 2 WiFi: $549 $50 off - 128GB iPad Air 2... Read more
16GB iPad Air 2 on sale for $447, save $52
Walmart has the 16GB iPad Air 2 WiFi on sale for $446.99 on their online store for a limited time. Choose free shipping or free local store pickup (if available). Sale price for online orders only,... Read more
iMacs on sale for up to $205 off MSRP
B&H Photo has 21″ and 27″ iMacs on sale for up to $205 off MSRP including free shipping plus NY sales tax only: - 21″ 1.4GHz iMac: $1029 $70 off - 21″ 2.7GHz iMac: $1199 $100 off - 21″ 2.9GHz... Read more
Apple Takes 89 Percent Share of Global Smartp...
According to the latest research from Strategy Analytics, global smartphone operating profit reached US$21 billion in Q4 2014. The Android operating system captured a record-low 11 percent global... Read more

Jobs Board

Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
Event Director, *Apple* Retail Marketing -...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global engagement strategy and team. Delivering an overarching brand Read more
*Apple* Pay - Site Reliability Engineer - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.