Embracing the suck

This is a followup to The Rollover of Doom: a Trap for Good Programmers. 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.”

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.

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 detecting that a rollover has occurred. 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).

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 undetermined. (Remember that I specified “detects rollover cases as often as possible, and explain which cases you cannot detect.”) There are returned dates for which you will not be able to tell if rollover has occurred. You cannot get to working code until you embrace this suck.

A&D regular Jay Maynard phoned me and said “You…you did a Kobayashi Maru 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 change 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.

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

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

Wrong, semicolon-breath! Remember, by hypothesis you’ve been handed the date after it may have been clobbered by rollover. 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.)

“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 set that clock. I’ll return to this issue shortly (cue ominous background music).

Look, I did warn you it was ugly. This problem is really a test of lateral-thinking ability: can you Kobayashi-Maru it?

But we are not yet at the end of the suck (ominous background music wells in volume).

Another A&D regular, Patrick Maupin, Koybayashi-Maru’d the problem in a different way than I did. He pointed out that, if 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.

I shrugged and started writing code anyway. First step: hack up a script to parse the U.S. Naval Observatory’s leap-second history. 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).

As I was doing this, I ran across the Trimble patent. 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 not 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.

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 past data. I didn’t like that abrupt change in the trend line in ’98, either; it suggested that there could well be enough randomness at decadal scales to break the estimation.

And then….I looked through our device drivers, just to check, and discovered that for older firmware revs of the most widely-used GPS receiver chip on the market…we can’t get leap second out of it. So much for that 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.)

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.

In this case, embracing the suck isn’t so bad.

29 comments

  1. Why not get the year from the system clock and the rest from GPS? Clock skew on the order of minutes is common and worth fixing, even if you choke on the rare case.

    If you want to be defensive, get the year/month/day from the system clock, and only set the time if they are compatible with GPS’s data.

    1. >Why not get the year from the system clock and the rest from GPS? Clock skew on the order of minutes is common and worth fixing, even if you choke on the rare case.

      That’s almost how it works now; we get century from the system clock. We’ll probably move to doing as you suggest.

  2. Sensing a trick question, I got it right the first time. What does it mean if you don’t get caught in a trap for good programmers….?

    1. >What does it mean if you don’t get caught in a trap for good programmers….?

      Well, it could mean that your capacity for lateral thinking – your ability to spot and question the hidden premise – is actually a match for or even stronger than your tendency to obsess about doing the Right Thing. I think that sort of ability is essential to lift you out of the category of “gifted” into “genius”, whether we’re talking programming or anything else

      Or it could mean you don’t give a shit about the Right Thing and settle for sleazy, easy solutions. I don’t know you, so I can’t tell :-).

  3. Beware of reading a patent and deciding you don’t infringe, though. It’s settled patent law that only a patent attorney is competent to make that decision. Anyone else who does it and is found by a court to be wrong automatically becomes liable for triple damages as a willful infringer.

    This, of course, flies in the face of the stated purpose of the patent system. It does, however, help what has become the true purpose of the patent system: enriching patent lawyers.

  4. There’s another piece information that’s hidden. If you see the leap second counter change, you know that it is either 1st of January or the 1st of July (although other months may be used in future). This didn’t seem to be particularly useful.

    The way I approach these sorts of problems is to alternate between trying to prove it impossible and trying to prove it possible. I find I tend to extract new truth on each iteration.

    You could probably fill in the white strips with Patrick’s method.

  5. Jay: Would you please provide a reference or case name which settles that “only a patent attorney is competent to make that decision”? I’d love to have another well-defined data point when I next talk to my CongressCritters. If I’m not legally competent to read or interpret a patent filed in a an area in which I’m “skilled in the art”, then I’m not certain that there is any part of the system which is working as it has been declared it is supposed to.

  6. What the hell are you talking about here?

    Wrong, semicolon-breath! Remember, by hypothesis you’ve been handed the date after it may have been clobbered by rollover. 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”.

    Here’s what you said the algorithm is:

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

    Your table of all recorded leap seconds by definition must be in the past or a few months in the future. Once the device is six months old, there is no “if yes” branch to pursue. It will return “undetermined” every single time. There is some, very important, part of this algorithm that is missing to reconcile these two quotes. I’m too dense to figure it out.

    1. >Your table of all recorded leap seconds by definition must be in the past or a few months in the future. Once the device is six months old, there is no “if yes” branch to pursue. It will return “undetermined” every single time.

      As I already described, sometimes it will return “yes” – rollover detected, because the rollover dropped the date back to a range it can check. Or it will return “undetermined”. You are correct that it can never verify that there has been no rollover for a future date. What you’re missing isn’t magic in the algorithm, it’s that the conditions of the problem don’t include knowing when “now” is. You could, for example, be postprocessing logs from a remote telemetry site.

  7. You could always use the least squares method for GPSes that do provide leap second data, with a fallback to looking at the century in the system clock for GPSes that do not provide leap second data. OTOH, embracing the suck seems to be the right solution here.

    Personally I figured that the problem was not truly solvable without using data from the system clock, and when Patrick Maupin had already gotten what I considered to be close enough, I didn’t bother to come up with a serious solution of my own. As in martial arts, knowing when not to fight is as important knowing how to fight. :)

  8. “Abrupt change in ’98” is 500ing for me, and I’m really curious about that. I’d gotten as far as wondering just how random the leap seconds are and wondering if a projection could be made with some reliability. Random is a continuum, not a binary thing.

    But, ultimately, I’ve also tired of trying to take crappy data and read tea leaves and turn it into good data and my gut instinct from day one would have been to just say that if you can’t be bothered to keep your system clock working, well, sucks to be you. Cutting corners has consequences. There’s no guarantee that bad data can be fixed up and often you just muck things up worse trying. See also the number of ways “fixing up” bad HTML or bad form input turns into injections of various kinds when the input should just have been rejected.

    I’m fully aware of the downsides of that attitude, but I think the downsides of the alternative of “just trying to do something” are almost universally underestimated; people tend to cost out “just doing something” at zero mentally, resulting in a pathological cost/benefit analysis. Always beware the hidden assumptions of zero cost or benefits.

  9. “Abrupt change in ’98? is 500ing for me, and I’m really curious about that. I’d gotten as far as wondering just how random the leap seconds are and wondering if a projection could be made with some reliability

    1972-1983, there was an average of one leap second every year (1972 had 2, 1980 had 0). 1984-1998, there were 10 leap seconds over 15 years; not too different. 1999-2010, there were 2 leap seconds in 12 years.

    What do the scientists tell us? Well, Tom O’Brian, Chief of the Time and Frequency Division at the U.S. National Institution of Standards and Technology, told LiveScience in a 2005 interview that, “In 1999 for reasons still unknown, the rotation of the Earth speeded up a bit.”

    So, you’ve got an fairly radical change in the frequency of leap seconds, and a baseline of 39 years to extrapolate from. 39 years also happens to also be the length of two 10-bit week-count rollovers. How sure are you, given that change, that the average rate of the previous 39 years are a reliable guide to leap-second frequency for the next 39?

    1. >How sure are you, given that change, that the average rate of the previous 39 years are a reliable guide to leap-second frequency for the next 39?

      I, for one, am not.

      >“In 1999 for reasons still unknown, the rotation of the Earth speeded up a bit.”

      That’s not what the numbers say. The numbers say the rate of decrease changed.

  10. Garrett:

    Would you please provide a reference or case name which settles that “only a patent attorney is competent to make that decision”?

    I have none. This is, however, standard advice given to software types in the corporate world. I got it when I was at Compaq, from the patent department there.

  11. “Only a lawyer can tell legal from illegal, and none of them care about justice anymore.”

    From where I stand I call it bad coding. The law is a kludge.

  12. Would you please provide a reference or case name which settles that “only a patent attorney is competent to make that decision”?

    I have none. This is, however, standard advice given to software types in the corporate world. I got it when I was at Compaq, from the patent department there.

    The patent system has a lot of problems, but this particular standard advice gained popularity after 1995, when the federal circuit decided in Markman v. Westman that interpretation of patent claim construction was a matter of law, not a matter of fact.

    This means, among other things, that a judge sitting by himself, without a jury, can decide the meaning and scope of the claims in what is now known as a Markman hearing.

    The judge is supposed to read the claims by themselves, but can rely on extrinsic evidence to familiarize himself with the terms of art. This works reasonably well sometimes, but can lead to drastic injustices in other cases. In any case, this is why you and I are purportedly incapable of reading or writing patent claims.

    If you google for Markman and claim construction and interpretation, you can find several references. Here is one for a start.

  13. You may have misunderstood my point, Steven. I wasn’t saying that this was absolutely a good idea before I looked at the data, I was saying that the mere fact that it is random did not immediately prove it wasn’t utterly impossible, the work still had to be done. The work was done, it’s not possible.

    And I do mean “may” have misunderstood, it’s not clear to me.

  14. This is where I landed (set and use the system clock), and I figured that I must be wrong, because I didn’t solve the problem.

    There is simply not enough data in GPS to do it without having a starting point to put you in a specific week.

    Could you put an additional receiver in to grab the time from WWV/WWVH? Is there something that could be used in other parts of the world to make it world-wide?

    The original problem never said we couldn’t use other available time transmissions.

  15. and yes, I realize after hitting post that we’re talking about historical devices that won’t have WWV receivers in them. So you can ignore/flame as you see fit.

  16. @brian:

    Could you put an additional receiver in to grab the time from WWV/WWVH? Is there something that could be used in other parts of the world to make it world-wide?

    Actually, you bring up an important additional point that applications and systems programmers often forget about. The ultimate functionality of a given system isn’t really decided by the application developer or even by the developer of the operating system; that responsibility lies with the systems integrator. To think otherwise is the height of arrogance.

    IOW, I think it’s important that for any given use case, a given application should allow for more than one way to implement that use case where multiple possibilities exist. I believe this is why hackers tend to make their programs a bit like a Swiss Army Knife that can plug into various other software and hardware (sub)systems.

  17. An interesting problem, and a nice case of “There is no spoon”. At first, I tried to do what many others tried, try to calculate the date using the table of leap seconds as a rollover detector. When I realized, and later read, that such a path was doomed to failure, I considered a curve fit for leap seconds. After some more thought, and having other more interesting projects to work on, I finally threw my hands up in disgust. I keep a grass-script ‘mu’ (see here and here), in my own hand, on my white board at work for problems such as these, reminding me to question my assumptions, but failed to apply it here. I must meditate on it more in the future.

  18. > That’s not what the numbers say. The numbers say the rate of decrease changed.

    So now we know when the oceans stopped rising as strongly, thus slowing the rate of increase in the gyradius of the earth!

    Either that, or the Romulans have been moving the moon again…

  19. I gave up on trying to solve it before. If I’d had to, (say it was me in the hot seat to deliver working code,) I’d probably have sweat blood for a bit, then tried coming up with some hypothetical dates with different combinations of rollovers/brokenness and leap-second table availability, and tried to divine a pattern. Even after reading the blog post, I guess I’m not bright enough to tell if that would have worked.

  20. “Only a lawyer can tell legal from illegal, and none of them care about justice anymore.”

    From where I stand I call it bad coding. The law is a kludge.

    Said the old grizzled COBOL programmer/senior partner at major law firm:

    “You call it a kludge, I call it job security! Hee hee hee!”

  21. “That’s not what the numbers say. The numbers say the rate of decrease changed.”

    No, what the numbers say is that the amount by which the speed was less than 86400 s/d [i.e. the rate of positive leap seconds] went down. Which is the same thing as saying the speed went up.

Leave a Reply to Ask Bjørn Hansen Cancel reply

Your email address will not be published. Required fields are marked *