6 ms·

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

395 points by benjoffe 10mo ago

benjoffe 10mo ago
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 10mo ago
  Very nice writeup! > Years are calculated backwards How did that insight come about?
  - benjoffe 10mo ago
    Thanks. 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/218356e28c7d8d9d2b5986a2aa642bf829494236/algorithms/joffe_fast64bit.hpp https://github.com/benjoffe/fast-date-benchmarks/blob/218356...
- sltkr 10mo ago
  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.
  - benjoffe 10mo ago
    Thanks, that is a good idea. This was originally a blog post series, and the first article gave a bit of an introduction. 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 10mo ago
  Nicely done.
- zozbot234 10mo ago
  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.
  - benjoffe 10mo ago
    That is an interesting question. 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 10mo ago
  Love the literate programming style explanation. Chapeau bas
swiftcoder 10mo ago
Nice to see the micro-optimising folks are still making progress on really foundational pieces of the programming stack
- HackingWizard 10mo ago
  Yes, some sharing Vibe coded slop.
vladde 10mo ago
> 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 10mo ago
  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 10mo ago
    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.
    - Tor3 10mo ago
      And count Planck time instead of seconds.. it's not as impossible as it may sound. You'll need more than 128 bits but less than 256 bits even if the epoch is the Big Bang (I can't recall exactly how many bits are needed, but I did the math once, some years ago). And it'll be compatible with alien or future time systems too, in case what we call a second (currently defined by caesium-133 periods) changes.
- layer8 10mo ago
  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.
deleted 10mo ago
[deleted]
kccqzy 10mo ago
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/9cfddf7e85c2c65aa6dec1ac183a73a58379e8f8/src/smartcal/core.cljs#L88 https://github.com/kccqzy/smartcal/blob/9cfddf7e85c2c65aa6de...
- silisili 10mo ago
  At this risk of me feeling stupid, could you briefly explain the benefit of this?
  - da_chicken 10mo ago
    It's easy to know what day of the year it is because leap days are at the end.
  - kccqzy 10mo ago
    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 10mo ago
      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 10mo ago
      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...
zkmon 10mo ago
Nice to see that there are still some jewels left to be dug out from the algorithm land.
- rurban 10mo ago
  Well searching for strings, appending strings, comparing strings. All still unimplemented in standard libs. (Strings being unicode of course)
juancn 10mo ago
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!
- brucehoult 10mo ago
  Not really. It looks like that in the C code, but in the generated machine code it'll just be a single `MULH` instruction giving (only) the upper 64 bits of the result, no shift needed.
kittikitti 10mo ago
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 10mo ago
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 10mo ago
  Relevant Old New Thing: https://devblogs.microsoft.com/oldnewthing/20090306-00/?p=18913 https://devblogs.microsoft.com/oldnewthing/20090306-00/?p=18... https://stackoverflow.com/questions/10849717/what-is-the-significance-of-january-1-1601 https://stackoverflow.com/questions/10849717/what-is-the-sig...
wood_spirit 10mo ago
Admittedly in a different league speed wise but also scope wise is my very fast timestamp library for Java https://github.com/williame/TimeMillis 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 10mo ago
Interesting how it compares with the ClickHouse implementation, which uses a lookup table: https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/DateLUTImpl.h 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.
- simlevesque 10mo ago
  Simply, ClickHouse only works on a 399 years span while OP's algorith parses any date, over 3 trillion years.
danishSuri1994 10mo ago
[flagged]
pyrolistical 10mo ago
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.
- flumpcakes 10mo ago
  This pretty much is assembly written as C++... there's not much the compiler can ruin.
- Jaxan 10mo ago
  Because that isn’t portable?
Findecanor 10mo ago
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.
- toast0 10mo ago
  If Unix Time enumerated leap seconds, you couldn't convert future timestamps into localized times.
  - dxdm 10mo ago
    Could you elaborate on what you mean? I think it's already impossible to accurately turn a future timestamp into a local time, leap seconds or not, because of timezone shenanigans. So I'm probably misunderstanding what you're talking about.
    - Marsymars 10mo ago
      I think it depends on whether you consider “localized” to refer to a point in time in a particular time zone, or to a point in time in a particular physical location.
      - dxdm 10mo ago
        > or to a point in time in a particular physical location 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.
        Marsymars 10mo ago
        Oh I'm saying the reverse, I think. Future timestamp for "time at location" is impossible because you don't know within which time zone a location will be in the future. But for the right time zone database structure you can have indeterminate time zones - so you can know future timestamps for a time zone, but you don't know if any particular location (or any location at all) is using that time zone in the future.
ComputerGuru 10mo ago
Good opportunity to plug this folklore legend: https://neosmart.net/forums/threads/an-extended-history-of-time-the-calendar.2851/ https://neosmart.net/forums/threads/an-extended-history-of-t...
aidenn0 10mo ago
An interesting writeup on using a different representation for time is here[1]. It can represent any specific second from March 1, 2000 +/-2.9Myears with 62 bits and can efficiently calculate Gregorian dates using only 32-bit arithmetic. An optimization involving a 156K lookup table is also discussed. 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. 1: https://naggum.no/lugm-time.html https://naggum.no/lugm-time.html
hyperhello 10mo ago
Can this algorithm tell me how old I was last year?
ape4 10mo ago
Perhaps nicer to avoid the comment and write: const C1 = 505054698555331 // floor(2^64*4/146097) as constexpr int C1 = floor(2^64*4/146097);
- aw1621107 10mo ago
  std::floor was made constexpr in C++23, which is pretty recent as far as C++ standards go. It's possible the author didn't think using C++23 was worth the constraints it places on who could use the code.
  - CodesInChaos 10mo ago
    That's a mathematical expression, not a C++ expression. And floor here isn't the C++ floor function, it's just describing the usual integer division semantics. The challenge here is that you need 128-bit integers to avoid overflowing.
    - aw1621107 10mo ago
      Ah, you're right. I saw that the expression in the comment and in the code was the same and assumed that the commented bit was valid C++ code. You got me to look again and it's obvious that that isn't the case. I had even gone looking through the codebase to see if std::floor was included, and still missed the incorrect `^`. 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.
- glitchdout 10mo ago
  const C1 = 505054698555331 // floor(2^64*4/146097) is faster
burnt-resistor 10mo ago
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.
zokier 10mo ago
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?
seastarer 10mo ago
Do these calculations take into account the lengthening of the days due to tidal friction?

395 points by benjoffe 10mo ago

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 10mo ago
Very nice writeup! > Years are calculated backwards How did that insight come about?
- benjoffe 10mo ago
  Thanks. 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/218356e28c7d8d9d2b5986a2aa642bf829494236/algorithms/joffe_fast64bit.hpp https://github.com/benjoffe/fast-date-benchmarks/blob/218356...
sltkr 10mo ago
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.
- benjoffe 10mo ago
  Thanks, that is a good idea. This was originally a blog post series, and the first article gave a bit of an introduction. 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 10mo ago
Nicely done.
zozbot234 10mo ago
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.
- benjoffe 10mo ago
  That is an interesting question. 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 10mo ago
Love the literate programming style explanation. Chapeau bas

swiftcoder 10mo ago

Nice to see the micro-optimising folks are still making progress on really foundational pieces of the programming stack

HackingWizard 10mo ago
Yes, some sharing Vibe coded slop.

vladde 10mo ago

> 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 10mo ago
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 10mo ago
  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.
  - Tor3 10mo ago
    And count Planck time instead of seconds.. it's not as impossible as it may sound. You'll need more than 128 bits but less than 256 bits even if the epoch is the Big Bang (I can't recall exactly how many bits are needed, but I did the math once, some years ago). And it'll be compatible with alien or future time systems too, in case what we call a second (currently defined by caesium-133 periods) changes.
layer8 10mo ago
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.

deleted 10mo ago

[deleted]

kccqzy 10mo ago

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/9cfddf7e85c2c65aa6dec1ac183a73a58379e8f8/src/smartcal/core.cljs#L88 https://github.com/kccqzy/smartcal/blob/9cfddf7e85c2c65aa6de...

silisili 10mo ago
At this risk of me feeling stupid, could you briefly explain the benefit of this?
- da_chicken 10mo ago
  It's easy to know what day of the year it is because leap days are at the end.
- kccqzy 10mo ago
  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 10mo ago
    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 10mo ago
    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...

zkmon 10mo ago

Nice to see that there are still some jewels left to be dug out from the algorithm land.

rurban 10mo ago
Well searching for strings, appending strings, comparing strings. All still unimplemented in standard libs. (Strings being unicode of course)

juancn 10mo ago

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!

brucehoult 10mo ago
Not really. It looks like that in the C code, but in the generated machine code it'll just be a single `MULH` instruction giving (only) the upper 64 bits of the result, no shift needed.

kittikitti 10mo ago

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 10mo ago

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 10mo ago
Relevant Old New Thing: https://devblogs.microsoft.com/oldnewthing/20090306-00/?p=18913 https://devblogs.microsoft.com/oldnewthing/20090306-00/?p=18... https://stackoverflow.com/questions/10849717/what-is-the-significance-of-january-1-1601 https://stackoverflow.com/questions/10849717/what-is-the-sig...

wood_spirit 10mo ago

Admittedly in a different league speed wise but also scope wise is my very fast timestamp library for Java https://github.com/williame/TimeMillis 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 10mo ago

Interesting how it compares with the ClickHouse implementation, which uses a lookup table: https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/DateLUTImpl.h 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.

simlevesque 10mo ago
Simply, ClickHouse only works on a 399 years span while OP's algorith parses any date, over 3 trillion years.

danishSuri1994 10mo ago

[flagged]

pyrolistical 10mo ago

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.

flumpcakes 10mo ago
This pretty much is assembly written as C++... there's not much the compiler can ruin.
Jaxan 10mo ago
Because that isn’t portable?

Findecanor 10mo ago

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.

toast0 10mo ago
If Unix Time enumerated leap seconds, you couldn't convert future timestamps into localized times.
- dxdm 10mo ago
  Could you elaborate on what you mean? I think it's already impossible to accurately turn a future timestamp into a local time, leap seconds or not, because of timezone shenanigans. So I'm probably misunderstanding what you're talking about.
  - Marsymars 10mo ago
    I think it depends on whether you consider “localized” to refer to a point in time in a particular time zone, or to a point in time in a particular physical location.
    - dxdm 10mo ago
      > or to a point in time in a particular physical location 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.
      - Marsymars 10mo ago
        Oh I'm saying the reverse, I think. Future timestamp for "time at location" is impossible because you don't know within which time zone a location will be in the future. But for the right time zone database structure you can have indeterminate time zones - so you can know future timestamps for a time zone, but you don't know if any particular location (or any location at all) is using that time zone in the future.

ComputerGuru 10mo ago

Good opportunity to plug this folklore legend: https://neosmart.net/forums/threads/an-extended-history-of-time-the-calendar.2851/ https://neosmart.net/forums/threads/an-extended-history-of-t...

aidenn0 10mo ago

An interesting writeup on using a different representation for time is here[1]. It can represent any specific second from March 1, 2000 +/-2.9Myears with 62 bits and can efficiently calculate Gregorian dates using only 32-bit arithmetic. An optimization involving a 156K lookup table is also discussed. 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. 1: https://naggum.no/lugm-time.html https://naggum.no/lugm-time.html

hyperhello 10mo ago

Can this algorithm tell me how old I was last year?

ape4 10mo ago

Perhaps nicer to avoid the comment and write: const C1 = 505054698555331 // floor(2^64*4/146097) as constexpr int C1 = floor(2^64*4/146097);

aw1621107 10mo ago
std::floor was made constexpr in C++23, which is pretty recent as far as C++ standards go. It's possible the author didn't think using C++23 was worth the constraints it places on who could use the code.
- CodesInChaos 10mo ago
  That's a mathematical expression, not a C++ expression. And floor here isn't the C++ floor function, it's just describing the usual integer division semantics. The challenge here is that you need 128-bit integers to avoid overflowing.
  - aw1621107 10mo ago
    Ah, you're right. I saw that the expression in the comment and in the code was the same and assumed that the commented bit was valid C++ code. You got me to look again and it's obvious that that isn't the case. I had even gone looking through the codebase to see if std::floor was included, and still missed the incorrect `^`. 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.
glitchdout 10mo ago
const C1 = 505054698555331 // floor(2^64*4/146097) is faster

burnt-resistor 10mo ago

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.

zokier 10mo ago

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?

seastarer 10mo ago

Do these calculations take into account the lengthening of the days due to tidal friction?