from Hacker News

Identifying Leap Years (2020)

by g0xA52A2A on 6/22/24, 11:44 AM with 6 comments

• by squirrel on 6/23/24, 3:24 PM

  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)?

• by tppiotrowski on 6/23/24, 2:53 PM

  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?

• by omoikane on 6/23/24, 4:58 PM

  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.

• by bradfitz on 6/23/24, 2:33 PM

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