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.
I remember when having a solid math background was de reguire for a programmer. Of course, I'm talking the mid 80's, engineering school and Fortran, so I'm kind of krufty.
I wonder how much better could we be if coders knew basic math, if they know how those little bitty chips actually computed the sine of something instead of assuming it works. We would probably have rock solid operating systems without all the glitzy GUI stuf..
How does the book compare to the classics: Numerical Recipes, The Art of Computer Programming, etc?
Someone marked this question redundant? Guess that shows you jerks are everywhere.
Hey, I understand completely what you're saying. I for one am glad I don't have to deal with such as latency and pre-emption. In fact, here is a link to a nifty article entitled "Real Time Issues in Linux" that essentially sums up what you asked with a resounding yes.
healyourchurchwebsite.com - WWJB?
The above generally doesn't apply to anyone doing serious embedded work with small and midrange microcontrollers. Often an operating system is thin to non-existent on these platforms. Some of the lower-range parts may have a 2-byte hardware stack, 28 bytes of RAM and maybe 512 bytes of program memory. Obviously, you won't be doing much sophisticated numerical work on these smallest of microcontrollers, but for more midrange parts, I've found this book to be a godsend.
The book is not aimed at PC users.
Roving Web-Teleoperated Robot
When I went for my Comp Sci bachelor's I was amazed at how many math-phobics there were in my Comp Sci classes. As part of earning the degree you had to take 4 specified math classes (Calc 1 & 2, Linear Systems, Probability). You only had to take one more math class to get a minor in mathematics, Calculus 3.
Now I've always been big on math but I was kind of surprised at how few people were willing to take a single class to earn a full-fledged minor.
The Forth literature contains many examples of high-performance hardware-integer-math-only routines. A core feature of most Forth algos is rescaling to a power of two space at the start of the algo and from it at the end. This allows bit shift operators to do their stuff. It can take non-trivial fiddling to rescale algorithms - hence, it's nice to just look them up.
Unfortunately, it's tricky to find Forth books these days.
That's a shame, because along with Smalltalk, Lisp and APL, I think Forth is one of the "mind expanding" languages all programmers should at least experience, instead of just deciding C/Java/C++/VB is the one true language.
Not to nitpick here, but if you honestly wanted to "squeeze every last bit of math power out of the CPU", would you really be writing Perl scripts?
Just wondering...
-ubermuffin
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 then had a fair old "discussion" with the one person in the audience whose head hadn't been overflown (sic), as there was plainly still much controversy left in this area. 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.
The reviewer's concern that coprocessor-less systems should be covered is valid, but I'm not sure going as far as assembly is necessary. For example, I once had the privilige of reading through Hitachi's libm implementation for their H8 series microprocessor/microcontroller (one would be generous to call H8 a 16-bit system, and ungenerous to call it an 8-bit system). With one small exception (I think the cos table lookup) the whole thing was in (quite readable) C, and (at least for basic libm stuff) performance was perfectly acceptable. For didactic purposes, a C (or sane C++) implementation would be the thing one would want to find in a book - I get very annoyed at embedded books where the examples are written in asm for the author's favourite (obscure) microcontroller.
## W.Finlay McWalter ## http://www.mcwalter.org ##
Yes. Banks, old satallite programs, messaging systems...etc.
I work with a group of eight other people updating 40 year old Assembler on an IBM Series 1. Something tells me that if this was included in our training programs, those that are
SUF
FER
ING
through the digit-crunching wouldn't have such a hard time. Most people consider this back-in-the-day, but there's an aaaawwwful lot out there that still reeks of old german engineering, and chunk-button ATMs.
{...reality is wrong, Dreams are for real...}
Embedded != Assembly coding.
To be honest, a lot of embedded coding is done with C or C++ these days. I've been following Crenshaw's articles in Embedded Developer magazine for years now. He explains a lot of what they try to teach in college Calc, etc. in simple, practical terms, and reduces it to usable algorithms.
I'd probably buy the book and add it to my shelf.
I am not merely a "consumer" or a "taxpayer". I am a Citizen of the State of Texas
I am currently trying to get a data-acquisition computer to keep up with a five thousand frame-per-second video feed while doing processing between the frames. Hard real-time is a real issue for me.
I won't bash you like some of the other replies to your post, nor will I give you hope that you can advance past a limited set of jobs in the IT industry.
College (esp for computer engineering and CS) fundamentally teaches you:
1. How to solve problems
2. A toolset (ie math, algorithms) to go about solving those problems
True, you may not ever use calculus, but as a computer scientist you will use matrix theory because it is the best way to solve some problems.
This is not only for scientific/research either. If you try to write anything performance related, you'll have to use higher math. Computer science ain't easy.
Let me stress again that college teaches you about your subject matter and how to solve problems for it. You can come up with this stuff by yourself, in my experience only a tiny percent working without a college degree will ever accrue enough to offset what they missed in college.
Why, o why must the sky fall when I've learned to fly?
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
But by "math" the reference is almost always to calculus.
But math is not just calculus.
Math includes (and this is a MINIMAL list :
- algebra Every program using symbols to represent things that might vary is using algebra. Algebra isnt just manipulating big expressions to find values of x and y - it is really about using names to refer to values. (For example x=y+1 is fundamentally an algebraic expression.
And there's more - check out Glassner's "Digital Image Synthesis", or Knuth's "Art of Computer Programming", - find places where mathematics is not mentioned. Let alone such things as wavelets, the Mandelbrot set, grammars, text (or UI) layout, automata (and on, and on, and on...). I can show you a very hard mathematical problem (which I'm still working on) based on an algorithm you all know, but that is often coded incorrectly.boolean logic Using logical expressions and understanding what they do is just the predicate calculus. Using logic languages (prolog primarily) is, well, logic.
Linear Algebra Try to program more than minimal graphics without linear algebra.
The structure of numbers computing square roots and the like. This kind of computing also typically involves calculus and its relatives
Calculus many parts of computational mathematics, including things like square roots, sin/cos and the like. Also, finding tangents and normals to surfaces which is a big part of reflection models in graphics. The logic involved is also used in the analysis of algorithms.
logical reasoning Every time someone writes a loop or a recursive function, they are essentially using mathematical induction (albeit informally). Propagation of pre/post conditions (not just in procedure calls, but on the statement to statement level is also logical reasoning (and informal proofs).
Fourier analysis Fourier analysis is essential in image manipulation (including compression), graphics in general, Most algorithms involving sound processing also rely on fourier analysis
Graph Theory Where doesn't graph theory show up? Dependency graphs, path algorithms of all sorts. Trees are graphs. Garbage collection involves graph theory. Programs are (on several levels) graphs. The internet as a network is a graph. Websites are graphs (and it can be interesting and revealing to look at them as such).
Number Theory Cryptography!
If you're not doing any of these things, you may be programming, but you're probably not programming well.
Juris Hartmanis said (half jokingly) in his Turing Award lecture that "Computer Science is the engineering of mathematics" I think its about as good a definition as any I have ever heard.