Geek Nostalgia...

Update: Mere minutes after I published this, reader, friend, and former colleague Doug W. wrote to say: “Sorry to out-geek you, but no way is this equation (from your blog today) correct.”  Out-geek me he did – and he caught a typo.  I've now fixed it (the pi / 2 term on the left)...

Long ago – before, I'm afraid, many of my readers were born – I was given the task of writing a “program library” that calculated a particular set of functions to a specified accuracy within a specified amount of (computational) time.  These included trigonometric functions, logarithmic functions, and a few others.

Initially I looked at Taylor series that converged on the functions I needed.  These are series with an infinite number of terms, each of which is trivially related to the terms preceding.  In other words, they're easy to compute.  It quickly became obvious, though, that the Taylor series converged too slowly to be useful for my problem – the computers I was writing the program for (Univac CP-642Bs) were just too slow.

What to do?  I did a lot of reading at libraries – first the San Francisco City library, then the technical library on the Navy base I was stationed at (Mare Island).  In the Navy's library I accidentally ran across a slim volume titled Approximations for Digital Computers, by Cecil Hastings.  As the preceding link shows, this book is well represented on the web even today (including free PDF and eBook downloads), despite it's 1954 publication date.

The book was a revelation for me, and a direct solution to my problem.  It contained numerous finite (and usually quite short!) polynomials that approximated most of the functions I needed, usually to better than the accuracy I needed.  Even better, for each of the approximations an error curve was included – and that could be directly used to improve the approximation even further.  Best of all, the first half of the book explains exactly how these approximations were created – so I could create my own approximations for the few that Hastings didn't already do.

Just as an example, here's the Hastings approximation for sin(x) that produces sines accurate to better than 1 part in 10^-7:, for angle in radians, -1 <= x <= 1:

sin((pi/2)x) = 1.57079631847x - 0.64596371106x³ +
             0.07968967928x⁵ - 0.00467376557x⁷ + 0.00015148419x⁹

If you're a programmer, you'll see the beauty of that approximation right away. First of all, it's a finite series – no iteration to reduce errors is needed.  You just compute the five terms and add them up, and bada bing, bada boom, you've got your answer.  Second of all, the computation is easy – even for the ancient computers I was working with.

With that little book, and a couple weeks of work, I successfully implemented that programming library.  About a week after I delivered it (this would have been in 1973), a full Commander whom I didn't know dragged me out of a cryptography class and into a meeting with several Captains and a Rear Admiral.  At the time, I was a lowly E-5 (Petty Officer Second Class, in Navy parlance).  I had very little experience with officers of any rank, and absolutely none with this level.  I was terrified, and in spite of their best efforts,  only slightly put at ease by their smiles and evident good will.

This group of scary people told me why they'd dragged me up there.  They had given this problem (of writing that library) to two companies who had failed to deliver a usable result after more than a year of effort.  The second company declared it impossible.  The officers decided to give it to the school as a classroom exercise, thinking that it would make a good challenge to humble students upon.  The instructors, thinking it was for real, gave it to three of their best pupils, myself included – but as an assignment, not a challenge.  We all thought we had to deliver, or suffer some dire consequence.  The worst possible consequence was really, really bad – students flunking out of this school were sent to another school at Mare Island: the “swift boat” school, whose graduates went on patrols on Vietnam's rivers, and suffered the highest casualty rate of any of the U.S. Armed Forces.

So when those officers got back a piece of code after just three weeks that claimed to solve the problem, they were skeptical.  They tested it, and found that it exceeded both their accuracy specification and (especially) their performance specification.  They did find a couple of little bugs, but they were obviously just little bugs, not major fails.   So they dragged me out of class to explain to them just what magic I was using.

I happened to have the Hastings book with me, so I just whipped it out and showed them.  To say they were stunned – especially after I told them where I found the book – would be a major understatement.  Now they knew I wasn't a magician, but just a stubborn guy familiar with libraries :)

The best part of all, for me, was that they wanted to deploy this code as part of an upgrade to the Navy Tactical Data System (NTDS) – actual production code being used on our warships.  They pulled me out of class for two months (I just dropped back in on the next class cycle), and I worked with a hotshot Lt. Cmdr programmer and two Univac contractors to get my code tested and “production ready”.  That was the very first piece of production code I ever wrote, and I still get a warm feeling when I remember producing the master tape (for that was how we distributed code back then :)

Every few years since then, I've searched for a copy of Hastings' book.  Last time was probably ten years ago, when I bid on eBay for a copy – and lost, to someone willing to pay $200 for it.  A couple weeks ago I looked again – and found several copies available through Amazon's used book sources.  I ordered one that was in good condition, paying just $12 (including shipping!).  Today it arrived.

The copy I had used in 1973 was library-bound; the one I just received had the publisher's binding and the slip cover on it – so I didn't recognize the cover at all.  But the inside of the book – oh, my, that brought back good memories in a hurry.  Skimming Chapter 5, on Chebyshev polynomials, immediately brought back the sense of excitement, and even of adventure, that I felt on first reading this chapter.  I knew then even less mathematics than I do today, and that chapter was quite challenging for me to understand.  But once I did understand it, woo hoo!  “Revelatory” is the right word.

