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

Bean 3.3.3 - Fast and uncluttered word p...
Bean is no longer being actively developed, but will be updated as necessary to patch bugs and maintain OS X compatibility Bean is lean, fast, and uncluttered. If you get depressed at the thought of... Read more
Acorn 6.6.2 - Bitmap image editor.
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Tor Browser 10.0 - Anonymize Web browsin...
The Tor Browser Bundle is an easy-to-use portable package of Tor, Vidalia, Torbutton, and a Firefox fork preconfigured to work together out of the box. It contains a modified copy of Firefox that... Read more
EtreCheck Pro 6.3.2 - For troubleshootin...
EtreCheck is an app that displays the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support Communities to... Read more
Macs Fan Control 1.5.8.22 - Monitor and...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
Iridient Developer 3.4 - Powerful image-...
Iridient Developer (was RAW Developer) is a powerful image-conversion application designed specifically for OS X. Iridient Developer gives advanced photographers total control over every aspect of... Read more
Motion 5.4.7 - Create and customize Fina...
Motion is designed for video editors, Motion 5 lets you customize Final Cut Pro titles, transitions, and effects. Or create your own dazzling animations in 2D or 3D space, with real-time feedback as... Read more
calibre 5.0.1 - Complete e-book library...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital librarian... Read more
Compressor 4.4.8 - Adds power and flexib...
Compressor adds power and flexibility to Final Cut Pro X export. Customize output settings, work faster with distributed encoding, and tap into a comprehensive set of delivery features. Features:... Read more
Adobe Acrobat Reader 20.012.20048 - View...
Adobe Acrobat Reader allows users to view PDF documents. You may not know what a PDF file is, but you've probably come across one at some point. PDF files are used by companies and even the IRS to... Read more

Latest Forum Discussions

See All

Blastomancer is a comfortable puzzle gam...
Blastomancer arrived on Google Play for Android at the weekend. It’s a 2D puzzle game involving cartoon stick figure wizards and lots of bombs. [Read more] | Read more »
Undercrawl is a procedurally generated r...
Undercrawl is a roguelike dungeon crawler from indie developer Monster Shop Games. It's a genre that's popular in gaming in general but features even more frequently on mobile devices since the shorter, 'run' style of playthrough suits playing in... | Read more »
Distract Yourself With These Great Mobil...
There’s a lot going on right now, and I don’t really feel like trying to write some kind of pithy intro for it. All I’ll say is lots of people have been coming together and helping each other in small ways, and I’m choosing to focus on that as I... | Read more »
BTS Universe Story, the social game that...
Netmarble's highly anticipated social game, BTS Universe Story, is available now for iOS and Android. It's the second collaboration between the hugely successful mobile developer and the K-pop superstars following BTS World. [Read more] | Read more »
The 5 Best Mobile Games Like Hades
Supergiant Games finally released Hades upon the world this week, and we’re loving it. The game plays to all of the studio’s strengths while still retaining a strong sense of identity. It also just so happens to play rather well using the Steam... | Read more »
A Year of Apple Arcade: The Good, The Ba...
Apple Arcade has persisted for just over a year at this point, and although that means I've been busy ranking and re-ranking every game on the service for just about as long, I haven't done much reflection on the service as a whole. [Read more] | Read more »
Animal Restaurant anniversary event team...
Animal idle simulator Animal Restaurant is celebrating its first-year anniversary with a crossover event with popular YouTube series Aaron’s Animals. [Read more] | Read more »
Raziel: Dungeon Arena is a hack 'n...
Raziel: Dungeon Arena is available now on mobile and will appeal to fans of both comic books and old school dungeon crawlers. Not only will you hack 'n' slash your way through mobs of enemies but there's also fully-narrated animated comic to enjoy... | Read more »
Steam Link Spotlight - Hades
Steam Link Spotlight is a feature where we look at PC games that play exceptionally well using the Steam Link app. Our last entry was on Disco Elysium. Read about how it plays using Steam Link over here. | Read more »
Microsoft has acquired ZeniMax Media and...
In the latest of a series of blockbuster moves, Microsoft has now acquired Zenimax Media and its subsidiary, Bethesda Softworks, for $7.5 billion. [Read more] | Read more »

