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
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.
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.
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.
Given the chronostrife will occur in around 40_000 years (give or take 2_000) I somewhat doubt that </humor>
[0]: https://github.com/kccqzy/smartcal/blob/9cfddf7e85c2c65aa6de...
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
In case someone was wondering why in the world someone said we should add a day to the second month of the year...
(You do see "deca" used as a prefix, "a" included, but that doesn't come from Latin.)
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.
> 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.
It's fair to say January was the first month of the Roman calendar; despite it having formerly been March.
Caesar happened to be the Pontifex Maximus (an office you hold for life once elected to), but he wasn't in Rome much to do that job. So after he came back from hanging out with Cleopatra in Egypt he came back and set the calendar on auto-pilot.
Note that some sources suggest that February might still have been the last month, placed after December and before January.
edit: I just love that there are like 5 different comments pointing out this same thing
this is when time-travelling fugitives hide out
(It's still evidence in the direction you suggest, just much weaker than it looks at first.)
Everything now makes sense, I always wondered why September was the nine month with a 7 prefix.
And often the last month too. The early modern English calendar began the year on March 25.
This is coincidental in relation to the offset in the names of the months. The Romans started their year in January just like we do today.
(Though in a very broad sense, it's common to begin the year with the new spring. That's the timing of Chinese new year and Persian new year. I believe I've read that the Roman shift two months backward was an administrative reform so that the consuls for the year would have time to prepare for the year's upcoming military campaigns before it was time to march off to war.)
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!
Displaying the months like the following helps see the regularity at a glance. Columns 1, 3 and 5 are the long months, others being shorter:
+-----+-----+-----+-----+-----+
| 31 | 30 | 31 | 30 | 31 |
| I | II | III | IV | V |
| MAR | APR | MAY | JUN | JUL |
|-----+-----+-----+-----+-----+
| 31 | 30 | 31 | 30 | 31 |
| VI |VII |VIII | IX | X |
| AUG | SEP | OCT | NOV | DEC |
+-----+-----+-----+-----+-----+
| 31 |28/29|
| XI |XII |
| Jan | FEB |
+-----+-----+
Neat code though!
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.
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.
Have a fallback with this algorithm for all other platforms.
But how does this not take the local time zone into account? For "time at location", the local time zone is by necessity always involved in conversions, isn't it? There's just a difference between the time zone being explicit in your data representation, or merely implied.
But you cannot with any sort of confidence assume a future "implied" time zone, which makes turning a future timestamp into a local time, even using a timezone-naive representation, into an usure proposition.
Maybe I'm simply not aware of specific conventions around this topic, though, hence my original question.
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.
const C1 = 505054698555331 // floor(2^64*4/146097)
constexpr int C1 = floor(2^64*4/146097);I guess in that case as long as the 128-bit type supports constexpr basic math operations that should suffice to replace the hardcoded constants with their source expressions.
const C1 = 505054698555331 // floor(2^64*4/146097)
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.
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?
benjoffe•2mo ago
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•2mo ago
> Years are calculated backwards
How did that insight come about?
benjoffe•2mo ago
I was fortunate enough to be programming on an ARM based device, which meant that the terms (x * 4 + 3) strongly stood out to me as highly inefficient, being 2 cycle prep for the more important division. On x64 computers, those two operations are calculated in only one operation by using the 'LEA' assembly instruction (which I wasn't aware of at the time), and so others using that type of computer might not have felt this step needed any simplification.
I tried everything under the sun to get rid of these steps. The technique noted in the article of using the year 101 BC was for a long time my strongest candidate, you can view the implementation of that attempt at the link below [1].
An epoch of 101 BC still meant that there was extra work required to re-normalise the timeline after the century calculation, but it was only a single addition of 365 in the calculation of `jul`. The explanation of how this works is probably a whole blog post in itself, but now that this algorithm has been discarded it's not worth the time to explain it fully.
I also had the year-modulus-bitshift technique developed at that time, but it couldn't be integrated cleanly with any of my algorithm attempts yet. My plan was to simply document it as an interesting but slower concept.
I don't know what sparked the idea of going backwards other than immersing myself deeply in the problem in my spare time for about a month. It finally came to me one evening, and I thought it was only going to save 1-cycle, but when it also meant the year-modulus-bitshift could be utilised, the entire thing fit together like a glove and the speed collapsed down from 20% time saving to 40%.
[1] https://github.com/benjoffe/fast-date-benchmarks/blob/218356...
sltkr•2mo ago
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.
benjoffe•2mo ago
When I started the blog series, I expected the first article to be the most noteworthy, with the 2nd and 3rd being lesser supplementary topics.
Now that the 3rd blog post ended up with a much larger result than I was expecting, it stands on its own and could do with some editing as you suggest.
drob518•2mo ago
zozbot234•2mo ago
benjoffe•2mo ago
It might also come into play if developing SIMD alternatives for batch date processing, as one can have more lanes with 16-bit. I plan to make a blog post covering SIMD and if 16-bit algorithms have reasonable performance then that will be covered.
baq•2mo ago