Awesome geek nostalgia moment!!!

Wat?

Courtesy of friend, reader, and former colleague Doug S., this lovely little example of geek humor.  It appears to be a presentation by Gary Bernhardt at CodeMash 2012.

Javapocalypse...

Oracle Drops the Other Shoe – Right on Top of Java...

I've been programming almost exclusively in the Java programming language for over 10 years.  Like many other Java programmers, ever since Oracle bought Sun (the previous owner of Java), I've been watching to see what Oracle would do to start making money on Java.  It's not in Oracle's corporate DNA to support something like Java for the good of humanity – which is, essentially, why Oracle bought Sun and not the other way around :)

Now we see the beginning, I suspect, of the multiple “incentives” Oracle is going to provide for Java developers to purchase a support contract from Oracle.  There are a lot of Java developers in the world – over a million, by some counts.  If even a small fraction of those bought support contracts, Larry would have an interesting revenue stream.

I'd bet that this timezone data is but the first of many such changes to come, and that soon the only way you can be a serious developer using Oracle Java is to pay a “tax” to Oracle.  What will be interesting to see is what happens next.  Will the Java community just complain and pay up?  Or will they fork the (still open source) Java code base and create a real open source community, perhaps with another, more altruistic sponsor?

Hexagonal Grids...

Here's an interesting discussion about using hexagonal grids in software games, though the results are more generally useful.  The authors have worked through details like coordinate systems, distances, rotations, etc.

A Beautiful Piece of Code...

Not only is this beautiful code, but it involves regular expressions, was written by Rob Pike, and is explained by Brian Kernighan (two of my heroes while learning to program).  Awesome geekery!

Geek One-Liners...

Via reader Simi L.:

• I used to work in a fire hydrant factory. You couldn't park anywhere near the place.
• Last week, I went to a furniture store to look for a decaffeinated coffee table. They couldn't help me.
• What's another word for "thesaurus"?
• When I get real bored, I like to drive downtown and get a great parking spot, then sit in my car and count how many people ask if I'm leaving.
• When I was a kid, we had a quicksand box in the backyard. I was an only child . . . eventually.
• I bought some batteries, but they weren't included. So I had to buy them again.
• For my birthday I got a humidifier and a dehumidifier. I put them in the same room and let them fight it out.
• I have a switch in my apartment that doesn't do anything. Every once in a while I turn it on and off. One day I got a call from a guy in France who said, "Cut it out!"
• I replaced the headlights on my car with strobe lights. Now it looks like I'm the only one moving.
• I wrote a song, but I can't read music. Every time I hear a new song on the radio, I think "Hey, maybe I wrote that."
• I got my driver's license photo taken out of focus on purpose. Now when I get pulled over the cop looks at it (moving it nearer and farther, trying to see it clearly)... and says, "Here, you can go."
• I went to a general store, but they wouldn't let me buy anything specific.
• I turned my air conditioner the other way around, and it got cold out. The weatherman said, "I don't understand it. It was supposed to be 80 degrees out today." I said "Oops . . ."
• I put contact lenses in my dog's eyes. They had little pictures of cats on them. Then I took one out and he ran around in circles.
• I spilled Spot remover on my dog. Now he's gone.
• My neighbor has a circular driveway. He can't get out.
• I bought some powdered water, but I didn't know what to add.
• I put instant coffee in a microwave and almost went back in time.
• I have an answering machine in my car. It says, "I'm home now, but leave a message and I'll call when I'm out."
• I bought a house on a one-way dead-end road. I don't know how I got there.
• I have a hobby. I have the world's largest collection of sea shells. I keep it scattered on beaches all over the world. Maybe you've seen some of it.
• I Xeroxed a mirror. Now I have an extra Xerox machine.
• Last week I forgot how to ride a bicycle.
• My school colors were clear.
• I stayed in a really old hotel last night. They sent me a wakeup letter.
• I'm taking La maze classes. I'm not having a baby, I'm just having trouble breathing.
• When I was in high school, I got in trouble with my girlfriend's Dad. He said, "I want my daughter back by 8:15." I said, "The middle of August? Cool!"
• My girlfriend's weird. One day she asked me, "If you could know how and when you were going to die, would you want to know?" I said, "No." She said, "Okay, forget it."
• I went for a walk last night and she asked me how long I was going to be gone. I said, "The whole time."
• My buddy got busted for counterfeiting. He was making pennies. They caught him because he was putting the heads and tails on the wrong sides.
• He's in a minimum security prison now; he's on a whiffle-ball and chain.
• Hermits have no peer pressure.
• Whenever I think of the past, it brings back so many memories .
• There's a fine line between fishing and just standing on the shore like an idiot.
• How much deeper would the ocean be if sponges didn't live there?
• Did Washington just flash a quarter for his ID?
• I just got skylights put in my place. The people who live above me are furious.
• Imagine if birds were tickled by feathers.
• I remember when the candle shop burned down. Everyone stood around singing "Happy Birthday".
• I accidentally installed the deer whistles on my car backwards. Now everywhere I go, I'm chased by a herd of deer.
• I got stopped by a cop the other day. He said, "Why'd you run that stop sign?" I said, "Because I don't believe everything I read."
• It doesn't matter what temperature a room is, it's always room temperature.
• Yesterday, my eyeglass prescription ran out.
• I'm a peripheral visionary.
• I make my own water - two glasses of H, one glass of O.
• Ballerinas are always on their toes. Why don't they just get taller ballerinas?
• The other day, I went to a tourist information booth and asked, "Tell me about some of the people who were here last year."
• Why in a country of free speech, are there phone bills?

