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/.

 
AAPL
$524.94
Apple Inc.
+5.93
MSFT
$40.01
Microsoft Corpora
-0.39
GOOG
$536.10
Google Inc.
-20.44

MacTech Search:
Community Search:

Software Updates via MacUpdate

Tweetbot 1.5.1 - Popular iOS twitter cli...
Tweetbot is a full-featured OS X Twitter client with a lot of personality. Whether it's the meticulously-crafted interface, sounds and animation, or features like multiple timelines and column views... Read more
Mac DVDRipper Pro 4.1.7 - Copy, backup,...
Mac DVDRipper Pro is the DVD backup solution that lets you protect your DVDs from scratches, save your batteries by reading your movies from your hard disk, manage your collection with just a few... Read more
PDFpenPro 6.2 - Advanced PDF toolkit for...
PDFpenPro allows users to edit PDF's easily. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Create... Read more
PDFpen 6.2 - Edit and annotate PDFs with...
PDFpen allows users to easily edit PDF's. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Features... Read more
Monolingual 1.5.9 - Remove unwanted OS X...
Monolingual is a program for removing unnecesary language resources from OS X, in order to reclaim several hundred megabytes of disk space. It requires a 64-bit capable Intel-based Mac and at least... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
Starcraft II: Wings of Liberty 1.1.1.180...
Download the patch by launching the Starcraft II game and downloading it through the Battle.net connection within the app. Starcraft II: Wings of Liberty is a strategy game played in real-time. You... Read more
Sibelius 7.5.0 - Music notation solution...
Sibelius is the world's best-selling music notation software for Mac. It is as intuitive to use as a pen, yet so powerful that it does most things in less than the blink of an eye. The demo includes... Read more
Typinator 5.9 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
MYStuff Pro 2.0.16 - Create inventories...
MYStuff Pro is the most flexible way to create detail-rich inventories for your home or small business. Add items to MYStuff by dragging and dropping existing information, uploading new images, or... Read more

Latest Forum Discussions

See All

Have a Special Dead Trigger 2 Easter Bas...
Have a Special Dead Trigger 2 Easter Basket Full of Goodies, Courtesy of Madfinger Games Posted by Rob Rich on April 18th, 2014 [ permalink ] Dead Trigger 2 | Read more »
Zynga Launches Brand New Farmville Exper...
Zynga Launches Brand New Farmville Experience with Farmville 2: Country Escape Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »
David. Review
David. Review By Cata Modorcea on April 18th, 2014 Our Rating: :: MINIMALISTIC IN A DIFFERENT WAYUniversal App - Designed for iPhone and iPad David is a minimalistic game wrapped inside of a soothing atmosphere in which the hero... | Read more »
Eyefi Unveils New Eyefi Cloud Service Th...
Eyefi Unveils New Eyefi Cloud Service That Allows Users to Share Media Across Personal Devices Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »
Tales from the Dragon Mountain: The Lair...
Tales from the Dragon Mountain: The Lair Review By Jennifer Allen on April 18th, 2014 Our Rating: :: STEADY ADVENTURINGiPad Only App - Designed for the iPad Treading a safe path, Tales from the Dragon Mountain: The Lair is a... | Read more »
Yahoo Updates Flickr App with Advanced E...
Yahoo Updates Flickr App with Advanced Editing Features and More Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »
My Incredible Body - A Kid's App to...
My Incredible Body - A Kid's App to Learn about the Human Body 1.1.00 Device: iOS Universal Category: Education Price: $2.99, Version: 1.1.00 (iTunes) Description: Wouldn’t it be cool to look inside yourself and see what was going on... | Read more »
Trials Frontier Review
Trials Frontier Review By Carter Dotson on April 18th, 2014 Our Rating: :: A ROUGH LANDINGUniversal App - Designed for iPhone and iPad Trials Frontier finally brings the famed stunt racing franchise to mobile, but how much does its... | Read more »
Evernote Business Notebook by Moleskin I...
Evernote Business Notebook by Moleskin Introduced – Support Available in Evernote for iOS Posted by Tre Lawrence on April 18th, 2014 [ permalink ] | Read more »
Sparkle Unleashed Review
Sparkle Unleashed Review By Jennifer Allen on April 18th, 2014 Our Rating: :: CLASSY MARBLE FLINGINGUniversal App - Designed for iPhone and iPad It’s a concept we’ve seen before, but Sparkle Unleashed is a solidly enjoyable orb... | Read more »

Price Scanner via MacPrices.net

iMacs on sale for up to $160 off MSRP this we...
Best Buy has iMacs on sale for up to $160 off MSRP for a limited time. Choose free home shipping or free instant local store pickup (if available). Prices are valid for online orders only, in-store... Read more
iPad Airs on sale this weekend for up to $100...
Best Buy has WiFi iPad Airs on sale for $50 off MSRP and WiFi + Cellular iPad Airs on sale for $100 off MSRP on their online store for a limited time, with prices now starting at $449. Choose free... Read more
Apple restocks refurbished Mac minis starting...
The Apple Store has restocked Apple Certified Refurbished Mac minis for up to $150 off the cost of new models. Apple’s one-year warranty is included with each mini, and shipping is free: - 2.5GHz Mac... Read more
Hyundai Brings Apple CarPlay To The 2015 Sona...
Hyundai Motor America has announced it will bring Apple CarPlay functionality to the 2015 Sonata. CarPlay is pitched as a smarter, safer and easier way to use iPhone in the car and gives iPhone users... Read more
Updated iPads Coming Sooner Than We Had Thoug...
MacRumors, cites KGI securities analyst Ming Chi Kuo, well-respected as an Apple product prognisticator, saying that Apple will introduce an upgraded iPad Air and iPad mini in 2014/Q3, meaning the... Read more
Toshiba Unveils New High And Low End Laptop M...
Toshiba has announced new laptop models covering both the high-end and low-end of the notebook computer spectrum. Toshiba 4K Ultra HD Laptop Toshiba’s new Satellite P55t features one of the world’s... Read more
Save up to $270 with Apple refurbished 13-inc...
The Apple Store has Apple Certified Refurbished October 2013 13″ Retina MacBook Pros available starting at $1099, with models up to $270 off MSRP. Apple’s one-year warranty is standard, and shipping... Read more
Apple now offering refurbished iPad mini with...
The Apple Store has Certified Refurbished 2nd generation iPad minis with Retina Displays now available starting at $339. Apple’s one-year warranty is included with each model, and shipping is free.... Read more
Microsoft Blinks – Drops Microsoft Office 365...
Microsoft has dropped the annual subscription fee for Microsoft Office 365 Personal – which is needed in order to create and edit documents in Microsoft Office for iPad. However, Apple’s iOS and OS X... Read more
New AVG Vault Apps for iOS and Android Help K...
AVG Technologies N.V. an online security company for 177 million active users, has announced the launch of its latest mobile application, AVG Vault. The free app introduces an innovative user... Read more

Jobs Board

*Apple* Automotive Parts Department position...
Apple Automotive is one of the fastest growing dealer…and it shows. Consider making the switch to the Apple Automotive Group today! At Apple Automotive, we Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**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* Retail - Manager - Holyoke - Apple I...
Job Summary Keeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you’re a master of them all. In the store’s fast-paced, Read more
*Apple* Retail - Manager - Apple (United Sta...
Job SummaryKeeping an Apple Store thriving requires a diverse set of leadership skills, and as a Manager, you're a master of them all. In the store's fast-paced, dynamic Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.