# ALGORITHM ALLEY

## Computing the Day of the Week

Introduction

### by Bruce Schneier

Thirty days have September, April, June, and November.... So the song goes. Or did you learn to count the months forward and backwards on your fingers, with even-numbered fingers being the short months? Mnemonics such as these work well for people (I recited that silly song well into adulthood) but are less intuitive for computers. Of course, you can write a program that manually computes the day of the week for any date, using a whole lot of If-Then-Elses, or a few Case statements.

However, I like the technique Kim Larsen presents in this month's "Algorithm Alley" because it approaches the problem from another direction. There isn't really a mathematical formula for computing the day of the week for any given date, but maybe we can cobble one together. The formula works, and you have an easy-to-program mathematical formula for computing the day of the week automatically.

By the way, if you've developed a clever new algorithm, or come up with a new twist on an old idea, I'd love to hear from you. Please contact me at schneier@chinet.com, or just drop a note to me at the DDJ offices.

Have you ever wondered how your computer knows that today is Wednesday? Even if your machine has been down and you specify a new date when starting it up again, it immediately knows which day of the week it is.

When you were a kid, you probably saw tables with entries for the date, the month, and the year. You added up a few numbers and another table gave you the day of that date. Of course, such tables could be hardwired into your computer's operating system. However, there exists a simple formula for computing the correct day of the week. This formula takes up very little space, whereas a collection of tables covering just a few hundred years would take up quite a bit.

If your machine is not capable of computing the day of the week, then you can use this formula in your own programs and applications.

### Creating a Formula

The starting point for the formula is a date represented by the variables D, M, and Y. For example, for the date March 1, 1994, D=1, M=3, and Y=1994. Our goal is to compute a number between 0 and 6, where 0 represents Monday, 1 represents Tuesday, 2 represents Wednesday, and so on.

It turns out that March 1, 1994 is a Tuesday, so the formula D mod 7 would actually work for the rest of the month of March. For example, the 18th is a Friday, and 18 mod 7=4, which represents Friday. (Remember that integer division and modulo are closely connected. For example, 26 divided by 7 is 3 with the remainder 5. This means that the integer division of 26 by 7 equals 3, and 26 modulo 7 (abbreviated 26 mod 7) equals 5. This also implies that 19 mod 7=12 mod 7=5 mod 7=5. In fact, this works similarly for negative numbers, so --2 mod 7=5, --9 mod 7=5, and so on.

More formally, it can be shown that for any integers n and k, n can be written as n=qk+r in exactly one way, where q and r are also integers and 0 Table 1 lists the shift information for all months. Note that in order to obtain as much regularity as possible, the short month of February (and, hence, also January) has been moved to the end.

Example 1(a) is a formula that imitates the pattern depicted in the shift column. The division is integer division, so the result is rounded down to the nearest integer. The interesting values for this function are given in Table 2. Intuitively, when M increases with one (going from one month to the next), 2M increases with two, and 3(M+1)/5 increases three out of five times, which is what we need to imitate this repeated pattern 3,2,3,2,3 of shifts (indicated by the curly brackets to the right of the table). Notice that since we are working modulo 7, going from 6 to 2 is an increase of 3 (counting 6,0,1,2).

We have now found a formula to adjust our calculations correctly when we go from one month to the next, and we want to add this formula to our first attempt, namely D mod 7. The only problem is getting it to start out right. Again using March 1, 1994 (that is, M=3), notice that in Example 1(b) 8 mod 7=1, so we must subtract 1 when the whole formula is put together. Working modulo 7, this is the same as adding 6, since -1 mod 7=6 mod 7=6.

Now the formula in Example 1(c) will work for the rest of the year. In fact, since we have placed January and February at the end of Table 1, the formula will also work for these two months in 1995, provided that we refer to these as months 13 and 14. This is because they start a new, though incomplete, 3,2,3,2,3 sequence. To make a nicer formula, we adopt the convention from now on of treating January and February as the months 13 and 14 of the previous year.

### Incorporating the Year

Our next problem occurs with 1996--a leap year. March 1 is a Friday, not a Thursday, as our formula would currently predict. So we need to add one every time we enter a leap year. The rule is that a year is a leap year if it is divisible by four, except that years divisible by 100 are only leap years if they are also divisible by 400. In effect, we add Y/4--Y/100+Y/400 to what we already have. Again, we must make sure that we start out correctly. Since (1994/4--1994/100+1994/400) mod 7=(498--19+4) mod 7=483 mod 7=0, no adjustments need to be made, and Example 2(b) is our final formula. This formula works indefinitely (unless we change calendar systems). As an example, let us try July 4, 2000: (4+2*7+3(7+1)/5+2000+2000/4--2000/100+2000/400) mod7=(4+14+4+2000+500--20+5) mod 7=2507 mod 7=1, so it is a Tuesday.

This also works backwards in time; however, we switched to the current calendar system on Thursday, September 14, 1752, so it does not work for dates earlier than this. But if we try the standard "where were you when..." date of November 22, 1963, we find: (22+2*11+3(11+1)/5+1963+1963/4--1963/100+1963/400)mod7=(22+22+7+1963+490--19+4)mod 7=2489 mod 7=4, which is a Friday.

These formulas have been implemented in Example 3, a C program for computing the day of the week automatically.

#### Table 1: Shift information for each month.

Month   # Days  Shift
March   31       --
April   30        3
May     31        2
June    30        3
July    31        2
Aug.    31        3
Sept.   30        3
Oct.    31        2
Nov.    30        3
Dec.    31        2
Jan.    31        3
Feb.    28        3

Table 2 A function for imitating the shift pattern. Example 1 Creating a formula that works for the year 1994. Example 2 Extending the formula to account for different years.

#### Example 3: The formula expressed as a C program.

/* Computing day of the week from the date. It is assumed that input */
/* represents a correct date.                                      */
#include <stdio.h>
char *name[] = { "Monday",
"Tuesday",
"Wednesday",
"Thursday",
"Friday",
"Saturday",
"Sunday"
};
void main(){
int D,M,Y,A;
printf("Day: "); fflush(stdout);
scanf("%d",&D);
printf("Month: "); fflush(stdout);
scanf("%d",&M);
printf("Year: "); fflush(stdout);
scanf("%d",&Y);
/* January and February are treated as month 13 and 14, */
/* respectively, from the year before.                  */
if ((M == 1) || (M == 2)){
M += 12;
Y--;
}
A = (D + 2*M + 3*(M+1)/5 + Y + Y/4 - Y/100 + Y/400) % 7;
printf("It's a %s.\n",name[A]);
}