[ntp:questions] Converting from Y-m-d h:m:s

Terje Mathisen "terje.mathisen at tmsw.no" at ntp.org
Sat May 15 21:05:35 UTC 2010

Rob wrote:
> Terje Mathisen<"terje.mathisen at tmsw.no">  wrote:
>> Going from YMDHMS to unix (or ntp) seconds is really quite trivial,
>> while the opposite direction is much harder!
>> My most efficient algorithm for the reverse function needs somewhere
>> between 30 and 50 clock cycles (compare with 40 cycles for a single DIV
>> opcode...), while the forward function is about twice as fast:
> Have you seen how glibc approaches this conversion?

No, but as I noted in the source code, my algorithm turned out to be 
quite similar to what IBM developed for mainframes. I wouldn't be 
surprised to learn that other programmers have ended up with similar code.

The key idea is to realize that when you have a function and its much 
slower inverse, then you can implement the slow function by making a 
fast guess of what the answer should be, test the guess using the fast 
forward function, and then correct if needed.
 From offtime.c (glibc 2.1.3):
#define DIV(a, b) ((a) / (b) - ((a) % (b) < 0))
#define LEAPS_THRU_END_OF(y) (DIV (y, 4) - DIV (y, 100) + DIV (y, 400))

   while (days < 0 || days >= (__isleap (y) ? 366 : 365))
       /* Guess a corrected year, assuming 365 days per year.  */
       long int yg = y + days / 365 - (days % 365 < 0);

       /* Adjust DAYS and Y to match the guessed year.  */
       days -= ((yg - y) * 365
                + LEAPS_THRU_END_OF (yg - 1)
                - LEAPS_THRU_END_OF (y - 1));
       y = yg;

The code here is actually both significantly slower and larger (in code 
space) than mine. :-)

It knows that time zone offsets are less than 24 (actually 13 or 14?) 
hours, which means that most adjustments will stay within the same day 
or worst case add/subtract a day.

However, since the latter happens on average 25%+ of the calls (at least 
for those of you in the US), it would be faster to simply convert the 
struct tm array to seconds, add/subtract the offset, then convert back.

This also gets rid of pretty much all of the offset calculation code. :-)


- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

More information about the questions mailing list