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

Tunnelblick 3.7.4b - GUI for OpenVPN.
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
Carbon Copy Cloner 5.0.5 - Easy-to-use b...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more
Postbox 5.0.22 - Powerful and flexible e...
Postbox is a new email application that helps you organize your work life and get stuff done. It has all the elegance and simplicity of Apple Mail, but with more power and flexibility to manage even... Read more
Ortelius 2.0.8 - Vector drawing app espe...
Ortelius is a full-featured vector drawing application especially for map design. Draw directly with features such as roads, rivers, coastlines, buildings, symbols and contours. Ortelius is known for... Read more
Bartender 3.0.32 - Organize your menu-ba...
Bartender lets you organize your menu-bar apps by hiding them, rearranging them, or moving them to Bartender's Bar. You can display the full menu bar, set options to have menu-bar items show in the... Read more
Adobe Animate CC 2018 18.0.1.115 - Anima...
Animate CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Flash Professional customer). Animate CC 2018 (was Flash CC) lets you... Read more
Adobe Lightroom Classic CC 7.1 - Import,...
Adobe Lightroom is available as part of Adobe Creative Cloud for as little as $9.99/month bundled with Photoshop CC as part of the photography package. Lightroom 6 is also available for purchase as a... Read more
ExpanDrive 6.1.8 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
ExpanDrive 6.1.8 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
DiskCatalogMaker 7.2.7 - Catalog your di...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast Finder-like intuitive look and feel Super-fast search algorithm Can compress catalog data for... Read more

Latest Forum Discussions

See All

Amazing Katamari Damacy guide - beginner...
Amazing Katamari Damacy brings the bizarro world of the original games to mobile and shifts them into an endless format that's just as addictive as the PlayStation entries. Your goal is still to roll as much random stuff as you possibly can, though... | Read more »
Portal Knights guide - crafting tips and...
In Portal Knights, you're only as strong as the items you have at your disposal. This sandbox adventure is all about crafting and building up the next big thing. Whether you're an avid explorer or collector, crafting will likely play a large part... | Read more »
The best deals on the App Store this wee...
A new week means new discounts on the App Store. This week's deals run the gamut of action-adventure titles, puzzle games, and one of the best narrative adventure series out there. If you're looking to fill out your mobile gaming library on a... | Read more »
What you need to know about Animal Cross...
We hope you've been hard at work on collecting all of those holiday items in Animal Crossing: Pocket Camp, because you're about to get a whole new list of fun things to do as the game receives its first big update sometime soon. There are a lot of... | Read more »
Reigns: Her Majesty guide - how to use e...
Ruling a kingdom isn't easy--doubly so for a queen whose every decision is questioned by the other factions seeking a slice of power. Reigns: Her Majesty builds on the original game's swipey tactics, adding items that you can use to move the story... | Read more »
The best new games we played this week -...
Friday has crept up on us once again, so it's time to honor the best new games we've played over the past few days. This past week was a pretty exciting one, with the debut of lots of beautiful new indies and some familiar faces returning to the... | Read more »
Portal Knights guide- beginner tips and...
Portal Knights is finally making the jump to iOS and Android, and it's already climbing the ranks to become the next big MMO experience on mobile. This sprawling sandbox game will let you pursue any adventure you wish, whether you want to sling... | Read more »
Reigns: Her Majesty guide - how to swipe...
Reigns: Her Majesty is storming the App Store this week, bringing more tinder-esque kingdom building to eager players everywhere. If you've played the original Reigns, you'll know that leading a kingdom is never easy. It's a careful balancing act... | Read more »
Getting Over It (Games)
Getting Over It 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: A game I madeFor a certain kind of person To hurt them. • Climb up an enormous mountain with nothing but a hammer and a pot.•... | Read more »
Reigns: Her Majesty (Games)
Reigns: Her Majesty 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »

Price Scanner via MacPrices.net

Apple Watch Series 2, Certified Refurbished,...
Apple has Certified Refurbished Apple Watch Nike+ Series 2s, 42mm Space Gray Aluminum Case with Anthracite/Black Nike Sport Bands, available for $249 (38mm) or $279 (42mm). The 38mm model was out of... Read more
Apple offers Certified Refurbished 2016 12″ R...
Apple has Certified Refurbished 2016 12″ Retina MacBooks available starting at $949. Apple will include a standard one-year warranty with each MacBook, and shipping is free. The following... Read more
B&H drops price on 13″ 256GB MacBook Air...
B&H has the 13″ 1.8GHz/256GB Apple MacBook Air (MQD42LL/A) now on sale for $1079 including free shipping plus NY & NJ sales tax only. Their price is $120 off MSRP, and it’s the lowest price... Read more
Holiday sale: 9″ iPads starting at $299, take...
MacMall has 9″ WiFi iPads on sale for $30 off including free shipping: – 9″ 32GB WiFi iPad: $299 – 9″ 128GB WiFi iPad: $399 Read more
Green Monday deal: 15″ 2.8GHz MacBook Pro on...
B&H Photo has the 15″ 2.8GHz Space Gray MacBook Pro on sale for $250 off MSRP for today only as part of their Green Monday/Holiday sale. Shipping is free, and B&H charges sales tax for NY... Read more
Green Monday sale: B&H offers 12″ Apple i...
B&H Photo has 12″ iPad Pros on sale for up to $150 off MSRP as part of their Green Monday/Holiday sale. Shipping is free, and B&H charges sales tax in NY & NJ only: – 12″ 64GB WiFi iPad... Read more
Holiday deal: 21″ and 27″ Apple iMacs on sale...
MacMall has 2017 21″ and 27″ Apple iMacs on sale for up to $200 off MSRP. Shipping is free: – 21″ 2.3GHz iMac: $999 $100 off MSRP – 21″ 3.0GHz iMac: $1199 $100 off MSRP – 21″ 3.4GHz iMac: $1379 $120... Read more
Holiday deal: Apple Mac minis for up to $150...
MacMall has Mac minis on sale for up to $100 off MSRP, each including free shipping: – 1.4GHz Mac mini: $399 $100 off MSRP – 2.6GHz Mac mini: $599 $100 off MSRP – 2.8GHz Mac mini: $949 $50 off MSRP... Read more
Beats by Dr. Dre – BeatsX Earphones on sale f...
Best Buy has BeatsX Earphones on sale for $109, $40 off, on their online store. Sale price for online orders only. Choose free store pickup, if available, or choose free shipping. Read more
10″ 64GB WiFi Apple iPad Pros on sale for $59...
MacMall has 10.5″ 64GB Apple iPad Pros on sale for $599 including free shipping. That’s $50 off MSRP and among the lowest prices available for these iPads from any Apple reseller. Read more

Jobs Board

QA Automation Engineer, *Apple* Pay - Apple...
# QA Automation Engineer, Apple Pay Job Number: 113202642 Santa Clara Valley, California, United States Posted: 11-Dec-2017 Weekly Hours: 40.00 **Job Summary** At Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Information Security - Security Data...
# Apple Information Security - Security Data Analyst Job Number: 113119545 Austin, Texas, United States Posted: 10-Nov-2017 Weekly Hours: 40.00 **Job Summary** This Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.