Identifying Leap Years (2020) | Hacker News Reader

Identifying Leap Years (2020)

davecturner.github.io

28 pointsg0xA52A2A6 comments

Fun maths, especially computing the inverse of 25 in Z/65536Z!

As the article mentions, you need a slightly different calculation in the period between 45 BC and 1582 AD -- the rule about 400 didn't exist in the Julian calendar in force then. Before 45 BC, and in non-Roman-based calendars, it gets even more complicated with intercalary months and postponing New Year's and such.

But surely in all but the tiniest fraction of cases, you only care about years after 1582, and years that are no more than a few centuries in the future. There are only 223 leap years from 1582-2500 (I checked with ChatGPT so that number must be right!) A binary search of an ordered 223-item list would require at most 8 comparisons, and if you don't mind a little more space, you could just store all 919 of those years in a list and look up the answer directly. Wouldn't either be faster than any of these methods (and clearer)?

The problem is, should you take 1582, 1752, or some other year for the cutoff? If you receive a bare date from anywhere within the Gregorian calendar transition, there's no foolproof way to know which calendar it's using. Better to treat dates that old as the social problem that they are, and not try to decree a one true interpretation that will fall flat in most contexts.

(And if you do need to interpret old dates, consider adding explicit calendar-type annotations to your dates, and especially make sure they align with the calendar(s) your sources are truly using.)

Does a compiler use special cases for division by two (and other integers as well) that it implements as single bitwise operations? This seems like a lot of work to scan through all mathematical operations. Is that why compiling code takes so long sometimes?

They can, yes. I recommend playing around with code at https://godbolt.org. Here's an example using division:

https://godbolt.org/z/xqebM6d11

That code is simple, just divides the argument by a constant. The linked version divides by 32, note the sar eax, 5 instruction, that's the actual division computation. Play around with other constants and you'll get other results (including multiply/shift instruction combinations for non-power of two constants).

I tried implementing the four versions:

16bit: https://gcc.godbolt.org/z/6G38YxcGr

32bit: https://gcc.godbolt.org/z/vEzf9h1jo

I thought it's interesting how "div" is used in 16bit versions, whereas for 32bit versions the compiler optimized all of them to use only imul.

We need more languages with "moreover" as a keyword.

Reply on news.ycombinator.com