21 lines
7.1 KiB
Plaintext
21 lines
7.1 KiB
Plaintext
Embracing the suck
|
|
<p>This is a followup to <a href="http://esr.ibiblio.org/?p=2869">The Rollover of Doom: a Trap for Good Programmers</a>. That post ended “This problem is a Chinese finger-trap for careful and conscientious programmers. The better you are, the worse this problem is likely to hurt your brain. Embrace the suck.”</p>
|
|
<p>That last phrase is a take on a military objurgation which translates as “The situation is bad. Deal with it.” Well, my friends, I am about to tell you how bad the GPS rollover situation really is.</p>
|
|
<p><span id="more-2882"></span></p>
|
|
<p>First, my solution to the Chinese finger-trap. Good programmers – especially good programmers who are bright but prone to linear thinking – hurt their brains on this problem in two ways. First, they try to solve a more difficult problem: disambiguating the GPS date by deducing which rollover period we are in, as opposed to simply <em>detecting that a rollover has occurred</em>. Once they’ve realized they can’t solve the harder problem with the information given, they look for a way to code a rollover detector that always return true (rollover has occurred) or false (rollover has not occurred).</p>
|
|
<p>The second assumption is the killer. You can’t do it; there isn’t enough information supplied. You jump out of the “conceptual box” I referred to by recognizing that the rollover detector must return three values: true, false, and <em>undetermined</em>. (Remember that I specified “detects rollover cases as often as possible, and explain which cases you cannot detect.”) There are returned dates for which <em>you will not be able to tell if rollover has occurred</em>. You cannot get to working code until you embrace this suck.</p>
|
|
<p>A&D regular Jay Maynard phoned me and said “You…you did a <a href="http://en.wikipedia.org/wiki/Kobayashi_Maru">Kobayashi Maru</a> on the problem!” He’s right. Often the right answer to an unsolvable conundrum, if you’re doing engineering rather than theory, is to grok that you got the conditions of the problem wrong…or to <em>change</em> them. Tellingly, of the three or four people I bounced this problem off, the one who grokked the most rapidly is not a programmer but a control systems engineer, the kind of guy who designs factory wiring for a living.</p>
|
|
<p>Here’s the ugly but correct algorithm. Look at the date. Look at the table of all recorded leap seconds. Is the date within the table range? If yes, then check to see if its entry matches the leap second you see – that’s your true or false answer. If no, then return ‘undetermined’.</p>
|
|
<p>If you are a programmer, you may well be spluttering in outrage at this point. You may be asking “What the hell good is that? You can’t check dates past the end of the table! You can only validate the <em>past!</p>
|
|
<p></em><em>Wrong</em>, semicolon-breath! Remember, by hypothesis you’ve been handed the date <em>after it may have been clobbered by rollover</em>. Each input value corresponds to a countable infinity of future dates. Think of the set of future time values as being sort of striped like an old-fashioned barber pole; the algorithm will return “true” or “false” over the red parts, with white gaps where it returns “undetermined”. Each red/white pair of stripes will have exactly the width of a rollover period. (Pinning down positions and relative widths would involve painful details about hidden magic numbers and logic in the receiver firmware. The above is a good enough first approximation.)</p>
|
|
<p>“Er, wait.” you say. “Won’t all future dates return either rolled-over or or undetermined?” Why, yes, that’s true. But what’s the future? I did not say you could have the system clock as an input to your algorithm. I left that out deliberately; ideally, we’d like to be able to use the GPS to <em>set</em> that clock. I’ll return to this issue shortly (cue ominous background music).</p>
|
|
<p>Look, I did warn you it was ugly. This problem is really a test of lateral-thinking ability: can you Kobayashi-Maru it?</p>
|
|
<p>But we are not yet at the end of the suck (ominous background music wells in volume).</p>
|
|
<p>Another A&D regular, Patrick Maupin, Koybayashi-Maru’d the problem in a different way than I did. He pointed out that, <em>if</em> you can get a year estimate within 512 weeks from the leap-second input, there’s a way to interpret a week/tow pair that gives you a firm date. Someone else pointed out (at about the same time I was getting there myself) that a curve-fit to the historical leap-second data might give us good enough confidence in predicting years of future leap seconds. Then somebody else muttered that Trimble, a GPS vendor, has a patent on a similar technique.</p>
|
|
<p>I shrugged and started writing code anyway. First step: hack up a script to parse the U.S. Naval Observatory’s <a href="ftp://maia.usno.navy.mil/ser7/tai-utc.dat">leap-second history</a>. Run a least-squares fit on the data and see what the residuals look like (you don’t want a higher-order curve fit on random data with a strong central tendency, as it would tend to over-weight outliers).</p>
|
|
<p>As I was doing this, I ran across the <a href="http://leapsecond.com/notes/gpswnro.htm#patent">Trimble patent</a>. To say this is “junk” would be to wallow in understatement. There’s prior art, it failed the obviousness test, over-broad, badly drafted – if there’s any way this patent is <em>not</em> utterly bogus, I couldn’t find it. Fuck ‘em; if they send me a C&D I can tell them to stick it where the sun don’t shine.</p>
|
|
<p>Um, but. Turned out there were two problems between me and a patent fight. The first was that the maximum residual on my least-squares fit was 215 weeks – close enough to 512 to make me nervous and that’s only on the <em>past</em> data. I didn’t like that <a href="http://esr.ibiblio.org/wp-content/uploads/2011/01/leapseconds.png">abrupt change in the trend line in ’98</a>, either; it suggested that there could well be enough randomness at decadal scales to break the estimation.</p>
|
|
<p>And then….I looked through our device drivers, just to check, and discovered that for older firmware revs of <em>the</em> most widely-used GPS receiver chip on the market…we can’t get leap second out of it. So much for <em>that</em> idea. In fact, it turns out there is only one time reference we have reliably available; the host-system clock. (Ominous background music reaches a thundering crescendo.)</p>
|
|
<p>Well, on the one hand, this means we can forget about using the GPS to set the system clock. On the other hand, life is now much simpler. Since we must rely on the system clock anyway, all the estimation stuff goes out the window, and the logic for determining the current rollover period is near trivial. </p>
|
|
<p>In this case, embracing the suck isn’t so bad.</p>
|