We have previously given two algorithms to calculate the day of the week, one in the Standard Prelude and one in the exercise on Zeller’s Congruence. In today’s exercise we give three more algorithms to calculate the day of the week.

Our first method is due to Carl Gauss, and is based on moving January and February to the end of the preceding year, then fitting a straight line through the number of days in each month. Gauss gives the formula w = \left( d + \lfloor 2.6 m - 0.2 \rfloor + y + \lfloor \frac{y}{4} \rfloor + \lfloor \frac{c}{4} \rfloor - 2c \right) \pmod{7} where Y is the input year, except that it is reduced by 1 in January and February, d is the day of the month, m is the number of the month, with 1 for March through 12 for February, y is the last two digits of Y, c is the first two digits of Y, and w is the day of the week, with 0 for Sunday through 6 for Saturday. For instance, June 24, 2011 is calculated as 24 + floor(2.6×4−0.2) + 11 + floor(11÷4) + floor(20÷4) – 2×20, modulo 7, which is 5 for Friday.

Our second method is due to Tomohiko Sakamoto, who gives a table of offsets for the days of each month from the day at the start of the year: t = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}. Then Sakamoto subtracts 1 from the input year in January and February and calculates the day of the week with the formula \left( y + \lfloor \frac{y}{4} \rfloor - \lfloor \frac{y}{100} \rfloor + \lfloor \frac{y}{400} \rfloor + t[m-1] + d \right) \pmod{7}. For instance, June 24, 2011 is calculated as 2011 + floor(2011÷4) − floor(2011÷100) + floor(2011÷400) + t[6−1] + 24 = 2011 + 502 – 20 + 5 + 3 + 24 = 2525, modulo 7, which is 5 for Friday.

Our third method is due to John Horton Conway, and is intended for mental calculation. Conway’s method is based on calculating the anchor day for the requested century, the doomsday for the requested year, and interpolating from various repetitions of the doomsday through the year.

The anchor day is calculated as \left( 5c + \lfloor \frac{c-1}{4} \rfloor \right) \pmod{7} + Thursday, where c is the century; note that century years, such as 2000, are part of the succeeding century, so c=21 for the year 2000. For example, the anchor day for the 21st century is Tuesday, calculated as 5×21 + floor(20÷4), modulo 7, plus Thursday. Anchor days repeat every four centuries, in the cycle Friday, Wednesday, Tuesday, Sunday starting from the year 1800.

The doomsday is calculated by dividing the last two digits of the year by 12 to calculate the quotient and remainder. Then the doomsday is the quotient, plus the remainder, plus the quotient of the remainder divided by 4, plus the anchor day for the century. For example, the doomsday for 2011 is Monday, calculated as 0 + 11 + floor(11÷4) = 13, which is 6 modulo 7, plus the anchor day Tuesday.

Once the doomsday is known, the day of the week is calculated by locating the nearest doomsday in each month, which can be memorized in the following manner: For April, June, August, October, and December, the doomsday is the month number: 4/4, 6/6, 8/8, 10/10, and 12/12. For May, July, September, and November, the doomsday can be calculated by the ditty “I worked 9 to 5 at 7-11″ which gives 5/9, 7/11, 9/5, and 11/7. The last day of February is a doomsday, whether a common year or a leap year, and this gives an easy way to calculate the day of the week for March, where doomsday is 3/0 (the “zeroth” day of March). All that’s left is January, for which the doomsday is 1/10 in common years and 1/11 in leap years.

Thus, the day of the week for June 24, 2011 is calculated as 24−6=18 ≡ 4 (mod 7) days past the doomsday, which gives an answer of Friday. Conway claims to be able to calculate any day of the week in two seconds, though I confess I have not been able to make the required calculations reliably except by using pencil and paper to assist.

Your task is to write programs to calculate the day of the week using the three functions described above; for Conway’s algorithm, you should calculated the doomsday for the year rather than the day of the week for the date. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2


Get every new post delivered to your Inbox.

Join 576 other followers