Price Scanner via MacPrices.net

Apple offers clearance 2019 27″ 5K iMacs for...
Apple has Certified Refurbished 2019 27″ 5K iMacs available starting at $1439 and up to $520 off their original MSRP. Apple’s one-year warranty is standard and shipping is free. The following... Read more
Weekend’s Best MacBook Deal: These 2020 13″ M...
Apple has a full line of Certified Refurbished 2020 13″ 1.4GHz 4-Core Touch Bar MacBook Pros available starting at $1099 and up to $230 off original MSRP. Apple’s one-year warranty is included,... Read more
Clearance 8-core iMac Pro available for $3819...
Apple has Certified Refurbished, clearance, 27″ 3.2GHz 8-Core iMac Pros available $3819 including free shipping. Their price is $1180 off the original MSRP of new models. A standard Apple one-year... Read more
How The Upcoming Mac Transition To Apple Sili...
FEATURE: 09.25.20 – Apple’s plan to transition all of its desktop and notebook computers away from Intel processors to Apple silicon, chips designed by the company itself, has been eclipsed by the... Read more
New low price! Apple Watch SE for only $269
B&H Photo is reporting limited stock of Apple’s new Apple Watch SE GPS models for $10 off MSRP and including free shipping. Their $269 price for the 40mm model is the lowest price we’ve seen so... Read more
Lowest price anywhere: New 13″ 2.0GHz MacBook...
Amazon has new 2020 13″ 2.0GHz/512GB MacBook Pros with 10th generation Intel processors back in stock on sale today for $200 off Apple’s MSRP. Shipping is free. Be sure to purchase the MacBook Pro... Read more
Apple Pro Display XDR with Nano-Texture Glass...
Amazon Apple Premier Partner GatorTec has the Apple Pro Display XDR with Nano-Texture Glass on sale for $5599 shipped, on Amazon. Their price is $400 off Apple’s MSRP, and it’s the cheapest price... Read more
Get a 2019 13″ MacBook Air for only $779 toda...
Apple has clearance, Certified Refurbished, 2019 13″ 1.6GHz/128GB MacBook Airs available again for $779. Each MacBook features a new outer case, comes with a standard Apple one-year warranty, and is... Read more
2020 11″ iPad Pros on sale today for $50-$75...
Apple reseller Expercom has new 2020 11″ Apple iPad Pros on sale for $50-$75 off MSRP, with prices starting at $749. These are the same iPad Pros sold by Apple in their retail and online stores: – 11... Read more
Apple has restocked 2020 13″ MacBook Airs sta...
Apple has restocked Certified Refurbished 2020 13″ MacBook Airs starting at only $849 and up to $200 off the cost of new Airs. Each MacBook features a new outer case, comes with a standard Apple one-... Read more

Jobs Board

Tier 2 Technical Support Analyst - ( *Apple*...
…Support Analystiwho will analyze and determine user software needs on all Apple devices (first support contact), Windows devices, and support printers in the Read more
Medical Assistant - Internal Medicine *Apple...
Schedule & Location Full Time Day (80 Hours every two weeks) Apple Hill Medical Center 25 Monument Road York PA Job Description: Under the general supervision of the Read more
*Apple* Technology Journalist - Valnet Freel...
…freelance basis. Valnet Inc. is looking for journalists with strong knowledge of Apple technology for our website MakeUseOf.com MakeUseOf is one of the largest Read more
Bookseller- *Apple* Shop Support - Penn Sta...
…combination of education, certification and experience will be considered. + A+ and/or Apple certified or able to achieve certification within 60 days required. + Read more
Freelance *Apple* Technology Journalist - V...
…freelance basis. Valnet Inc. is looking for journalists with strong knowledge of Apple technology for our website MakeUseOf.com MakeUseOf is one of the largest Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.