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

41–50 of 100 posts

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

#41

Post by _dain_ »

Mikhail_Edoshin wrote: post #29
zokier wrote: 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'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.

>So after the tenth month there was a strange unmapped period.

this is when time-travelling fugitives hide out

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

#44

Post by jcranmer »

d--b wrote: post #24
kccqzy wrote: post #17

Earlier quoted context omitted.

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

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 centuries hence and the change there is attributed to a mythical character.

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

#45

Post by [deleted] »

d--b wrote: post #24
kccqzy wrote: post #17

Earlier quoted context omitted.

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

[deleted]

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

#46

Post by anyfoo »

jcranmer wrote: post #44
d--b wrote: post #24

Earlier quoted context omitted.

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

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

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

#47

Post by zozbot234 »

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.

How would this algorithm change on 16-bit or 8-bit devices? Or does some variety of the traditional naïve algorithm turn out to be optimal in that case? There's quite a bit of microcontroller software that might have to do date conversions, where performance might also matter. It's also worth exploring alternative epochs and how they would affect the calculation.

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

#48

Post by wizzwizz4 »

d--b wrote: post #24
kccqzy wrote: post #17

Earlier quoted context omitted.

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

Technically, the leap day (bissextus) was the 24th. (Wikipedia tells me this is because that's when Mercedonius used to be, before the Julian reforms.)

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

#49

Post by sltkr »

amenghra wrote: post #32
d--b wrote: post #24

Earlier quoted context omitted.

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

And (oct)ober was the 8th month of the year, (nov)ember the ninth, (dec)ember the tenth!

Weird parenthesization. The latin numbers are septem, octo, novem, decem for 7, 8, 9, 10. And then they all have a -ber suffix.

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

#50

Post by flumpcakes »

pyrolistical wrote: post #40

For something this short that is pure math, why not just hand write asm for the most popular platforms? Prevents compiler from deoptimizing in the future. Have a fallback with this algorithm for all other platforms.

This pretty much is assembly written as C++... there's not much the compiler can ruin.
Post reply on HN