3
$\begingroup$

I came across this algorithm recently to calculate day of the week for any year.

int y0 = year - (14 - month) / 12;
int x = y0 + y0/4 - y0/100 + y0/400;
int m0 = month + 12*((14 - month)/12) - 2;
int d0 = (date + x + (31*m0)/12)%7;
switch (d0) {
    case 1: return "Monday";
    case 2: return "Tuesday";
    case 3: return "Wednesday";
    case 4: return "Thursday";
    case 5: return "Friday";
    case 6: return "Saturday";
    case 0: return "Sunday";
}

How does this algorithm work? I see a lot of magic numbers in calculations above, but its difficult to understand the intuition behind this algorithm

$\endgroup$
  • $\begingroup$ if it written in c, dose month and year are int and start from zero or not (this might sound silly though) $\endgroup$ – nima_moradi Jun 19 '18 at 17:14
7
$\begingroup$

As mentioned in a comment, this program is a variant on Zeller's congruence.

Here are the steps:

  1. It's good to know that the Gregorian calendar (which is what we are using) repeats every 400 years. In the 400 year cycle, every fourth year is a leap year except for the centuries other than the one at the start of the cycle. In other words, in the 400-year cycle starting 2000 and ending 2399, there are 97 leap years: all the years divisible by 4 except 2100, 2200 and 2300.

    There are 365 days in a normal year, which is 52 weeks and one day. A leap year has an extra day. So the 400-year cycle, which has 303 normal years and 97 leap years, is 52*400 weeks plus (303 + 97*2 = 497) days. 497 days is exactly 71 weeks, so the cycle is an exact number of weeks, which means the weekday for a given date is the same for the "same date" in every cycle. (The same date meaning the same day, month and year mod 400.)

    Since we're only interested in which weekday a date is, and not the total number of days since some determined starting point, we can do all computations mod 7. So if we know the weekday for some particular date, we can find the weekday for the same day/month in another year by adding the number of years and then the number of intervening leap days.

    int x = y0 + y0/4 - y0/100 + y0/400;
    

    y0 is explained below; if you think of it as the number of years from the beginning of (some) 400 year-cycle, then x is just the number of years plus the number of leap years: y0/4 (every fourth year) - y0/100 (except for centuries) + y0/400 (other than the centuries which start a cycle). If we had computed y0 as years into the current cycle, we could have avoided the y0/400 term.

  2. The fact that a leap day falls into the middle of a year complicates that computation. To make it simpler, we start the cycle at March 1 instead of January 1, effectively moving January and February to the previous year. That puts the leap day at the end of the year, so we can evaluate the number of leap days by counting the number of leap years, as above. As we'll see below, this also has the advantage of making the alternation of month lengths more regular; aside from February, months more or less alternate between 31 and 30 days.

    int y0 = year - (14 - month) / 12;
    int m0 = month + 12*((14 - month)/12) - 2;
    

    Those lines are trying to way too hard to be clever, and end up being terrible because of the slowness of division (even though division by 12 can be performed with multiplies, and even though the compiler can figure out that it's only necessary to do it once. The code would be clearer and faster if it were written in the obvious way:

    int y0 = year, m0 = month - 2;
    if (m0 < 1) { ++y0; m0 += 12; }
    
  3. Essentially, we now have a weekday offset of March 1 in the specified year from the March 1 which starts the cycle. Now we just need to figure out the adjustment for the months between March and the specified month. Each of these months will move the weekday by either two (30 mod 7) or three (31 mod 7) days. Months mostly alternate between 31 and 30 days, except although sometimes there are two 31-day months in a row. (As mentioned above, we can ignore February here because we're only counting months which come before the specified date, and with February shifted to the end of the year, it is never before any date in the year.)

    int d0 = (date + x + (31*m0)/12)%7;
    

    (31 * m0) / 12 for m0 in the range [1, 12] produces the sequence {2, 5, 7, 10, 12, 15, 18, 20, 23, 25, 28, 31}. The adjacent differences in that sequence are {3, 2, 3, 2, 3, 3, 2, 3, 2, 3, 3} which happen to correspond to the lengths of the months (mod 7) starting at March. (The pairs of consecutive 3s correspond to July/August and December/January.) So adding this to the year adjustment x and the date in the month date and then reducing the sum mod 7 gives us the day in the week with the week starting three days before March 1 of (every) cycle. (Three days before because (1) the magic formula (31 * m0) / 12 starts with 2, not 0, and (2) the day of the month starts with 1, not 0. So the formula is off by 3.)

    This is not the only way of performing this calculation. As it happens, exactly the same sequence is produced with (13 * m0 - 1) / 5. Either way, the cleverness is not justified by efficiency; division is a lot slower than a simple table lookup:

    /* Not optimal but it corresponds to the above computation */
    static const char month_adjust[] = { 
        2, 5, 7, 10, 12, 15, 18, 20, 23, 25, 28, 31
    };
    int d0 = (date + x + month_adjust[m0]) % 7;
    

    The above table could be reduced to three bits per month, since only the value mod 7 is important. That means that the lookup table could be replaced with a magic integer constant and a bit-shift, but the potential gain is probably insignificant. I'll leave the details as an exercise for would-be code golfers.

  4. March 1 of every cycle is a Wednesday, and that needs to correspond to the value 3 of that computation. The mapping between modulo and day of the week is provided by the switch statement:

    switch (d0) {
        case 1: return "Monday";
        case 2: return "Tuesday";
        case 3: return "Wednesday";
        case 4: return "Thursday";
        case 5: return "Friday";
        case 6: return "Saturday";
        case 0: return "Sunday";
    }
    

    I would have used a lookup table instead of a switch, which leads to more direct code:

    static const char* weekdays = { 
        "Sunday", "Monday", "Tuesday",
        "Wednesday", "Thursday",
        "Friday", "Saturday"
    };
    return weekdays[d0];
    
$\endgroup$
  • $\begingroup$ Very nice! It may be worth to mention it is Zeller formula. $\endgroup$ – Evil Jun 19 '18 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.