Live data from Hacker News

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

benjoffe.com

81–90 of 100 posts

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

#81
post #49

Earlier quoted context omitted.

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

The three letter prefixes show up in English (eg oct in octal, dec in decimal, etc.).

The prefix in "decimal" is "decim", like you'd expect given that the root is "decem". There is no "dec-" prefix.

(You do see "deca" used as a prefix, "a" included, but that doesn't come from Latin.)

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

#82

Earlier quoted context omitted.

The three letter prefixes show up in English (eg oct in octal, dec in decimal, etc.).

The prefix in "decimal" is "decim", like you'd expect given that the root is "decem". There is no "dec-" prefix. (You do see "deca" used as a prefix, "a" included, but that doesn't come from Latin.)

You are right. I should have written: (septem)ber was the 7th month of the year, (octo)ber was the 8th, (novem)ber the ninth, and (decem)ber the tenth!

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

#83
That pseudo-code isn't very imprecise because there's no type information (64-bit or 128-bit integers? signed or unsigned?) and it doesn't account for results of overflow or underflow in the realm of UB. It's also inconsistent to introduce bit shifts instead of division and then use modulus instead of "and" masking; typically, pick one style or the other.

caldat is the third algorithm in the Numerical Recipes in Pascal (1986,89,90,92) book[0] (p. 13), where Julian days are easy to turn into days since the UNIX epoch. It uses 3 single-precision floating point divisions and 3 multiplications with pre-Gregorian support or 2 each respectively without, but is convertible to an algorithm using a mix of 8-bit and 16-bit signed fixed point integer math for microcontroller usage. 64-bit (or higher) integer math is not strictly required, but whatever's faster and correct for a given target is fine.

0: The last time I dug up the book was some time last year because I was hunting for an algorithm for the precise position of the Sun in the sky given a lat lon (WGS 84) and date time for a solar tracker that didn't need light sensors, only time and location that was already available for free.

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

#84
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…

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

Note that some sources suggest that February might still have been the last month, placed after December and before January.

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

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

Love the literate programming style explanation. Chapeau bas

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

#86
post #53
post #27

Earlier quoted context omitted.

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.

I meant reducing the representable year numbers, not the whole timestamp.

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

#87
For 64 bit timekeeping arguably for lots of uses counting nanoseconds makes a more sense than seconds. You can still cover decent usable range (2^64 ns > 584 years) and save the need for separate subsecond counter.

What would be the most efficient algorithm to handle such ns scale? I guess one option would be just to divide by 10^9 and run the code from the article, but can we do better?

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

#88
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

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!

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

#90

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.

Because that isn’t portable?
Post reply on HN