Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

benjoffe.com

Post reply on HN
Print view View original

21–30 of 100 posts

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

#21

Post by zamadatix »

kccqzy wrote: post #17
silisili wrote: post #13

Earlier quoted context omitted.

At this risk of me feeling stupid, could you briefly explain the benefit of this?

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…

The magic numbers at the end of this explanation are the number of days of each part of the leap year cycle:

146097 days = 400 year portion of the leap year cycles (including leap years during that)

36524 days = same for the 100 year portion of the leap year cycles

1461 days = 4 year cycle + 1 leap day

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

#22

Post by [deleted] »

kccqzy wrote: 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...

[deleted]

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

#23

Post by drob518 »

benjoffe wrote: post #2

A write-up of a new Gregorian date conversion algorithm. It achieves a 30–40% speed improvement on x86-64 and ARM64 (Apple M4 Pro) by reversing the direction of the year count and reducing the operation count (4 multiplications instead of the usual 7+). Paper-style explanation, benchmarks on multiple architectures, and full open-source C++ implementation.

Nicely done.

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

#24

Post by d--b »

kccqzy wrote: post #17
silisili wrote: post #13

Earlier quoted context omitted.

At this risk of me feeling stupid, could you briefly explain the benefit of this?

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…

IIRC, it's also why the leap day was set to Feb 29th in the first place. At the time (romans?) the year started March 1st.

In case someone was wondering why in the world someone said we should add a day to the second month of the year...

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

#25

Post by zokier »

kccqzy wrote: 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

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

#26

Post by 3eb7988a1663 »

silisili wrote: post #13
kccqzy wrote: 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...

At this risk of me feeling stupid, could you briefly explain the benefit of this?

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.

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

#27

Post by layer8 »

vladde wrote: 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 calculation has little practical relevance. The question is if the calculation could be made even more efficient by reducing to 32 bits, or maybe even just 16 bits.

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

#28

Post by zX41ZdbW »

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.

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

#29

Post by Mikhail_Edoshin »

zokier wrote: post #25
kccqzy wrote: 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'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.

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

#30

Post by ____tom____ »

vladde wrote: 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

The calendar system already changed. So this won't get correct dates, meaning the dates actually used, past that date. Well, those dates, as different countries changed at different times.
Post reply on HN