Perpetual Calendar Algorithm

See the book CalendricalCalculations and/or Standard C Date/Time Library: Programming the World's Calendars and Clocks by Lance Latham, ISBN 0879304960 (although note that both books may have peculiar licensing terms).

All this, and nothing on Zeller's Congruence? See http://www.merlyn.demon.co.uk/zeller-c.htm for example.

The following, invented by Mike Keith and published in Journal of Recreational Mathematics, Vol. 22, No. 4, 1990, p. 280, is conjectured to be the shortest expression of a day-of-the-week algorithm:

(d+=m<3?y--:y-2,23*m/9+d+4+y/4-y/100+y/400)%7

Only 45 characters! See http://members.aol.com/s6sj7gt/mikecal.htm

My hat's off to him. -- Doug

I have just downloaded a perpetual calendar from Internet. You type in any date and it will give you a calendar for it. It's written in JavaScript. I'll write the URL in a few minutes.

I suspect you are talking about http://www.rootsweb.com/~pabutler/javascrp/calendar/, or http://www.skylighters.org/special/chrono/perpetual.html, or any one of the thousands of other Google hits for 'JavaScript perpetual calendar'.

Now there are 14 possible calendars. In other words, a year must be either calendar 1 or 2 or three till 14. Why 14 calendars and not 15 or 40 or whatever?

Please contribute algorithms for this problem here.

Quite simply, the year can start on any one of 7 week days. After this, the rest of the year must be fixed; except for leap years, when we miss a day, therefore there are another 7 possible calendars, totalling 14. It's not an algorithm, but it is CommonSense.

Who would want a whole year in one go? Isn't a month at a time quite enough? Only the pattern of days in the month is significant - the month name and the number of days in the month are minor details. Hence, one can use 7 patterns (1 for each day of the week), subject to minor alterations to give the correct month name and number of days in the month.

Is it so hard to do a web search? Here's the core part of one of the calendar programs I've written:

int day_of_week(int day, int month, int year) {

intabsolute_day = 0;
intleap, i;
absolute_day += ((year-1) * 365);
absolute_day += total_leap_days(day, month, year);
leap = is_leap_year(year);
for (i=0; i<month; i++)
absolute_day += days_in_month[leap][i];
absolute_day += day;
if (year > 1752) {
absolute_day -= MISSING_DAYS_IN_SEP_1752;
} else if (year == 1752 && month > SEP || (month == SEP && day >= SEP3)) {
absolute_day -= MISSING_DAYS_IN_SEP_1752;
}
return (6 + absolute_day) % 7;

}

