Efficient algorithm for determining if a date is in DST

Question

I'm looking for a better than O(n) algorithm to determine if a date in the future will have daylight savings time applied (and how much). Given a year, month, day, hour, minute and time zone (and a copy of the Olsen Time Zone database) how does one efficiently determine if that date will be in DST? I'm looking for the algorithm, not a library function to call.

Thank you.

FURTHER EXPLANATION: The date library I'm using is very slow when you create an object with a date in the future and a time zone. It turns out its doing a linear calculation to calculate if the date is in daylight savings time. Not only that, its doing this at object creation time. Obviously it could wait until asked, but it should also be more efficient.

Sure, DST rules change and a date library can't predict the future, but the alternative is to put an arbitrary upper limit on localized dates.

Answer 1

Your number one problem is daylight savings rules that are set by the local authorities. The latter can pass almost any law at any time and therefore change the rules in a way you can't possibly predict.

Answer 2

As far as I know DST changes that are known start and end on a fixed day each year (first weekend in april, last weekend in october, stuff like that). So you could ese the Doomsday Algorithm to find the days of the week for the given year and calculate the conversion dates from that. Then you can determine if DST is in effect in source and/or destination locale. The converion itself is simply a matter of adding and/or subtracting an hour to compensate for DST and then factor in the timezone difference.

Answer 3

Everybody's already commented on the problems with always-changing DSTs. But I can accept the premise that we just pretend the currently known rules will apply forever.

To get your DST information, the first thing to do is to calculate the year/month/day for your future date (if it isn't in that form already). Then you look up your time zone and pull out the variation against UTC, the DST on/off rule and offset. There could be several different rules depending on which year, you want to be sure to grab the right one for your "target" year. For reasons explained below, it may be handy to also be aware of the rules for the preceding year.

The on/off rules will have a funny spec like "Oct lastSun": That means the switch occurs in the night of the last Sunday in October.

What you need to do is gather up all of these tersely formatted "rules" and develop a bit of code for each to determine the last date indicated by that rule. It's currently December, so given a couple of rules like "Mar lastSun" and "Oct lastSun" for my time zone, those dates would be March 29, 2009 and October 25, 2009. Which of these dates is more recent? October. October is associated with an "off", so we must currently have NO DST.

You can calculate the DST on/off dates for the current (i.e. target) year regardless of whether the target date is before or after those dates; if the on/off date is in the future of your target date, then simply do the rule calculation again for the previous year. Note that the rules may have changed during the interval, so be sure to apply the correct one for the year you're looking at.

Worst case for this calculation is, you have to repeat your two rule calculations for the previous year. But there's no searching going on otherwise, so it's strictly O(1).

I found a Local/DST/Tz calculator here: http://home-4.tiscali.nl/~t876506/WhatDay.html and as it's a JavaScript applet you should be able to simply crib the code. It doesn't handle all rules, though, so you will need to add some code for the remaining rules.

---

Update: I just noticed you have an hour and minute in your time as well. That complicates matters just a little. If your date is not on a "switch" date then the instructions I gave above will do you fine. Otherwise, you need to consider the time. I guess the cleanest thing to do would be to include the time in your determination of "most recent". I.e. if your target time is 00:30 UTC and switch time for the given zone is 01:00, then the target year's switch time is still in the future and you have to use the previous year's switch time instead. For practical purposes, this will mean that the "other" switch time was the most recent, and its on/off status applies.

Answer 4

Hmm, as I see the problematic point is to determine weekday for a given day, far in the future.

For that, I suggest something like that:

• after every 400 years, the complete system turns around, so first divide the number of years with 400, take the integral part. In 400 years, there are 99 leap years and 301 simple ones. If an arbitrary day is Monday, then the same day 400 years later will be 301+2x99 = 499 (mod 7) ---> Monday+2 ---> Wednesday. So you have to say something like that:

wday = (ref_day + 2 * (int)((target_year - ref_year) / 400)) mod 7

• then you can do further optimizations, but I guess you can go year-by-year, that will do it. At most you make 399 simple operations, if (leap_year) then ++ else +=2, mod 7.

After you have the weekday for Jan 1 that year, you can calculate DST switching dates, as Carl Smotricz has written.