A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards) (opens in new tab)

I've read that not only March was the first month, but the number of months was only ten: winter months did not need to be counted because there was no agricultural work to be done (which was the primary purpose of the calendar). So after the tenth month there was a strange unmapped period.

Also: March is named after the Roman god of war, Mars.

This is because March is when they would begin to mobilize armies for campaigns. The timing is chosen by when winter wheat will be ready for harvest, so soldiers will have nearby high-calorie foot to pilfer while on campaign.

One tricky part of pre-industrial armying is that you can mostly only bring what food you can carry. Things that carry food (e.g. donkeys) require food themselves. So then you have to bring feed as well, which requires more donkeys… etc.

Instead, they would “forage” local areas. If they got there too soon, there is nothing en masse to take!

> explains why the month names have offset to them (sept, oct, nov, dec)

Everything now makes sense, I always wondered why September was the nine month with a 7 prefix.

I thought Sept, Oct, Nov, and Dec were shifted by the addition of July (Julius) and August (Augustus)?

The first article in this blog post series has a little section talking briefly about this history, and there's a representation of this that I think sheds a lot of light on the original design. See the heading "Side-Note on Month / Day Determination" in the below link [1].

Displaying the months like the following helps see the regularity at a glance. Columns 1, 3 and 5 are the long months, others being shorter:

  +-----+-----+-----+-----+-----+
  | 31  | 30  | 31  | 30  | 31  |
  |  I  | II  | III | IV  |  V  |
  | MAR | APR | MAY | JUN | JUL |
  |-----+-----+-----+-----+-----+
  | 31  | 30  | 31  | 30  | 31  |
  | VI  |VII  |VIII | IX  |  X  |
  | AUG | SEP | OCT | NOV | DEC |
  +-----+-----+-----+-----+-----+
  | 31  |28/29|
  | XI  |XII  |
  | Jan | FEB |
  +-----+-----+

> To a person who natively thinks in Roman numerals, remembering that the short months are: II, VII, XII, along with IV & IX would be much easier than the way us modern folks have to memorise it.

[1] https://www.benjoffe.com/fast-date

> not completely coincidentally, March was also the first month of the year in many historical calendars.

And often the last month too. The early modern English calendar began the year on March 25.

This is coincidental in relation to the offset in the names of the months. The Romans started their year in January just like we do today.

(Though in a very broad sense, it's common to begin the year with the new spring. That's the timing of Chinese new year and Persian new year. I believe I've read that the Roman shift two months backward was an administrative reform so that the consuls for the year would have time to prepare for the year's upcoming military campaigns before it was time to march off to war.)

I just added a link to the code with a brief comment. Basically, it simplifies the leap year date calculation. If February is the last month of the year, then the possibly-existing leap day is the last day of the year. If you do it the normal way your calculations for March through December need to know whether February is a leap year. Now none of that is needed. You don’t even need explicit code to calculate whether a given year is a leap year: it’s implicit in the constants 146097, 36524, and 1461.

It's easy to know what day of the year it is because leap days are at the end.

Not so relevant, but some fun history, the Roman calendar did start in March, so tacking on the leap years was done at the finale. This also meant that the root of the words - the "oct" in october means 8 was also the eighth month of the year.

As well as the leap year stuff people have mentioned, there was something else that I've got a vague memory of (from an old SciAm article, IIRC, which was about using March as the first month for calculations) which pointed out that if you use March as 0, you can multiple the month number by (I forget exactly what but it was around 30.4ish?) and, if you round the fraction up, you get the day number of the start of that month and it all works out correctly for the right 31-30-31 etc sequence.

Thanks, that is a good idea. This was originally a blog post series, and the first article gave a bit of an introduction.

When I started the blog series, I expected the first article to be the most noteworthy, with the 2nd and 3rd being lesser supplementary topics.

Now that the 3rd blog post ended up with a much larger result than I was expecting, it stands on its own and could do with some editing as you suggest.

That is an interesting question.

It might also come into play if developing SIMD alternatives for batch date processing, as one can have more lanes with 16-bit. I plan to make a blog post covering SIMD and if 16-bit algorithms have reasonable performance then that will be covered.

Thanks.

I was fortunate enough to be programming on an ARM based device, which meant that the terms (x * 4 + 3) strongly stood out to me as highly inefficient, being 2 cycle prep for the more important division. On x64 computers, those two operations are calculated in only one operation by using the 'LEA' assembly instruction (which I wasn't aware of at the time), and so others using that type of computer might not have felt this step needed any simplification.

I tried everything under the sun to get rid of these steps. The technique noted in the article of using the year 101 BC was for a long time my strongest candidate, you can view the implementation of that attempt at the link below [1].

An epoch of 101 BC still meant that there was extra work required to re-normalise the timeline after the century calculation, but it was only a single addition of 365 in the calculation of `jul`. The explanation of how this works is probably a whole blog post in itself, but now that this algorithm has been discarded it's not worth the time to explain it fully.

I also had the year-modulus-bitshift technique developed at that time, but it couldn't be integrated cleanly with any of my algorithm attempts yet. My plan was to simply document it as an interesting but slower concept.

I don't know what sparked the idea of going backwards other than immersing myself deeply in the problem in my spare time for about a month. It finally came to me one evening, and I thought it was only going to save 1-cycle, but when it also meant the year-modulus-bitshift could be utilised, the entire thing fit together like a glove and the speed collapsed down from 20% time saving to 40%.

[1] https://github.com/benjoffe/fast-date-benchmarks/blob/218356...

That's a mathematical expression, not a C++ expression. And floor here isn't the C++ floor function, it's just describing the usual integer division semantics. The challenge here is that you need 128-bit integers to avoid overflowing.

Could you elaborate on what you mean? I think it's already impossible to accurately turn a future timestamp into a local time, leap seconds or not, because of timezone shenanigans. So I'm probably misunderstanding what you're talking about.

> The question is if the calculation could be made even more efficient by reducing to 32 bits, or maybe even just 16 bits.

This is somewhat moot considering that 64-bits is the native width of most modern computers and Unix time will exceed 32-bits in just 12 years.

Shorter term the Gregorian calendar has the ratio for leap years just a tiny bit wrong which will be a day off by 3000 years or so.

Or set 0 to be the Big Bang and make the type unsigned. Do it the same time we convert all temperature readings to Kelvin.