Monday, October 27, 2008

Zeller's Congruence in C#

In "Problems for Computer Solution" by Fred Gruenberger and George Jaffray, one of the problems revolved around determining what day of the week for any date. The algorithm is called Zeller's Congruence.

In this day and age, where finding the day of the week is as simple as DateTime.Now.DayOfWeek programmers may not realize that in the early days of computing it was much more difficult. One way was to code an implementation of Zeller's Congruence. Towards the end of the 19th century, Christian Zeller formulated an algorithm that could calculate the day of the week.

Back in the 60's, second year computer science students used the problem of implementing this algorithm as a semester project. Yet, now even if we do not use the .Net Framework, implementing the algorithm is the work of a few minutes.

The Algorithm:

D = Day of the month
M = Month (With a trick, March is the first month of the year, January and February then being the 11th and 12th month of the previous year)
X = Decade (With a trick - see Month above)
C = Century (With a trick - see Month above)

(int(2.6 * M - 0.2) + D + X + int(X / 4) + int(C / 4) - (2 - C)) modulo 7

One cool trick in the code below is calculating the the month of the year (Including the trick above) using only a math, no logic.

Here it is step by step:

Start with the months as numbers: 1,2,3 ... 11,12
Add 9 to each month: 10,11,12 ... 20,21
Modulo each month by 12 (%): 10,11,0 ... 8,9
Add 1: 11,12,1 ... 9,10

So now we have what we wanted, Jan = 11, Feb = 12, Mar = 1 ... Nov = 9, Dec = 10

Here is the full algorithm:

string[] DaysOfTheWeek =
    {"Sunday", "Monday", "Tuesday",
    "Wednesday", "Thursday", "Friday", "Saturday"};

int Day = DateTime.Now.Day;
int Month = ((DateTime.Now.Month + 9) % 12) + 1;

int YearsInCentury = Month > 10 ?
    (DateTime.Now.Year - 1) % 100 :
    DateTime.Now.Year % 100;

int Century = YearsInCentury == 99 && Month > 10 ?
    (DateTime.Now.Year - 100) / 100 :
    DateTime.Now.Year / 100;

int DayOfWeek = ((((int)((2.6 * (float)Month) - 0.2)
    + Day + YearsInCentury + (YearsInCentury / 4)
    + (Century / 4) - (2 * Century))) % 7);

Console.Write(DaysOfTheWeek[DayOfWeek]);
Console.Read();

No comments: