[HN Gopher] A Fast 64-Bit Date Algorithm (30-40% faster by count...
___________________________________________________________________
A Fast 64-Bit Date Algorithm (30-40% faster by counting dates
backwards)
Author : benjoffe
Score : 217 points
Date : 2025-11-23 02:27 UTC (3 days ago)
(HTM) web link (www.benjoffe.com)
(TXT) w3m dump (www.benjoffe.com)
| benjoffe wrote:
| 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.
| digitalPhonix wrote:
| Very nice writeup!
|
| > Years are calculated backwards
|
| How did that insight come about?
| sltkr wrote:
| Very cool algorithm and great write-up!
|
| I was a bit confused initially about what your algorithm
| actually did, until I got to the pseudo-code. Ideally there
| would be a high level description of what the algorithm is
| supposed to do before that.
|
| Something as simple as: "a date algorithm converts a number of
| days elapsed since the UNIX epoch (1970-01-01) to a Gregorian
| calendar date consisting of day, month, and year" would help
| readers understand what they're about to read.
| drob518 wrote:
| Nicely done.
| swiftcoder wrote:
| Nice to see the micro-optimising folks are still making progress
| on really foundational pieces of the programming stack
| HackingWizard wrote:
| Yes, some sharing Vibe coded slop.
| vladde wrote:
| > 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
| fnordsensei wrote:
| Wouldn't it be accurate for that as well? Unless we change to
| base 10 time units or something. Then we all have a lot of work
| to do.
|
| But if it's just about starting over from 0 being the AI
| apocalypse or something, I'm sure it'll be more manageable, and
| the fix could hopefully be done on a cave wall using a flint
| spear tip.
| jandrese wrote:
| 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.
| layer8 wrote:
| 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.
| ____tom____ wrote:
| 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.
| hugmynutus wrote:
| > i'm placing my bets that in a few thousand years we'll have
| changed calendar system entirely haha
|
| Given the chronostrife will occur in around 40_000 years (give
| or take 2_000) I somewhat doubt that </humor>
| kccqzy wrote:
| 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...
| silisili wrote:
| At this risk of me feeling stupid, could you briefly explain
| the benefit of this?
| da_chicken wrote:
| It's easy to know what day of the year it is because leap
| days are at the end.
| kccqzy wrote:
| 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.
| zamadatix wrote:
| 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
| d--b wrote:
| 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...
| amenghra wrote:
| And (oct)ober was the 8th month of the year, (nov)ember
| the ninth, (dec)ember the tenth!
| Izikiel43 wrote:
| Don't forget (sep)tember being the 7th month
| variaga wrote:
| 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.
| ljsprague wrote:
| June and July used to be Quintilis and Sextilis.
| 3eb7988a1663 wrote:
| 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.
| zimpenfish wrote:
| 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.
| zokier wrote:
| 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
| Mikhail_Edoshin wrote:
| 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.
| _dain_ wrote:
| _> So after the tenth month there was a strange unmapped
| period._
|
| this is when time-travelling fugitives hide out
| Izikiel43 wrote:
| > 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.
| zkmon wrote:
| Nice to see that there are still some jewels left to be dug out
| from the algorithm land.
| juancn wrote:
| 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!
| kittikitti wrote:
| Thank you for sharing. This is a great achievement not only in
| the ability to invent a novel algorithm with significant
| performance gains but also the presentation of the work. It's
| very thorough and detailed, and I appreciated reading it.
| masfuerte wrote:
| The Windows epoch starts on 1601-01-01. I always assumed that was
| because it slightly simplifies the calculation, as described in
| the article. But it's not as good as the article's method of
| counting backwards.
| Lammy wrote:
| Relevant Old New Thing:
| https://devblogs.microsoft.com/oldnewthing/20090306-00/?p=18...
|
| https://stackoverflow.com/questions/10849717/what-is-the-sig...
| wood_spirit wrote:
| Admittedly in a different league speed wise but also scope wise
| is my very fast timestamp library for Java
| https://github.com/williame/TimeMillis
|
| This focuses on string <-> timestamp and a few other utilities
| that are super common in data processing and where the native
| Java date functions are infamously slow.
|
| I wrote it for some hot paths in some pipelines but was super
| pleased my employer let me share it. Hope it helps others.
| zX41ZdbW wrote:
| 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.
| pyrolistical wrote:
| 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.
| Findecanor wrote:
| TIL that Unix Time does not count leap seconds. If it did, it
| wouldn't have been possible to write routines that are this fast.
| ComputerGuru wrote:
| Good opportunity to plug this folklore legend:
| https://neosmart.net/forums/threads/an-extended-history-of-t...
___________________________________________________________________
(page generated 2025-11-26 23:00 UTC)