Tuesday, April 15, 2008

An Improved Doomsday Algorithm

Introduction

The Doomsday Algorithm can be used to mentally calculate the day of the week on which any date falls. With a little effort most people can learn to apply the algorithm mentally without pencil or paper. If you're interested, you can learn the method behind the Doomsday algorithm at rudy.ca or at Bob Goddard's site.

My purpose is not to describe the details of the Doomsday algorithm, but to describe an improved method to implement part of it (calculating Doomsday for an arbitrary year) which I have discovered. Below, I'll describe the method first using mathematical notation, which unfortunately appears needlessly complicated, but then I'll show how to easily perform the calculations mentally without the need for memorizing cumbersome equations.

Background

First, a key component of using the Doomsday Algorithm is knowing how to calculate Doomsday for an arbitrary year, after which you can figure out the day of the week for any date in that year. The usual formula described to make this calculation can be written as

int(y/12) + y mod 12 + int((y mod 12)/4)

where y is the last two digits of the year. The notation "int (a/b)" means to take only the integer part of a/b; "a mod b" means to divide a by b and take the remainder. For example, int (4/3) = 1, and 10 mod 7 = 3.

This result mod 7 is added to Doomsday for the base year of the century (e.g. 1900 or 2000) to get the final answer. For 1900, Doomsday is Wednesday (3, where Sunday is 0).

For example, Doomsday 1953 is

int(53/12) + 53 mod 12 + int ((53 mod 12)/4)

= 4 + 5 + int(5/4) = 4 + 5 + 1 = 10 mod 7 = 3

Adding 3 (Doomsday for 1900) to Wednesday gives Saturday.

This formula is not as bad as it looks, but it does require modular arithmetic, four divisions, and remembering three different numbers to add together. For me, this was always the most tedious part of applying the Doomsday algorithm.

An Easier Way!

Fortunately I have discovered an easier way to make the same calculation with much less effort!

For a leap year only, my new simpler formula is

7 - (y/2) mod 7

where y is the last two digits of the year. This result is added to the Doomsday for the base century year as before.

For example, for 1980 Doomsday is

7 - (80/2) mod 7 = 7 - 40 mod 7 = 7 - 5 = 2.

Adding to Doomsday 1900, the final answer is 2 + Wednesday = Friday. While my formula is simpler than the original, it still involves some modular arithmetic and divisions. But there is a simple shortcut which makes applying the formula easy.

Here's the trick: To apply this in practice mentally, you would simply divide the leap year by 2 and subtract the result from the next largest multiple of 7. No divisions by 12 or 4, no modular arithmetic, and less memory effort is needed. If you can divide an even number by 2 and add and subtract, you can do it quickly and easily.

Even better: If the year is not a leap year, just repeatedly add 11 to the year until you get a leap year and apply the same formula. At most this will require adding 33 to the year.

Examples

Returning to the first example, Doomsday 1953 is the same as Doomsday 1953 + 11 = Doomsday 1964.

Dividing 64 by 2, the result is 32 which subtracted from 35, the next multiple of 7 to give 3, the same as above. Added to Wednesday (Doomsday 1900) the result is again Saturday.

Another example: 1962 is not a leap year, so we add 22 to get 1984. 84/2 = 42, which is a multiple of 7 so the result is 0 and Doomsday is Wednesday. (In this case the original formula might be easier since 84 is a multiple of 12). If you're familiar with the traditional method given above and my easier method, it is easy to apply the simplest one for any case, which I believe is usually the newer formula given here. I only find the older method easier if the year is a multiple of 12. I especially like the new method for finding the Doomsday of an odd year, which I always hated to do using the older method.

Update: When the process of adding 11 takes you across a century boundary which is not a leap year (e.g. 1900 or 2100), the process is similar as pointed out by Robert Goddard in a comment to this post. As an example of crossing non leap year centuries, I'll use his example of 2095. We add 95+33=128. Since we crossed a non leap year (2100) use "128" instead of "28". We divide by 2 to get 64, and subtract from a big multiple of 7, to get 70-64=6. Added to Tuesday (Doomsday 2000, the century we started in) and the result is Monday. When crossing century years that are leap years, like 2000, the original method works without adjustment.

