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.
Back in the day, a book like this would have been a real life saver for those of us slugging it out with brain-damaged operating systems (e.g. MS-DOS). From things like MIDI sequencers to guidance systems, the need for real-time speed was a real issue.
However, with the the maturity of operating systems, many of them now include device drivers, APIs, objects and other goodies that insulate the average programmer from the hassle of issues like latency. So my question is, other than good academic study, would it pay for the rest of us to spend the $$ on such a book?
Though I admit, having to write my share of real-time apps back in the day has me curious enough to put the book on my wishlist.
--- have you healed your church website?
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?
I remember when having a solid math background was de reguire for a programmer.
And I remember when being able to spell the words they used was de rigueur for anyone with an education.
I'm surprised to see it posted on /., though, because he's pretty harsh towards the gaming community. In fact, he says near the beginning that game-related technology in CPUs (MMX and so forth) is taking away much-needed brainpower from research that should be reaching towards making chips do more math per unit time (not to mention driving up production costs for toy-obsessed, joyless loners). He calls for an immediate end to the pandering that Intel et al do to get into the pocketbooks of the socially-inept, technology pseudo-elite and wants real reform in the area of empowering science.
Powerful stuff.
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..
Huh? What's the use of sine in an OS besides to draw glitzy GUI stuff?
Funny this topic should come up. I just did a 'Store Locator' for the company I work for (I'm the IT Manager, belive it or not). All I have is your basic HS diploma, and in creating the search, I realized I don't know a damn thing about sine and cosine. I don't know how they're used, or how they're applied. I have a feeling that they're somehow related to geometry (which makes sense, seeing I have to get a distance between two points on a curve - the earth), but I'm not sure.
Sure, it's probably taken me longer to write this post, than it took to find the php code I used as a basis for the search, but how much math is REALLY needed overall?
I slept through school, I did really bad, all because I felt it was worthless. I did feel that my business class, business law, and basic Algebra has been useful. But overall, it wasn't worth my time. Hell I had a physics teacher who'd pick on me because I was flunking (it's amazing what good test grades + 0 homework does to you), but I just found physics interesting - jeez, it was only HS. I was testing the waters, not padding my GPA. I believe that's what's HS is FOR.
And if you KNOW what you want to do (I knew I wanted to fix/program computers when I played on my Apple ][ in 6th grade), what the hell is college for?
The ease of the internet sure hasn't helped my perception.
Am I the only one?
"I can't give you a brain, so I'll give you a diploma" - The Great Oz (blatently stolen sig)
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.
I don't know of other programs, but I know at the University of Waterloo (where I am a computer science student), we must take quite a lot of math courses, ranging from linear algebra, calc, classical algebra, combinatorics & optimization and statistics. The math content for the CS program is very high, and in the end you get a BMath degree.
Maybe this is different at other schools (well, actually I know it is at most, most don't do nearly as much math), but I would hope not. I think to be a solid programmer a solid math background is a requirement.
oh, and btw, for anyone nitpicking, UW now offers a BCS program, as well as the typical BMath Honours CS. The BCS seems to offer a bit more flexibility, so BCS students may not choose to take 'as much' math.
The reason Santa is so jolly is that he knows where all the bad girls live.
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 ##
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
But to get a job writing computer graphics software, or audio processing, or designing any sort of embedded hardware, knowledge of advanced math is required. The people who want to do this kind of work pursue higher educations, and if they enjoy what they're doing then that's great, too.
Karma: Bored. (Thinking about resurrecting the "Anyone else is an imposter" joke.)
I graduated as a Math/CS double major from Drake University, where almost all CS majors also got a Math degree because the CS prereqs covered all but 3 of the Math prereqs. It has actually helped me enormously as a programmer to know math: in the past month, I've needed transformation matrices, sine/cosine stuff, and a bunch of other things that, granted, could have been lifted verbatim from Google groups, but it's often faster (and the code is better) if I just do it myself.
I've been programming since 1968, and very little had anything to do with math. People give me the same line, wow, I'm no good with math, I couldn't program, and don't believe me when I say computers add and subtract, multiply once in a while (array subscripting usually), and hardly ever divide.
Scientific or engineering programming, they need the math because they are math programming. The rest, forget it, maybe you add some numbers for a shopping cart, multiply for sales tax, but programming has little use for math.
I learned long ago that when an 8 bitter needs trig functions, you use a look up table generated externally.
Infuriate left and right
As for the title, I agree it's a bit misleading. The book has pretty little to do about real-time (in fact nothing, as far as I could see). What it really should be called is "Computer arithmetic and a little of numerical methods for dummies". This book will help you understand how to write your own libm, and give you some ideas for more advanced tasks, but that's about it.
For me, who didn't know much of this stuff, it was very interesting. It will probably not save you that course in numerical algorithms (which I for one haven't taken), but even then, it will probably contain some interesting tidbits you didn't know.
On the other hand, if you have years of experience in writing computer math routines, it will probably quickly become dull, but that's true about anything you already know.
It's not that trading raw power against development costs is unreasonable where that choice exists - far from it - but rather that hand-waving away questions of efficiency on the assumption that God (or Moore's Law[1]) will provide is a sure recipe for the sort of bloated and near-unmaintainable messes that are so common today. A Mbyte here, a Mbyte there, an assumption that the compiler will find and optimize the invariant components of loops... if you're not careful these all start adding up to measurable numbers "why is this so s l o w . . .")
[1]And, of course, one can always paraphrase Parkinson's Law for IT: programs and data expand to fill the processor power and storage available.
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?
A couple minutes of going through results granted me a simple:
"I can't give you a brain, so I'll give you a diploma" - The Great Oz (blatently stolen sig)
What came out as a belittling tone probably slipped through because I know that colleges around the country are churning out graduates with BSes in Information Technology or similar majors, all of whom are going to be going after YOUR JOB. Now it sounds like you've got a good mind and a good head start in the IT world so I wouldn't be too worried, but just know that your field isn't going to be getting any less competitive.
Cheers!
Karma: Bored. (Thinking about resurrecting the "Anyone else is an imposter" joke.)
Bn.com has this book listed at $49.95. Amazon has it for $34.97
Save your self some money!
As a biz-app programmer, I am bothered by too much attention given to floating point math and not enough to decimal math. A decimal-centric approach would give better results for monetary calculations, because any truncation and rounding are at decimal (base-10) boundaries instead of base-2 boundaries. It gives results more like one expects doing it by hand on paper, which shapes most peoples' perceptions of what they expect (and the customer is always right, even if they are boneheads).
The only library I know that supports it is the BC-library sometimes used with PHP. (Well, I guess you could say that COBOL has such also.) It actually uses strings to hold the results so that there is no machine-based limitation on precision size. Plus, that improves its cross-language use since almost everything supports dynamic strings these days.
(Not the fasted approach I suppose, but most biz apps are not math intensive anyhow. Most code is devoted to comparing strings, codes, and ID's and moving things around from place to place. IBM used to include decimal-friendly operations in its CPU's. Those days seem gone for some reason, yet biz apps are still a huge domain.)
Table-ized A.I.
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.
May I be the first to say, that is a sad Math minor. You should at least need to get to Number Theory or Algebra and Real Analysis to qualify for a Math minor. Those five classes are (or should be) requirements for any science course, including Comp Sci.
Fortran programmer...oh yeah. Array math for life!
FWIW, There's a lot of people out there who don't think too much of numerical recipes: http://math.jpl.nasa.gov/nr/
When I have, I've never needed anything beyond what I could find in a textbook or online in less than 5 minutes.
Heck, I've practically never even had any reason to use floating point math over that period of time.
Sure, there are lots of areas where you do need maths beyond what you can pick up from a book in 5 minutes, but there are far more where maths is irellevant.
Beyond basic algebra, maths is just another set of domain knowledge that you'll need to aquire to do particular types of software development, not something that is an inherent requirement in order to be a good coder.
For those who don't support Slashdot's Amazon embargo, here's their link to the book. Not only are they selling the book for $35, they have 25 sample pages, including the entire index and the first half of the first chapter. (And no, I'm not in Amazon's affiliates program and don't make a dime if you buy the book using the link that I provided, as a quick glance at the URL will prove.)
:wq
It will depend really on what you call yourself. I am an engineer and I have been programming for almost 25 years however my background is definitly skewed towards scientific programming. You can even see it in the sequence of programming languages that I learned over my career:
BASIC->FORTRAN->ASSEMBLER->PASCAL->C->LISP->XLISP- >C++->JAVA
I don't call myself a programmer, but an engineer who programs. This is because you will notice there are some importand tools missing from the above list. Things such as PERL which we know that every real programmer would have in their toolbox.
"player 4 hit player 1 with 0 stroms"
Your code may do the job, but does it do the job efficiently? And if it didn't, how would you know?
I changed majors from CS to Mathematics halfway through because I realized that programming is easy; you can always learn a new language or a new technique by picking up the appropriate O'Reilly book on the subject. But writing good programs -- programs that are robust, that scale well, that do as much as possible as quickly as possible -- is really applied math. And math is hard.
You simply have no idea how much you don't know, and with the attitude you have, you probably never will.
The correlation between ignorance of statistics and using "correlation is not causation" as an argument is close to 1.
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.
How many EDI people know PC's? Networks?
:-)
Almost everybody in the EDI field sort of stumbled their way into it accidentally.
I used to be the primary EDI guy where I worked a few years ago, but I haven't touched it since. I think I can still look at an unparsed 850 (X12) transaction set and tell you what's on it without thinking about it, and writing a program to parse all those nested loops is pretty fun. I can probably belch out a 997 FA after chugging a pint of beer. That would impress a very small number of people, unfortunately.
But I also know a lot about PC's (served time doing desktop support) and a little networking.
-CausticPuppy "Of all the people I know, you're certainly one of them." -Somebody I don't know
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.
It's pretty easy to see that the author is a heavy follower of the KISS philosophy.
You mean he wants to rock and roll all nite and code every day? Sweet!
KISS rulez, Man!
GMD
watch this
Well, see, I'm a database guy too. I split my day pretty much equally between SQL and PHP. A lot of people may not consider that "real programming." I do, and in fact I've done some pretty heavy-duty scientific application programming in that past, and I'm here to tell you, I use my math skills just as much now as I did then. Because I don't just write queries and interfaces; I write them with absolutely fanatical attention to detail, and I subject everything I put up on my company's server to the kind of rigorous scrutiny I learned in set theory and algorithm analysis classes. And as a result, it works, and it works well, and on the rare occasions that something doesn't work as well as it should, I know how to fix it. The bigger applications get, the less meaningful the 90/10 theory really is -- for very big applications, a whole of bunch of seemingly trivial speed and scalability tweaks add up to big improvements down the road.
The correlation between ignorance of statistics and using "correlation is not causation" as an argument is close to 1.
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.
Lord Kelvin put it best (though the notebooks of Lazarus Long come darned close):
Anyone who doesn't know at least some basic math and statistics is a sucker for all the fallacies pushed by advertisers, politicians, and groups with an agenda. And once you've done your Google search for a formula to plug and chug, how do you test it if you don't know enough math to really understand it?
If you still need a decent integer square root algo, check out this page. I used the mborg_isqrt2 variant on that page as a starting point for writing my highly optimized Intellivision version for SDK-1600. My optimized version takes about 600 - 700 cycles for a 16-bit square root, on a machine where most operations take 6 to 8 cycles. (The version I was replacing took 4000 - 10000 cycles.)
This book looks like it might be interesting to me. Here at work, we had our own math expert, but he's retired (or semi-retired). We've contracted with him to do math libraries, and that works for now. But what about 10 years from now? There's a lot of subtlety in some of these algorithms (it's not always just as easy as whipping through a Taylor series expansion), so it's probably time someone in our group started learning. :-)
--JoeProgram Intellivision!
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!
Real-time and going fast are two totally different problems.
Satellite controllers may need real-time programming - there's physical stuff moving, and if a signal needs to be responded to in the 100ms before the bird turns another degree, you need hard real-time. But there's nothing that a bank does that needs real-time, unless the device in an ATM that hands out the cash is really badly designed. Yes, you need to know that the customer has taken the cash out of the slot or that the receipt-printer's finished, but if you find out 100ms late some of the time, it isn't going to hand out the wrong amount of money, it's just going to be slightly later drawing the next screenful of customer interaction. Some of their stuff needs to get high volumes of work done quickly, but that's a throughput problem, not a real-time problem, and you might get better throughput if some of the transactions have wait their turn rather than preempting other ones.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks