Clock Arithmetic Still Hard

Clock or modular arithmetic is hard. Take a look at the two code snippets below. Both seem reasonable integer comparison functions modeled after strcmp(). However, the left one contains an overflow bug.

BuggyIntCmp ClassicIntCmp

I have thirty odd years of programming experience, yet I had to be pointed out the bug. The left snippet looks obviously wrong to me, now. It’s like claiming that we go back in time if the short hand of a clock moves more than 6 hours. Ridiculous. (And, no, intermediate casting to long won’t help.) Just try a few extreme cases using INT_MIN, for example. Clock arithmetic is hard because if the modulus is sufficiently large we tend to ignore it. SimplifiedIntCmp So, if you have to go against the first directive, if you don’t trust the -O4 option, or if you just have to show off how brilliant you are, use something like the C code on the right. It won’t bring you much, but at least it does not contain an overflow bug. Though it might contain an other one, or show a incompatibility in your compiler. But that is left as an exercise to the reader.

3 Comments

  1. Careful, don’t do this:
    int intcmp(unsigned int a, unsigned int b)
    {
    return (a>b) – (a<b);
    }

  2. (translation of that comment is of course “turn on all your compiler warnings” 😉

  3. (translation of that comment is of course “turn on all your compiler warnings” 😉