Tuesday, August 13, 2013

Book Review...

I've just finished reading The Riddle of the Labyrinth: The Quest to Crack an Ancient Code, by Margalit Fox.  It's the story of the decoding of Linear B script, which was much more of an accomplishment than many today remember.  The first clay tablets bearing Linear B script were discovered in the late 1800s, and the form of the tablets made it crystal clear that Linear B was a script.  Prior to that, objects were found with Linear B script on them (especially seals), but nobody recognized the odd symbols as a script; they were thought to be merely decoration.

For over 50 years after the tablets were discovered – until Michael Ventris' key breakthrough in 1953 – nobody knew how to interpret the Linear B script.  For most of that period, even the kind of script Linear B was (alphabetic, syllabic, or logographic) was unknown.  And for that entire period, the language that the script was recording was unknown.

I first read about Linear B something like thirty years ago, and I've long wanted to learn more about how it was decoded.  On the face of it, the problem seemed insurmountable to me: an unknown script, recording an unknown language, and no equivalent of the Rosetta Stone to help.  How in the world could someone decode that?

Like many such achievements, the decipherment involved several people, much cleverness, and had several breakthrough “Ah ha!” moments.  One of the main players (Alice Kober) got little contemporaneous credit.  There were amateurs, professionals, and academic hobbyists.  At least one curmudgeon was present.  There was a borderline lunatic, much obsession, and a possible suicide.  And of course there were academic rivalries and jealousies, and abuse of power.  In other words, it's a pretty typical story of science, with lots of human interest.

I was quite satisfied with the book, especially for telling the stories of all the players in what appears to be an even and fair-minded way.  I wish it had a bit more detail about how the decipherment was accomplished, but there is enough there to give the reader the basic idea without too much work.

Recommended for anyone interested in the history of science, or in ancient languages...

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.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!!!

Transgender Children...

California Governor Gerry “Moonbeam” Brown has signed into law a bill (AB-1266) protecting transgender children enrolled in public schools.  Provisions in the bill allow transgender children to choose which gender's restrooms and locker rooms they will use, and choose which gender sports teams they'll participate in.

What does this actually mean?

The bill uses the term “gender identity”, which I found several definitions for out on the web – similar, but not identical.  The basic notion is that your gender identity is that gender that you deeply feel you are – even if that's different than your physical gender.  I couldn't find anything that defined (under California law) how one gets a particular gender identity under the law.  It could be that you simply declare it, or it could be that you have to have a psychiatric professional certify it.  I have no idea.

There really are people out there whose gender identity is different than their actual physical gender – transgendered people.  I've known two in my life.  The first was born a man (and that's how I first new him), but who thought of himself as a woman.  “Robert” became “Robin” while (s)he was an employee of mine.  That was quite an experience, on many levels.  The other was a person born as a woman (coincidentally, “Robin”) who thought of herself as a man.  She became “Al” several years before I first met him.  In this case, Al was an employee of the company I was CEO of, and I had another male employee who complained about Al's inappropriate advances.  Yes, transgender people can also be gay, as I got a quick education on.

I relate the preceding mainly to illustrate through my own experience that transgender people exist.  I have no doubt, personally, of the reality of this condition.  I also have no doubt that some transgender children exist, and in this day and age, they might well be recognized at a young age. 

So I don't doubt the sincerity of the bill's authors, nor the reality of the issue they address.

But I, like many others, am worried about the bill's imposition of potentially very uncomfortable situations on young people who already have enough social challenges.  Again like many others, I worry about its potential for abuse.

First the uncomfortable situations.  Imagine a 16 year old person who is physically male, but identifies as female.  That person, under AB-1266, has the right to choose to use the girl's restrooms and the girls locker room.  I suspect that even in these “enlightened”  times, there are still girls of high school age who are uncomfortable in the presence of nude men, and who would be uncomfortable being nude in the presence of a man (nude or not).  Basically this bill says “tough” to those girls (or the boys in an opposite situation, though the discomfort potential there is admittedly far lower :). 

Then there's the potential for abuse.  This mainly rests upon the requirements imposed by California law on establishing gender identity.  If those requirements are very loose – say, simply the declaration of the student – then it doesn't take much imagination to contrive situations where a horny and curious boy (that would be all of them) establishes gender identity as a girl and thereby gains admittance to about 80% of all teenage boy sexual fantasies.  Because I couldn't find the rules by which one establishes gender identity (under the law), I can't assess the probability of abuse.  I can imagine a fairly “tight” set of rules that would make it difficult for abuse to occur, but this is California; there's no telling what those idiots in Sacramento have actually done.  They probably don't know themselves!

Late Night Catechism...

Via my mom, these clips from Late Night Catechism – one of the longest running plays ever: