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.64596371106x3 +
0.07968967928x5 - 0.00467376557x7 + 0.00015148419x9
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!!!
No comments:
Post a Comment