Three-Shear Image Rotation...

Nick Berry has the best explication of three-shear image rotation I've ever seen – something any programmer could understand...

Computer Science Blogs...

A very nice list of CS-related blogs.  At least half of these were new to me...

Grace Hopper...

While I was in Navy “C” school at Mare Island, California I had the chance to meet Grace Hopper.  This would have been in 1972 or 1973.  At the time, I had no idea of her career or accomplishments.  I first met her when she lectured to a large group of people attending and teaching the various technical schools there (mainly Data Systems Technicians and various rates attending cryptographic schools).  This must have been late in the week, because on the following weekend I met her again – this time much less formally, and one-on-one.  That meeting was quite memorable.

The Data Systems Technician school that I was attending had a “lab” with a large collection of the kinds of equipment we were learning how to repair.  This collection included a number of military Univac computers (models like the 1206a, 1206b, 1218, and 1230, for those of you who can remember such antiques).  This was like a playground for me after school hours; I spent many evening and weekend hours just poking around in there, learning as much as I could.  Most of the time, I had this extensive lab completely to myself.

On the weekend in question, I had rolled an oscilloscope (they were big back then!) over to a computer, and I was running a little test program and observing how the electronics responded – trying to figure out how the hardware integer square root instruction (on a 1206b) actually worked.  While heads down, staring at a schematic, I heard someone come up behind me.  I turned around, and there was Grace Hopper – with a friendly smile, and in civilian clothes. She was a high-ranking officer, normally quite a scary thing to a low-ranking enlisted guy like myself.  But it was obvious right from the first that she was “just people”, and not the type to insist (as many officers did) on formalities.

Ms. Hopper wanted to know why I was there, and what I was up to.  When I told her I was trying to figure out the damned square root instruction, she hauled me off to a blackboard (yes, with slate and chalk!), and launched into a great explanation.  By the time we were done, I knew that thing inside and out.

Then she sat with me for another half hour or so, and just talked about working with computers.  She was the first person I'd met who was actually passionate about working with computers – and she was also the first programmer I'd ever met.  The people I was surrounded by were technicians; people who understood the hardware, how it worked, and how to troubleshoot it.  Ms. Hopper understood the hardware, but what she really cared about was the software.  On several occasions during that conversation, she encouraged me to get serious about learning how to program if I wanted to pursue a career in computers.  When I asked her how one might go about doing that, she said “Just practice.  Write programs, for anything.  Do it over and over until you're happy with the result.  You might consider going to college when you get out of the Navy, but what really matters is to practice.”

If I could choose one moment that started my career in programming, that would be it.  I didn't immediately stop working on hardware, though – I continued to work extensively in hardware design for more than 10 years after that.  But I did start seriously investigating programming immediately following that meeting with her.  I've never stopped.

I never had the privilege of talking with Ms. Hopper again.  About a week after I met her, someone at the school clued me in a bit on her career, and I read a book about her (in which I discovered how she started the use of the word "bug" to describe a software problem!).  After the fact I was awed that she actually sat down and talked with me for an hour or so.  I'm glad I didn't know about that when she walked up to me – I'd have been terrified!  Most especially, though, I'd have enjoyed a followup conversation, and especially the opportunity to thank her for her good advice and inspiration to me.

So perhaps you'll understand now why I found this video of Grace Hopper to be quite a trip down memory lane...

Stupid Float Tricks...

Don't click here unless you have a geekly interest in IEEE float internals...

Force-Feed State Machines...

Generally my peers think I'm pretty weird (and that's an objective of mine!).  There are a few things about my development likes and dislikes that stand out to them, and are a frequent source of odd looks and sadly shaking heads as my peers ponder my deteriorating mental condition.  One of these is my attraction to regular expressions.  Another is my fondness for finite state machines.

Here's someone who shares my appreciation of the latter, so much that he recommends forcing developers to use them!

Myself, I wouldn't go that far.  For me, a developer's understanding of, and use of, state machines is more an interesting metric of their ability to make software that works reliably in the real world, as that's one of the things that state machines are very good at...

Where the Electrons Hit the Silicon...

Via reader Doug S.:  some lucky computer science students in England are getting a chance to learn about how the guts of computers actually work.  Most modern students don't get much opportunity to learn this, as they're generally working with high-level languages on modern operating systems – and all this stuff very effectively hides how computers actually work.  This school, by deliberately putting students on quite old computer hardware (and quite incapable by today's standards), forces them to understand how the elemental bits of the computer work in order to get anything done...

P != NP?

If you're of the right geekly sort, you know whereof I speak.  A serious attempt at a formal proof of the above has been (apparently accidentally) released on the web, by an HP scientist named Vinay Deolalikar. Big news, if the proof is confirmed.

For those of you of a slighly less geekly bent, here's the scoop in very general terms: that statement (P != NP) encapsulates something that much of modern computer science is based on, but until now nobody has never been able to prove (in the formal mathematical sense).  In that sense (and in that sense only), it's sort of like Einstein's famous E = MC²...

There's a Reason Why Farmers are Smarter...

But it just may be a different reason than you imagined...

Avalanche Diagrams of Hash Functions...

Fascinating set of avalanche diagrams for various hash functions.  Like many analysis techniques, these take advantage of our perceptual system's ability to digest information rapidly.  FNV is much worse than I expected...

Computers Suck at Math...

Well, not really.  But they do make mistakes that surprise most people, including most professional programmers.  The basic problem is the way that computers usually represent numbers internally – with something called “binary floating point numbers”.  This article does a reasonably good job of explaining the problems in laymen's terms.

The most common place that errors in computer math show up is in financial calculations, where it's not unusual to need 15 or more digits of precision, and where calculations are often done repetitively (as in adding a large column of numbers).  Just to give a simple example, if the computer represents $0.01 as $0.0999934821, and you add enough of those pennies together, your result will be off by more than a penny.  Even though a computer did the math.

There are other ways that computer math can go horribly wrong, too.  All of these are well-known and covered by extensive literature, yet programmers keep making the same mistakes over and over again.  The basic error is to choose binary floating point to represent money (or other critical values).  Other representations exist.

So why do programmers keep doing this?  I've asked that question of programmers working for me on numerous occasions.  The most common response, by far, is something along the lines of “These errors only show up because the incorrect rounding was used, and I'm using the correct rounding.”  That's just plain wrong, though most programmers appear to be unaware of this.  But probably the most important reason programmers keep using binary floating point numbers is because it's easy, and often the problems with that choice don't show up until after a software system has been in use for a while.

The fact is that binary floating point numbers cannot represent all real world numbers with sufficient accuracy for all uses.  It's not a rounding problem, it can't be “worked around” – they're simply not up to the job.  There are many alternative ways to represent numbers in a computer that do not have any of the problems of binary floating point.  These methods are a teensy bit harder to use in most programming languages, and not at all harder in some.  There is, in most cases, a small performance penalty – irrelevant in all but the most compute-intensive algorithms.

So be careful with those binary floating point numbers, y'all...