Friday, April 23, 2010

Magic and other programming tricks

This is some good stuff.
Normally, a dual-linked circular list would contain both previous and next pointer fields and the current position in the list would be identified by a single pointer. By using two current pointers, one to the node in question and the other to the one just before/after it, it becomes possible to store only a single pointer value in each node. The value stored in each node is the XOR of the next and previous pointers that normally would have been stored in each node. Decoding is obvious.

If you program and are unfamiliar with the dangers of floating point, then you should read this. Proper understanding of how floating point actually works is important because sometimes "cos(x) != cos(y) even though x == y".
Turns out that the behavior can depend on how many instructions are between the cos() calls and the != comparison.
This is another example of the trickery of floating point. Thinking about this, I recently said to a friend of mine, "I'm surprised companies' billing systems ever work", his response was "maybe they don't". Which is kind of disturbing to think about. Though some have claimed that this is why we will be running Cobol code forever.

My personal rule of thumb is that closed source software needs to be at least two orders of magnitude better in performance then the equivalent open source program. Otherwise it is not worth all the hassles. On that note, Octave is a MATLAB replacement that on my list of software to try. Also, unlike MATLAB it can be connected to ROS, which is nice.

On another computational note, I liked the fifth edition of this textbook for an introduction to numerical methods. Which could be useful if you are trying to program complex math(s) on a microcontroller.

4 comments:

Pierce Nichols said...

Financial software doesn't use floating point for exactly the reason you described. Or at least it's not supposed to -- I'm sure there are plenty of shitty packages out there that get this wrong.

I Heart Robotics said...

At least in scientific computing the floating point errors will often cancel each other out.

All those $19.95 and $19.99 prices must wreck havoc with financial computing, and when you add in things like compound interest it must drive people crazy.

Is there an asylum somewhere filled with damaged Cobol programmers?

ian said...

Any thoughts on choosing between Octave, SciPy, SciLab, SAGE, etc.? When I was in an academic environment, MatLab and LabView were all over the place - but they are too expensive for the curious individual working in a non professional context. I'm mainly interested in tinkering with signal processing problems, and possibly working with ROS in the future.

I Heart Robotics said...

If you were going to learn one programming language at this point I would say your best bet is python. It's a well designed language and is useful a wide variety of projects. I really like the community emphasis on writing readable code.

I wrote some large array manipulation code with NumPy recently and it was fairly enjoyable. The only downside is that python may not be fast enough if you are working with huge datasets.

Octave seems useful if you already know MATLAB and don't know anything else.

Personally I usually use C or C++ since it is often the only option, as is the case on embedded systems and it usually allows you to squeeze out the best performance.