Thursday, June 15, 2017

Bikeshedding leap years

Darn it, I fell into the trap. An early exercise in Python at wants a function that in Haskell would have the type Int -> Bool and indicate whether a year is a leap year (under Gregorian rules, ignoring when various locales made the switch to keep it simple).

Some submissions are from people not yet comfortable with assigning/returning Booleans other than the constants True or False, or maybe not comfortable with the lazy nature of Python's and and or. Their versions are full of if statements. I bashed out
def is_leap_year(year): return year % (400 if year % 100 == 0 else 4) == 0
and it worked fine... but then I fell in. How about
return year % 16 == 0 if year % 25 == 0 else year % 4 == 0
Nah... no need to make the next guy, who could be me, do the prime factorization of 100 again and figure out how that ties to the leap year rules? OK, here's one way to look at it...
return (year // 100 if year % 100 == 0 else year) % 4 == 0
i.e. on century boundaries, the century has to be divisible by four, otherwise the year has to be. Well, that's one way to look at it, but one that doesn't go with the definition as clearly as one would like...

...and then the path of premature optimization that Knuth warns against beckoned.
return year % 4 == 0 and (year % 100 != 0 or year % 400 == 0)
The idea: three fourths of numbers get ruled out by a check for divisibility by four, which can be done cheaply if the compiler or interpreter notice. (That works for any power of two, not just four, which with another nod to factorization means one could write
return year % 4 == 0 and (year % 100 != 0 or year % 16 == 0)
which means, if you're lucky, only doing one divisibility check with an actual divide.)

Final decision? Leave it alone

A flashback and analogy

You've probably heard about how the notion of sum types (e.g. Algol 68 union s, Rust enum s, Haskell type s) and product types (e.g. tup...