Geek Humor...

Passed along by friend and reader Simon M.:

DIP...

“DIP” (or Dependency Inversion Principle) sounds very odd to me...

Flat UI Icons...

A nice collection of collections...

Programmer Jokes...

From StackOverflow.  Some of these are wonderful!  Some you really need to be a programmer to understand...

Floppy Decoding Code for the 6502...

Here's a wonderful post talking about the process of writing code that decoded floppy disk data read in realtime, on a 6502 processor.  Readers who are geekly and of a certain age will identify with this.  Younger folks will probably just shake their heads at the lameness of their elders :)

What struck me about this post was the way the author brings back the challenges of programming on those old, slow microprocessors – and the way we engineers glommed onto tricks like the “illegal” op codes (almost every microprocessor had them).  I never wrote any code that decoded floppy data, but I did many other similarly challenging things.  A couple that spring to mind: variable-slew stepper motor control (to speed up and quieten floppy disk positioners) and realtime FSK radioteletype decoding, with multipath and single-side dropout handling.  Both of these would be trivial today; your average smartphone could do it in a high-level language.  But back then, the microprocessors could only do things like that if you pulled out every trick in the book, and perhaps invented a new trick or two along the way...

The 12 Most Controversial Math Problems...

Upon seeing this headline, I clicked to see what I thought would be an article on problems that challenged mathematicians, but that's not at all what this article is about.  Instead, it's about math problems that challenge ordinary people's understanding – and it's quite well explained and illustrated.  About half of these problems are some I'd run across before as brain teasers; the other half were new to me.  All were interesting and illuminating.  Recommended reading!

Go 1.1...

A new release of Google's Go programming language...

Strange Programming Language Features...

Fascinating thread on StackExchange, if you're of a geekly bent...

Picking CPU Registers...

On many CPU architectures, especially older ones, there are a relatively small number (sometimes only two or three!) of CPU registers.  Modern CPUs are sometimes much more symmetric with respect to register set architecture.  If you're an assembly language programmer, you know all about registers.  If you're not, you can think of them as particularly fast memory locations that machine-level computer instructions can access directly (that is, without having a memory address).

This characteristic of a small number of registers wasn't limited to microprocessors; all the early “mainframe” and “mini” computers were built the same way.  The first mainframe computer I worked with was a Univac CP-642A, and if I remember correctly it had just four registers: A, Q, I, and the program counter.  All of the subsequent mainframes and minis I worked with were also machines with limited register sets, with some of the most modern of them having a couple dozen registers.  Similarly, all the early single-chip microcomputers I worked with had very limited register sets as well.  The TI 99000 attempted to move a lot of register functionality into memory locations, but even it had over a dozen specialized registers.

All of these machines with limited register sets shared another characteristic: to various degrees the registers were specialized.  One register might have special capabilities for increment and decrement.  Another might be specially usable as an index into memory.  Another might be part of double-precision multiply and divide operands.  Or perhaps a couple of registers might have a special “swap” capability.  This sort of thing was quite normal in those early CPUs, and the special register set capabilities were directly reflected in the machine-level instruction sets.

William Swanson has a nice article up exploring the Intel 8086 register set architecture in quite a bit of detail.  It's a specific case of this more general design characteristic.  Reading this brought back a lot of memories, both from the distant past :) and more recently, with PIC single-chip systems...

Chart.js is Back!

This very useful tool for building client-side charts using JavaScript and the HTML5 canvas element was taken down last week over a copyright issue.  Now it's back up – I'm not sure why, but I'm glad to see it!

Backbone.js – 1.0 Released...

Backbone.js is a very popular JavaScript framework, used in many of today's busiest websites.  Today it has it's first official “one point oh” release.  Congratulations!

Emotions on Demand...

This is a little creepy...

Submarine Cables...

Today's Internet is very dependent on undersea (submarine) cables that link various parts of the world together.  We can seamlessly link between web sites in various countries only because these cables exist.  Less obvious, but economically perhaps even more importantly, these cables enable many other kinds of communications traffic: email, voice phone, fax, instant messaging, and much, much more.  They are, these days, vital conduits of economic activity – it's hard to imagine any kind of business that isn't dependent on them.

These cables (see diagram at right) are the most concentrated information conduits in the world.  When one of them breaks, the impact is large and immediate.  In some cases around the world, a single submarine cable is the only high-bandwidth link between some region and the rest of the world.  When one of those links breaks, large numbers of people are sawed off from the rest of the world – no web, no email, no phones, just ... crickets.

Here's a nice explanation of all this...