It is easy to verify this method of adding 11 works by examining the following table which I have borrowed from rudy.ca. In this table the leap years are bold. You can see that every leap year is the final year in a chain of 4 years which differ by 11 and which have the same Doomsday. Every non leap year is a member of such a chain. Because it is easy to find Doomsday for a leap year with my method, it is therefore simple to find Doomsday for any year.

 Sun  Mon  Tue  Wed  Thu  Fri  Sat
---- ---- ---- 1900 1901 1902 1903
---- 1904 1905 1906 1907 ---- 1908
1909 1910 1911 ---- 1912 1913 1914
1915 ---- 1916 1917 1918 1919 ----
1920 1921 1922 1923 ---- 1924 1925
1926 1927 ---- 1928 1929 1930 1931
---- 1932 1933 1934 1935 ---- 1936
1937 1938 1939 ---- 1940 1941 1942
1943 ---- 1944 1945 1946 1947 ----
1948 1949 1950 1951 ---- 1952 1953
1954 1955 ---- 1956 1957 1958 1959
---- 1960 1961 1962 1963 ---- 1964
1965 1966 1967 ---- 1968 1969 1970
1971 ---- 1972 1973 1974 1975 ----
1976 1977 1978 1979 ---- 1980 1981
1982 1983 ---- 1984 1985 1986 1987
---- 1988 1989 1990 1991 ---- 1992
1993 1994 1995 ---- 1996 1997 1998
1999 ---- 2000 ---- ---- ---- ----

Also, if you examine the table you will notice that the first year in a chain is always 6 more than another year with the same doomsday, the last year in a chain is 6 less than a year with the same doomsday, and the two years on either end are members of different chains. Understanding this relationship makes it very easy to come up with all the years in a century on which a certain date falls on the same day of the week.

13 comments:

Bob Goddard said...

Mike, thanks for this breakthrough simplification!

You say your method fails if you add to the year and cross a century, and you give an extra rule, requiring us to add 1 in this event. But I have good news: there's no need for this warning and the extra rule. Just do the following:

When adding 11s to y (the last two digits of the year), it's OK if you go over 100. Don't even think about overflowing ("carry the one") into the next century. Just continue the math, and in the final step stick with the original century.

For example, for the year 2095, we add 95+33=128. Divide by 2 to get 64, and subtract from a big multiple of 7, to get 70-64=6. Added to Tuesday (Doomsday 2000) the result is Monday.  It would be wrong to equate 2095 with 2128, because 2100 is not a leap year.

Thanks again.

Mike said...

Thank you Bob! You're addition to my method is very elegant. I've added a link to your calendar page in my sidebar too.

ki said...

Divide last leap year by 2, subtract the lost years, calculate modulo 7 and find the complement to 10.

For example
1995=1992+3

92/2 ==> 46 - 3 ==> 43 ==> 1 to 10 ==> 9 ==> 2 ==> Doomsday is a Tuesday

Best
hcs

jackerz said...

regarding the ki/hcs proposal:

This suggestion of decomposing the 2-digit year to leap quotient and remainder has been suggested by Dr. Yingking Yu in Sept. 2010:
http://improvedddabyykyu.blogspot.com/
(in section 3.2 The Highest Multiple of 4 Algorithm)
The proposal is a variant of YingKing's method.

I still prefer the odd+11 method because:
1) it doesn't involve any division by 4 calculation for quotients and remainders
2) it doesn't require one to remember an intermediate variable (e.g. the remainder) that was subtracted after division by 2
3) it is easier to add 11 than to subtract a variable remainder

Bill Jefferys said...

This is wonderful!

I've used Conway's Doomsday calculation in my course (before I retired):

http://bayesrules.net/BillInfo/doomsday.html