"Why 14 calendars" is a homework problem, not an algorithm issue (i.e. this isn't rocket science; check the encyclopedia if all else fails).

-- DougMerritt

This is part of a general purpose calendar program I wrote. For any date in history, it returns the correct day of the week, including taking into account the change from the Julian to the Gregorian calendar in September 1752 (this actually varied in different European countries, so it could be improved by accepting a country name :-)

And it doesn't give sane results for dates B.C.E. ...and it probably fails 6,000 years from now because the Gregorian calendar itself will eventually fail to correctly compensate for leap days...etc. But for the usual requirements, it works. People who have requirements for longer durations, like astronomers, use a different calendar, not just the usual Gregorian.

The return value is offset by 6 in order to force the week to begin on Sunday. You can have weeks begin on any day of the week you like by changing that offset. (Some calendars show business weeks, starting on Mondays.)

Hint: the "14 calendars" isn't truly fundamental to calendar arithmetic, it's just a trick that has been used by manufacturers of paper calendars, where an algorithm wasn't suitable -- the point was convenience to the masses -- but printing 14 different calendars suited their needs perfectly.

BTW there's a version of this that is simple enough to memorize and perform in one's head, so that someone can tell you a date and you can almost instantly (if you've practiced) tell them the corresponding day of the week. I used to have it memorized but I've forgotten, do a web search. The core of it is doing all arithmetic mod 7 and adjusting for the varying lengths of each of the 12 months.

There's a moderately recent whole book that explains more than you ever thought you wanted to know about these things, but I never bought it because it's kind of expensive, and it came out years after I started implementing such algorithms. Again, sources like encyclopedias, particularly the EncyclopaediaBritannica, tend to be reasonably complete. -- DougMerritt

DougMerritt's algorithm

Just to clarify, calendar algorithms have a very long and complex history, and I certainly can't claim to have invented anything wholly new. I've seen dozens of variations, and no doubt at least thousands are out there. What I did here is just to do my best to do a variant algorithm that is simultaneously as terse as possible and as clear as possible; all of the short algorithms I've personally seen before are not clear, and most of the rest are both long and not particularly clear. However, there are lots of smart people in the world, so it could be that something exactly like this -- or better -- has previously been invented. -- DougMerritt

 #define SEP8
 #define MISSING_DAYS_IN_SEP_175211
 #define SEP32
 static int
 days_in_month[2][12] = {
{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
 };
 #define CHANGE_YEAR1752
 int
 is_leap_year(int year) {
/* Julian Calendar has a leap year every 4 years */
if (year <= CHANGE_YEAR) return !(year % 4);
/* This is just the *definition* of a Gregorian leap year: */
return !(year % 400) || ((year % 100) && !(year % 4));
 }
 int
 total_leap_days(int day, int month, int year) {
inttotal = (year / 4);/* initial estimate */
if (is_leap_year(year))
total -= 1;/* leap day is accounted for in days_in_month */
if (year > CHANGE_YEAR) {
/* Delete the inappropriate leap centuries, */
/* then add back in every 4th leap century */
total -= ((year / 100) - (CHANGE_YEAR / 100));
total += ((year / 400) - (CHANGE_YEAR / 400));
}
return total;
 }
 /*
  * Find the day of the week corresponding to any given date.
  * Works by computing the total number of days since Jan 1, year 1 A.D.
  * and then taking that modulo 7 to turn it into a day of the week.
  * Along the way we must compensate for leap years, and for the
  * change from the Julian to the Gregorian calendar in Sep 1752.
  */
 int day_of_week(int day, int month, int year) {
intabsolute_day = 0;
intleap, i;

/* Initial estimate of the total number of days */
absolute_day += ((year-1) * 365);
absolute_day += total_leap_days(day, month, year);
leap = is_leap_year(year);
for (i=0; i<month; i++)
absolute_day += days_in_month[leap][i];
absolute_day += day;
/* If the target is after the calendar switchover, add in the */
/* number of days that were deleted from Sep 1752 by the */
/* calendar changeover */
if (year > 1752) {
absolute_day -= MISSING_DAYS_IN_SEP_1752;
} else if (year == 1752 && month > SEP || (month == SEP && day >= SEP3)) {
/* Also make that adjustment for the part of 1752 */
/* after September 3, when the calendar change happened */
absolute_day -= MISSING_DAYS_IN_SEP_1752;
}
/* Take it mod 7 to find out the day of the week. Add 6 to */
/* force the first day of the week to be Sunday. */
return (6 + absolute_day) % 7;
 }

Here is an algorithm that has worked well for me (Java code derived from old C standard library sources). (Code added by 24.x.x.x)

 // Number of days since the base date of the Julian calendar.
 int julianDate(int yyyy, int mm, int dd) {
    /*
     * yyyy = 4 digit year
     * mm = month number [1, 12]
     * dd = day of the month [1, 31]
     */
    if(mm > 2) {
        mm -= 3;
    } else {
        mm += 9;
        yyyy -= 1;
    }
    int cc = yyyy / 100;
    int yy = yyyy % 100;
    return(
        ((146097 * cc) >> 2) +
        ((1461 * yy) >> 2) +
        (((153 * mm) + 2) / 5) +
        dd +
        1721119 );
 }

 // Day of the week, 0=Sunday, 1=Monday, ..., 6=Saturday
 int dayOfWeek(int yyyy, int mm, int dd) {
    return (julianDate(yyyy, mm, dd) + 1) % 7;
 }

Thanks, 24! Now there's a good example of what I mean. It's unclear, and incorrect for dates before the Julian/Gregorian switch, but it actually appeared in some version of the standard C library code (not the one for Unix, incidentally; the Unix calendar program got the calendar switchover correct from the start, back in the early 1970s).

Perfect example of unclear: what is 146097? A little fiddling around with arithmetic reveals that it is equal to (400 * 365.2425), so that's 400 years, in units of days. 400 years happens to be the length of the leap year cycle, so that's suggestive, but still, what exactly is it doing there?

And that's just one of a dozen constants that are all manipulated in various opaque ways. Figuring it out might take hours, especially for some poor guy who'd never happened to do calendar algorithms before. Most people would never go to the trouble; it would just remain a write-only black box. If there were a bug in it (and as I said, there is) it could stay there forever.

That's why I went to some trouble to invent a clearer version - which is also shorter, notice, neglecting comments. Writing short, clear code is hard, but pays off. -- DougMerritt

I don't think it's fair to protest that the code above is "long" and "unclear" when comparing it with yours. Your code is about the same length, but it's missing the bits that actually do the work: the implementations of total_leap_days and is_leap_year, the contents of days_in_month, the definition of MISSING_DAYS_IN_SEP_1752. None of those things is terribly hard, but the code you criticize as being "long" is actually shorter than yours once the details are filled in, and the details are precisely the bits that are implemented obscurely here.

Ah, dueling algorithms! Ok, I deleted the word "long"; you're right, mine is, in toto, longer. But are the alternatives "unclear"? You bet! And I added what you called "the missing bits that actually do the work". As you can now see, the work they do is trivial and clear and merely reflect the definition of leap year and days per month etc, which is why I didn't bother to post them before. They're trivial to infer. Anyway hopefully I didn't screw something up when editing, but I still claim that my algorithm is far clearer than the alternative you present. Mine has no "magic" whatsoever! The only constants I use are those which are given in the problem definition itself, like "7" is days per week, "100" is years in a century...trivial. And so are the operations on them. Yours uses many magic numbers and many magic operations. I mean, like how can you claim "153" is just obvious? I never heard of it. -- DougMerritt

Here's what I consider a reasonably clear implementation. It approaches the details in the same sort of fashion as the obscure code above; in practice a moderate-sized lookup table would be a better bet than all the clever modular calculations, for efficiency as well as clarity. It's also explicit about what it assumes happened to the calendar when, for the Julian-Gregorian changeover. -- GarethMcCaughan

 /* Number of days since the date that would have been 0000-03-01
  * if the Gregorian calendar were projected infinitely far into
  * the past. yyyy,mm,dd are the date in usual notation. We assume
  * these dates are for use in a country (such as England) that
  * switched from the Julian to the Gregorian calendar by omitting
  * the 11 days beginning on 1752-09-03; pre-Gregorian dates in
  * some other countries, such as Spain, will require tweaking.
  */
 int gregorian_date(int yyyy, int mm, int dd) {

   /* Check for Julian-to-Gregorian change.
    */

   bool pre_gregorian = (yyyy < 1752
                         || (yyyy == 1752 && (mm < 9
                                              || (mm == 9 && dd < 3))));

   /* Tweak to make the year start on March 1, so that
    * leap days come at the end, and count months from
    * March = 0.
    */

   if (mm >= 3) mm -= 3;
   else { mm += 9; yyyy -= 1; }

   /* Separate the year into century and remainder.
    * Now there are 365*4+1 = 1641 days per 4-year group,
    * increasing by 365,365,365,366 for years 1,2,3,4 mod 4.
    * Similarly there are 36524*4+1 = 146097 days per
    * 4-century group, increasing by 36524,36524,36524,36525
    * for centuries 1,2,3,4 mod 4.
    */

   int cc = yyyy/100, yy = yyyy%100;
   int days_to_year_start = (146097*cc)/4 + (1461*yy)/4;

   /* Month lengths starting in March go 31,30,31,30,31, 31,30,31,30,31, 31,28+.
    * Since February is now our last month it doesn't matter how long it is,
    * so these are repeating with period 5. The fact that the following works
    * is still a bit magical, but hopefully now less surprising.
    */

   int days_to_month_start = (153*mm+2) / 5;

   /* Now we're done: put those pieces together.
    */

   return days_to_year_start + days_to_month_start + dd-1
          + pre_gregorian ? 11 : 0;
 }

 /* Day of week for a given date; see above for the interpretation
  * of dates before the Gregorian changeover. Day 0 is Sunday,
  * 1 is Monday, ..., 6 is Saturday.
  */
 int day_of_week(int yyyy, int mm, int dd) {
   /* Our mythical day 0000-03-01 was a Wednesday.
    */
   return (gregorian_date(yyyy,mm,dd) + 3) % 7;
 }

See above comments. I stand by my claim that things like this are extremely unclear compared with the code I presented (and have now supplemented with missing definitions). -- DougMerritt

Doug, I think you may have thought I was claiming more than I was! I'm not saying that the code above is clearer than yours (with details filled in, of course), nor that it's better. Only that (1) you claimed "My code is clear, this other code is unclear" when your code was *missing* the bits corresponding to the unclear stuff in the other code; and that (2) the oh-so-clever modular arithmetic stuff doesn't have to be quite as opaque as in its first presentation on this page. As I said, for a real implementation that needs to be efficient you'd do most of the work in lookup tables. I didn't intend to make this into an algorithm pissing contest.

There's no getting around the fact that the oh-so-clever stuff is hard to understand. There's no way of making it not be hard to understand. It can be fully explained, but then the explanations get long and mathsy.

"How can you claim 153 is just obvious?" I didn't claim that it is - in fact, I described it as "still a bit magical" - and I don't think it is obvious. Why do you ask? :-) - But I can explain why it's the right number; see below.

In case anyone's interested, here's a brief explanation of why those clever multiply-and-divide things work. I repeat that I'm not claiming that this is easy, or that the best implementation of date-handling code should work this way, or that it's possible to make a maximally clear implementation out of them. But the maths is a little bit interesting ...

Consider the sequence of values (a*n+b)/m, where a,b,m are fixed and n = 0,1,2,3, etc. (And "/" means rounding downwards, like in C.) Then the following things are true. (1) On average, this increases by a/m each time n goes up by 1. (2) The increases repeat with period m. (3) Each increase is either floor(a/m) or ceiling(a/m): two values that differ by 1. (4) The two kinds of increase are, in some sense, as evenly intermixed as possible given how many of each there are.

So, if you want increases repeating in groups of 5 like 31,30,31,30,31, then clearly we need m=5 (for repetition of period 5) and a=31+30+31+30+31=153. You can't get any more evenly intermixed than ABABA, so the thing should be achievable. Then it's just a matter of seeing what value of b will work, and it turns out that 2 does the job.

If you want repetition in groups of 4 like 365,365,365,366, then clearly we need m=4 and a=365+365+365+366=1461. This is a particularly simple case because there's only one "large" increase. We have the following general observation: if a=k*m+1 and b=0 then our sequence is k*n + n/m, whose increases are now obviously k (when n isn't increasing to a multiple of m) and k+1 (when it is). That's why b=0 is appropriate for the two leap-year counting bits.

Finally, what's the right way to approach code like mine above? (Other than rewriting it to use algorithms that are easier to understand.) You read the explanations until you understand why it's plausible that something like what's used might work and why you only need to look at m+1 consecutive values of n to be sure whether it's right; then you just try it. There aren't very many cases to check. Write a one-liner in Python or Perl or something of the kind and observe that the right numbers come out. :-)

Oh, one other thing. My code is in fact incorrect :-) because its leap year calculation is busted for dates while the Julian calendar was in use. I repeat: I never claimed it should be done that way, only that if it is it needn't be 100% cryptic and that the magic numbers can be explained. -- GarethMcCaughan

Thanks for explaining that approach; I hope any future WikiGnomes will leave that here.

So now that we've both explained ourselves better, can I tempt you into preferring my algorithm as being overall clearer? :-) -- DougMerritt

I've already said, several times, that yours is clearer. I never (once the relevant bits of your code were actually there!) claimed it wasn't. If I were actually implementing a "perpetual calendar" then I might (depending on the application) choose a different trade-off between clarity and efficiency, but it wouldn't be by using the code I wrote above; I'd do something similar to your code, but keep the March-1st trick, make the days-in-month lookup table store days from year start to month start instead of days in month (avoiding a loop) and do the leap-year checking and counting with a single division-and-remainder by 400 and a couple of 400-element lookup tables. -- GarethMcCaughan

Pope Gregorius XIII (with the help of the astronomer Christopher Clavius (1537-1612)) in 1582 declared that the day after 4 October 1582 should be 15 October 1582.

In England and the American colonies, The day after 1752.09.02 was 1752.09.14.