Input description: A particular calendar date d, specified by month, day, and year.
Problem description: Which day of the week did d fall on according to the given calendar system?
Discussion: Many business applications need to perform calendrical calculations. Perhaps we want to display a calendar of a specified month and year. Maybe we need to compute what day of the week or year some event occurs, as in figuring out the date on which a 180-day futures contract comes due. The importance of correct calendrical calculations is perhaps best revealed by the furor over the ``millennium bug,'' the crisis in legacy programs that allocate only two digits for storing the year.
More complicated questions arise in international applications, because different nations and ethnic groups around the world use different calendar systems. Some of these, like the Gregorian calendar used in most of the world, are based on the sun, while others, like the Hebrew calendar, are lunar calendars. How would you tell today's date according to the Chinese or Arabic calendar?
The algorithms associated with calendrical calculations are different from the other problems in this book, because calendars are historical objects, not mathematical ones. The issues revolve around specifying the rules of the calendrical system and simply implementing them correctly, rather than designing efficient shortcuts for the computation.
The basic approach behind calendar systems is to start with a particular
reference date and count from there.
The particular rules for wrapping the count around into months and years
is what distinguishes a given calendar system from another.
To implement a calendar, we need two functions, one that given a date
returns the integer number of days that have elapsed since the reference
start date, the other of which takes an integer n and returns the calendar
date exactly n days from the reference date.
This is analogous to the ranking and unranking rules for combinatorial
objects, such as permutations (see Section 
).
The major source of complications in calendar systems is that the solar year is not an integer number of days long. Thus if a calendar seeks to keep its annual dates in sync with the seasons, leap days must be added at both regular and irregular intervals. Since a solar year is 365 days and 5:49:12 hours long, an extra 10:48 minutes would have to be accounted for at the end of each year if we were simply to add a leap day every four years.
The original Julian calendar (from Julius Caesar) did not account for these extra minutes, which had accumulated to ten days by 1582 when Pope Gregory XIII proposed the Gregorian calendar used today. Gregory deleted the ten days and eliminated leap days in years that are multiples of 100 but not 400. Supposedly, riots ensued because the masses feared their lives were being shortened by ten days. Outside the Catholic church, resistance to change slowed the reforms. The deletion of days did not occur in England and America until September 1752, and not until 1927 in Turkey.
The rules for most calendrical systems are sufficiently complicated and pointless that you should lift code from a reliable place rather than attempt to write your own. We identify suitable implementations below.
There are a variety of ``impress your friends'' algorithms that enable you to compute in your head on which day of the week a particular date occurred. Such algorithms often fail to work reliably outside the given century and should be avoided for computer implementation.
Implementations: Dershowitz and Reingold provide a uniform algorithmic presentation [DR90, RDC93] for a variety of different calendar systems, including the Gregorian, ISO, Julian, Islamic, and Hebrew calendars, as well as other calendars of historical interest. Further, they provide Common Lisp and C++ routines to convert dates between calendars, day of the week computations, and the determination of secular and religious holidays. These are likely to be the most comprehensive and reliable calendrical routines you will be able to get your hands on, and are available at http://emr.cs.uiuc.edu:80/reingold/calendars.html.
A nice package for calendrical computations in Mathematica by Ilan Vardi is available in the Packages/Miscellaneous directory of the standard Mathematica distribution, and also from MathSource. Vardi's book [Var91] discusses the theory behind the implementation, which provides support for the Gregorian, Julian, and Islamic calendars.
Gregorian calendar computations implemented in C appear in [BR95]. This code uses 1582 as the date of the calendar reform, instead of the standard UNIX date of 1752. The code for these algorithms is printed in the text and are available on disk for a modest fee.
Notes: The most comprehensive discussion of calendrical computation algorithms are the papers by Dershowitz and Reingold [DR90, RDC93]. These papers are superseded by their book [DR97]. Histories of the Gregorian calendar appear in [BR95].
Related Problems: Arbitrary-precision arithmetic (see page ),
generating permutations (see page ).