But your method is so simple and easy. If I were still teaching, I'd use it. I'm having trouble updating my webpages at the moment, but as soon as I solve that problem I'll point my page to yours.

Have you mentioned this to Prof. Conway? I am sure he'd be delighted.

It would be interesting for you to develop a tutorial calculator such as the one given here

http://www.timeanddate.com/date/doomsday-calculator.html

to help people learn your very simple algorithm.

Regards, Bill Jefferys

Bill Jefferys said...
This comment has been removed by the author.
Bill Jefferys said...
This comment has been removed by the author.
Bill Jefferys said...
This comment has been removed by the author.
Bill Jefferys said...

Bob Goddard pointed out a way to avoid the extra rule.

I agree, this is elegant, but I think it does not quite work for three years in the 2000's, namely, 2089, 2078 and 2067. For each of these non-leap years, adding 11 repeatedly doesn't yield a leap year until 2144. This is because 2100 is NOT a leap year. So the comment "At most this will require adding 33 to the year" is not correct.

It doesn't even work for 2100, again not a leap year because of the Gregorian rule, so if you apply this rule literally to 2100 you have to add 44 years (not 33) to get 2044, which gives the wrong Doomsday if you use Tuesday as the Doomsday in the 22nd century.

So instead of talking about "leap years" in any particular century, we should be asking whether y is divisible by 4. So if y is divisible by 4, just divide it by 2 and subtract that from the next higher multiple of 7.

I think that the correct rule when y is not divisible by 4 is, "If y is not divisible by 4, just repeatedly add 11 to y until you get a number divisible by 4, and apply the same formula to that number. At most this will require adding 33 to y."

Since the four-century rule of the Gregorian calendar applies to 2100, the Gregorian interpretation of 2100 as "not a leap year" should not have anything to do with the calculation because we are using the 2000 Doomsday of Wednesday once you divide the number gotten by 2. We are only talking about year numbers here, as Bob's prescient remark notes, not the exact number of days in any particular year (like 2100).

Cornflower (Dale) said...

This is much easier than Conway. I wondered if I couple simplify further though, and add my take. Instead of adding 11s, do the following

1. Reduce the year to the nearest lower year-evenly-divisible-by-4 (2100 is such a year). Call the lower year x and the difference z. e.g. yyyy = 2013. x = 12, z = 1
Note x + z = yy

2. Get the 7's complement of x/2
e.g. 2013, x = 12 x/2 = 6 7's complement of 6 is 1

3. Add the century# + difference (z) + 7's complement to get your Doomsday #
2013 = 2 + 1 + 1 = 4 (Thursday)

It works for the pesky dates mentioned by Bill Jeffreys:
2089 2 + 1 + 88=>44=>5 = 8 (Mon)
2078 2 + 2 + 76=>38=>4 = 8 (Mon)
2067 2 + 3 + 64=>32=>3 = 8 (Mon)

Cornflower (Dale) said...

An addendum to my December, 2013 comment. I forgot to state that for January and February of leap years you must subtract 1 from the final date.

Alternately, if you consider that the ancient Roman calendar started in March, you can do the same. If I use my method (or almost any of the algorithms), but for the year before for Jan and Feb dates, then it works out correctly.

Note that instead of Conway's Jan 3/4 and Feb 7/8 Doomsdays, if you consider the year before for January and February, you have the easier Doomsdays of Jan 2 (like May and Dec)and Feb 6 (like Jun). This works whether it is or is not a leap year.

jackerz said...

Note to Bill Jefferys and Dale Cornflower:

You should read Mike Walter's follow-up improvement to his easier doomsday proposal. It's called the "Odd+11" method and is described here:

http://arxiv.org/abs/1010.0765

The "Odd+11" method does not require any calculation involving leap years or divisibility-by-4 tests.

Bill Jefferys said...

It's been a while since I stopped by this page. Thanks to jackerz for pointing out the article by Mike Walters. His method is truly elegant and simple, and works for those problematic years that I mentioned