Slashdot Mirror
Math Toolkit for Real-Time Programming
Who & What
Jack W. Crenshaw, Ph.D. (Physics) wrote his first computer program in 1956 for an IBM 650. He has been working with real-time software for embedded systems ever since -- contributing several years to NASA during the Mercury, Gemini, and Apollo programs. In addition to other activities, he is currently a contributing editor for Embedded Systems Programming magazine and author of the Programmer's Toolbox column.
In Math Toolkit for Real-Time Programming, his effort is focused on describing the pitfalls of vendor-provided math libraries and providing robust replacements. In section one he gives a thorough overview of constants and the various manners in which to declare them, naming conventions, and error handling. As the work progresses, in section two, he builds a library of proven algorithms ranging from square roots to trigonometrical functions to logarithms. Did you suffer through calculus in college with a barely passing grade? Section three will teach you more about numerical calculus in a half-hour than you may have learned in three semesters.
KudosMath Toolkit is written in an easy to understand anecdotal manner. You might be tempted to think that the author was animatedly relating the history of computing square roots while having lunch with you. This method works very well and keeps what could be a rather heavy subject from becoming too much of a burden. Most chapters have historical tidbits liberally sprinkled throughout.
Even if college algebra left you with post-traumatic stress disorder, you will not have any trouble with section two. Indeed, you may find yourself intently following the author on the trail of the perfect arctangent algorithm -- much as a sleuth on the trail of a villain.
The depth of knowledge shown, and its presentation, is exceptional. The author's years of experience are evident in his self-confident writing style. You will rarely see a clearer overview of numerical calculus. QuibblesThe cover of the book states: "Do big math on small machines." This, combined with the Real-Time Programming phrase in the title, might lead one to believe that the book's primary audience is intended to be the embedded microcontroller crowd. Sadly, not so. There is very little here for the die-hard assembler programmer other than some very handy integer square root and sine routines - and these examples are in C++. Based on the cover, I would have liked to see a greater emphasis on processors lacking a floating point unit. Also, some code examples in pseudo-assembler would have been welcome, as the author chose C++ as the language of choice for all examples.
CrimesAs is so often the case nowadays, there are various typographical errors scattered throughout. This seems to be an epidemic in current technical books. Fortunately, it didn't affect the readability of Math Toolkit.
ConclusionsI believe Math Toolkit for Real-Time Programming would be a great, perhaps mandatory, addition to the bookshelf of anyone that is involved in writing code that has a heavy math component. Other than the somewhat misleading cover, I cannot find anything truly negative to say about this work. Congratulations are in order to Mr. Crenshaw on a job well done.
The book also includes a CD-ROM of all example source code. In reality, to get the best benefit from the book, you should mostly ignore the CD-ROM and work through the examples. To quote the author: "Never trust a person who merely hands you an equation."
Table of Contents
- Getting The Constants Right
- A Few Easy Pieces
- Dealing with Errors
- Fundamental Functions
- Getting the Sines Right
- Arctangents: An Angle-Space Odyssey
- Logging in the Answers
- Numerical Calculus
- Calculus by the Numbers
- Putting Numerical Calculus to Work
- The Runge-Kutta Method
- Dynamic Simulation
- Appendix A: A C++ Tools Library
I received a review copy of this book from the publisher. Thus, my loyalties and opinions may be completely skewed. Caveat Lector.
You can purchase Math Toolkit for Real-Time Programming from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
Well... Realtime programming might now be an issue for you if you use an advanced OS coupled with a mighty cpu.
But in many situations you might find yourself programming for, say, a small 1 MHz cpu in a timecritic controllsystem at a factory or chemicalplant or something like that.
That's when you'll need your skills in realtime programming.
/.Mattsson - My native language is not English, so please don't whine over linguistic errors. (That's lame anyway...)
The subject matter of this book is slightly different, since it has an emphasis on real-time. If you're just interested in crunching a large problem as fast as possible, then latency is not an issue.
BTW, if anyone wants to take a gander at Numerical Recipes in C/Fortran they are available here.
I actually have this book. It does read fairly well with some good examples: although I should note that I haven't finished it yet. One thing it is especially usefull for is defining a math library that's accurate. Crenshaw talks about how a lot of compiler's built in function/methods don't hold up to rigorous math and he's right. But instead of just complaining about it he walks through solid alternatives. Overall it's pretty good and would provide some quality code for open projects. IMHO anyway.
(Sponsored by cheeseSource for President 2012)
Bn.com has this book listed at $49.95. Amazon has it for $34.97
Save your self some money!
This deserves some more explanation, since everyone here seems to have missed this point.
A Real Time system is one where the ouptut isn't correct unless it arrives on time. Real Time systems are deterministic - not necessarily fast. The key is to use bounded-time algorithims so that you can predict the worst case execution time at compile time. RTOS's aren't designed to be fast, they are designed to have deterministic schedulers and kernel services.
Of course, faster processors make it easier to meet real time deadlines, but as processors get faster I'm seeing engineers ignore the real time analysis and design because the code passed the last test they ran. Then they are surprised when it fails in the field...
Jeff
Mr. Crenshaw is also the author of the popular Let's Build a Compiler series of articles a while back.
These articles don't go into a lot of the complicated stuff that's involved in modern compiler design-- Crenshaw keeps it simple, keeps it straightforward, and still produces a working (if not optimizing) compiler by the end of the second or third article.
No, it won't let you code a C compiler that will beat the pants off of gcc or Borland's latest offering, but the end result is pretty useful.
FWIW, There's a lot of people out there who don't think too much of numerical recipes: http://math.jpl.nasa.gov/nr/
A year (or so) ago I attended a lecture given by Guy Steele (of Lisp/Java/ Crunchly fame) on his proposal to alter how IEEE floating point numbers are mapped to real numbers. It quickly flew over my head, but gave a great insight into the whole field.
Steele is God. He also invented Scheme, wrote the original Common Lisp manual, co-wrote with Harbison a classic reference manual for C, and wrote parallel languages for the Connection Machine.
On trying to do some "why didn't I get this stuff at college" reading, I found there wasn't a great deal of literature.
This is widely considered a good introduction.
Actually even if you're just doing basic sorts, searches and manipulate data structures, its amazing how much math goes into it. Ever considered the algorithmic complexity of using binary trees versus randomized data structures like skip lists?
You can be a "computer programmer", but to be a good one that actually has a brain and knows the pros and cons of the algorithms you're coding out requires math. At least the basics of probability theory and calculus.
"In mathematics, it's not enough to read the words -- you have to hear the music"
I used this book as one of the references for my Game Developer Conference course on "Faster Math Functions", and the book is good but has holes. Crenshaw's style shows his crusty old engineer roots at times - his coverage of Mininax polynomials is way behind the times and he seriously needs to get into Mathematica or Maple as his basic high-precision tool.
Work by Tang on combatting destructive cancellation in range reduction, the new semi-table based exponant and log methods, Intel's research into using Estrin's Method based SIMD for evaluating polynomials or Muller's book on Elementary Functions are beyond Crenshaw's experience, and it shows. This is a homebrew book rather than an introduction to the state of the art. More information at SCEA R&D Website.
Jack should just about be a household name. When Apollo 13 went berserk, NASA dusted off some calculations of trajectories that he had previously done (he was no longer working for NASA) and used one of them to bring the astronauts back.
What's sad is that discrete math isn't really taught in public school. (At least, it wasn't when I was in school.) One day, I found a Discrete Math textbook at the local library in the 'For sale, $0.25' bin. I opened it up and thought "Oh my goodness, this is a programming and algorithms book!" To my mind, 'math' had always meant either calculation (symbolic or otherwise, your typical Algebra and Calculus), or geometry and proofs. While geometric proofs may border on discrete math, they really seem different to me. They're not algorithms.
Discrete Math branches into useful concepts such as graph theory (you couldn't do network routing successfully without it!), some of the basics of sorting, and so on. Basically, it was the math of "machines" -- that branch of mathematics which concerns itself with stepwise algorithms. Djikstra's algorithm (least cost path through a weighted graph), Prim's and Kruskal's algorithms (minimum cost spanning trees) were all in there. I thought the book was great.
And, of course, not a single line of code in it. (At least, not in any computer programming language.) But I still thought of it as a programming book.
--JoeProgram Intellivision!