Live data from Hacker News

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

benjoffe.com

51–60 of 100 posts

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#51
post #33

Earlier quoted context omitted.

That's correct, the Romans had March as the first month of the year, so leap day was the last day of the year and September, October, November and December were the 7th (sept), 8th (oct), ninth (nov) and 10th (dec) months.

June and July used to be Quintilis and Sextilis.

I think Quintilis and Sextilis were renamed to July and August, in honor of Julius and Augustus, respectively.

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#52
An interesting writeup on using a different representation for time is here[1]. It can represent any specific second from March 1, 2000 +/-2.9Myears with 62 bits and can efficiently calculate Gregorian dates using only 32-bit arithmetic. An optimization involving a 156K lookup table is also discussed.

A few notes for those not familiar with Lisp:

1. Common Lisp defines a time called "universal time" that is similar to unix time, just with a different epoch

2. A "fixnum" is a signed-integer that is slightly (1-3 bits) smaller than the machine word size (32-bits at the time the article was written). The missing bits are used for run-time type tagging. Erik's math assumes 31-bits for a fixnum (2.9M years is approximately 2^30 days and fixnums are signed).

3. Anywhere he talks about "vectors of type (UNSIGNED-BYTE X)" this means a vector of x-bit unsigned values. Most lisp implementations will allow vectors of unboxed integers for reasonable values of X (e.g. 1, 8, 16, 32, 64), and some will pack bits for arbitrary values of X, doing the shift/masking for you.

1: https://naggum.no/lugm-time.html

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#53
post #27
post #5

> The algorithm provides accurate results over a period of ±1.89 Trillion years i'm placing my bets that in a few thousand years we'll have changed calendar system entirely haha but, really interesting to see the insane methods used to achieve this

Maybe not in a few thousand years, but given the deceleration of the Earth’s rotation around its axis, mostly due to tidal friction with the moon, in a couple hundred thousand years our leap-day count will stop making sense. In roughly a million years, day length will have increased such that the year length will be close to 365.0 days. I therefore agree that a trillion years of accuracy for broken-down date calculat…

> 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.

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#54
post #27
post #5

> The algorithm provides accurate results over a period of ±1.89 Trillion years i'm placing my bets that in a few thousand years we'll have changed calendar system entirely haha but, really interesting to see the insane methods used to achieve this

Maybe not in a few thousand years, but given the deceleration of the Earth’s rotation around its axis, mostly due to tidal friction with the moon, in a couple hundred thousand years our leap-day count will stop making sense. In roughly a million years, day length will have increased such that the year length will be close to 365.0 days. I therefore agree that a trillion years of accuracy for broken-down date calculat…

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.

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#55
post #46

Earlier quoted context omitted.

The calendar was regularized to include a leap day during the reign of Julius Caesar (hence the name "Julian calendar"), which would have been 45 BC. The Roman calendar moved to January as the first month of the year in 153 BC, over a hundred years before the leap day was added. The 10-month calendar may not have even existed--we see no contemporary evidence of its existence, only reports of its existence from centur…

Are you saying that while we do see evidence that September, October, November, December were once the 7th, 8th, 9th, and 10th month, we don't see any evidence that the calendar was ever "10 months long"? (How would that have worked anyway, did they have more days per month?)

Pretty much.

> How would that have worked anyway, did they have more days per month?

The way I've heard, they just simply didn't track the date during the winter.

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#57

Interesting how it compares with the ClickHouse implementation, which uses a lookup table: https://github.com/ClickHouse/ClickHouse/blob/master/src/Com... So that a day number can be directly mapped to year, month, and day, and the calendar date can be mapped back with a year-month LUT.

Simply, ClickHouse only works on a 399 years span while OP's algorith parses any date, over 3 trillion years.

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#58
post #25
post #7

I wrote my own date calculation functions a while ago. And during that, I had an aha moment to treat March 1 as the beginning of the year during internal calculations[0]. I thought it was a stroke of genius. It turns out this article says that’s the traditional way. [0]: https://github.com/kccqzy/smartcal/blob/9cfddf7e85c2c65aa6de...

not completely coincidentally, March was also the first month of the year in many historical calendars. Afaik that also explains why the month names have offset to them (sept, oct, nov, dec) edit: I just love that there are like 5 different comments pointing out this same thing

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

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#59
post #58
post #25

Earlier quoted context omitted.

not completely coincidentally, March was also the first month of the year in many historical calendars. Afaik that also explains why the month names have offset to them (sept, oct, nov, dec) edit: I just love that there are like 5 different comments pointing out this same thing

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

That's a common misconception. Those were just renamed for the Caesars. January and February we added, before that there was just a gap in the winter.

Re: A Fast 64-Bit Date Algorithm (30–40% faster by counting dates backwards)

#60
post #12

It took me a while to understand that internally it uses 128bit numbers, that `>> 64` in the pseudocode was super confusing until I saw the C++ code. Neat code though!

Not really. It looks like that in the C code, but in the generated machine code it'll just be a single `MULH` instruction giving (only) the upper 64 bits of the result, no shift needed.
Post reply on HN