[ntp:questions] Re: Question about synchronizing client and server clock

Terje Mathisen terje.mathisen at hda.hydro.com
Tue Jan 6 09:36:23 UTC 2004


John Howells wrote:
> Terje Mathisen wrote:
> 
>>NT's _ftime counts 100 ns intervals, starting from 1600 (?), 
> 
> 1st January 1601. Although I do not believe it is stated anywhere, this

Thanks.

> is presumably chosen so that all leap year "multiples" (every 4 years,
> every 100 years, and every 400 years) are the last modulo the multiple,
> which makes conversion between a date and an FTIME easier than any other
> origin (assuming all dates use the Gregorian calendar). I.e. assuming
> normal integer division you can do:
> 
> 	int	Years = Target_Year - 1601;
> 	int	Days_To_Start_Of_Year = Years * 365 +
> 			( Years / 4 ) -
> 			( Years / 100 ) +
> 			( Years / 400 );
> 
> which is not so simple with any other origin.

I'd bet that the "real" origin is 10 months earlier, i.e. after 
splitting the tick count into day number and seconds+fraction, they 
start by adding (365 - 31 - 28 =) 306 days to the day_number variable.
(This can never overflow, btw.)

In my own (fast) conversion code I use 1600-03-01 00:00 as the origin, 
because that makes the leap year handling even easier:

All leap days will then be the last day of the current year, and your 
example code above starts to work: You must start with logical year 
number zero!

I.e. the following portable code generates very fast machine code on all 
the cpus I've tested:

unsigned centuries = years / 100;
unsigned days_to_star_of_year =
    years * 365 +
    (years >> 2) -
    centuries +
    (centuries >> 2);

Anyway, this operation (Y-M-D to daynr) is quite trivial with such a 
March 1st origin, the opposite direction is much harder.

In fact, by far the fastest way to get from day_number to year is to 
guess the year, calculate the corresponding day number, and then 
possibly adjust the initial guess! :-)

(See code snippet below!)

Terje

     /* Start by subtracting any full 400-year cycles: */
     y400 = days / 146097; /* Reciprocal multiplication! */
     days -= y400 * 146097;

/* Useful and faster approximation to the number of years, will be wrong
  * (too high) 910 times
  * in a 400-year cycle, i.e. in 0.62% of all calls.
  *
  * Requires unsigned values with up to 29 significant bits!
  */
     y = (days * 2871 + 1983) >> 20;

/* Calculate # of centuries:
  * Since y will be in the 0 to 400 range, the following
  * approximation can be used instead of a division by 100:
  *     y / 100; -> (y * 41) >> 12;
  */
     y100 = (y * 41) >> 12;

/* # of days in those full years */
     gd = y * 365		/* Normal years */
	+ (y >> 2)		/* + leap years every 4 years */
	- y100			/* - missing century leap years */
	+ (y100 >> 2);  	/* + every 400 years */

/* test for the small chance of a wrong year: */
     if (gd > days) {
	y--;	/* y will be in the [0-399] range! */
	y100 = (y * 41) >> 12;
	/* The 400-year correction can be skipped! */
	gd = y * 365 + (y >> 2) - y100 /* + (y100 >> 2) */;
     }

     /* Calculate the offset into the current year: */
     days -= gd;

-- 
- <Terje.Mathisen at hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"



More information about the questions mailing list