Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Algorithm Alley


APR95: ALGORITHM ALLEY

ALGORITHM ALLEY

Computing the Day of the Week

Kim S. Larsen

Kim has a PhD in computer science and is primarily interested in databases, algorithmics, and data structures. He can be contacted at Ærtebjerggårdvej 31, DK-5270 Odense N, Denmark or at [email protected].


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 [email protected], 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 <=:><I>r</I><<I>k</I>. Now <I>q</I> is defined to be the integer division of <I>n</I> and <I>k</I> (written <I>n</I>/<I>k</I>), and <I>r</I> is defined to be <I>n mod k</I>).
<P>

What about April? Well, if March 1 is a Tuesday, then April 1 is a Friday. So, the formula needs to be shifted. There are 31 days in March, and since <I>31 mod 7=3</I>, the formula that would work in April is <I>(D+3) mod 7</I>. Of course, the same problem arises when we go from April to May, except that the shift will be 2, since April has only 30 days. <a href=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

In going from one year to the next, we observe that March 1, 1995 is a Wednesday. This means that changing to a new year should have the effect of adding one to our formula. That is easy: We simply add Y to what we already have. Again, we have to make sure things start out right. Since 1994 mod 7=6, we must subtract 6 when we combine Y with the formula we already have. Example 2(a) then becomes a new and better formula.

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]);
}


Copyright © 1995, Dr. Dobb's Journal


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.