Robert_A_Freed@cup.portal.com (02/08/88)
In article <1217@mtuxo.UUCP> khreb@mtuxo.UUCP (01274-K.ROSEN) writes to sci.math: >The day of the week of day k, of month m (where a year is >considered to start in March, so that March is month 1 of that year and >January is considered the 11th month of the previous year and >February the twelfth month of that year), of year >100C + Y, where C is the century and Y is the year of the >century, is given by the remainder of > > k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4] > >when divided by 7, where Sunday is represented by a remainder of 0, >Monday by 1, etc. > >For instance, for January 1, 1900 we have C=18, Y=99, m=11, and k=1 >(since January is considered the 11th month of 1899 for this >calculation). The formula becomes 1+28-36+99+4+24 which leaves a >remainder of 1 when divided by 7. Hence this day was a Monday. > >For a derivation of this formula see my book ELEMENTARY NUMBER THEORY >AND ITS APPLICATIONS, Addison-Wesley, either first edition 1984 or >the new second edition, 1988. The formula is messy because of the >problem of different numbers of days in months and leap years occurring >every 4 years, except for even century years not divisible by 400. > > Ken Rosen, AT&T > 201-957-3691 (A similar, but slightly less elegant, formula was recently discussed in comp.sys.ibm.pc as well.) I believe this is known as Zeller's congruence. It's also cited in the text book, Elementary_Number_Theory, by Uspensky and Heaslet. I first noticed this little gem in a 1965 book, Problems_for_Computer_Solution, by Fred Gruenberger and George Jaffray. (The subject computer was the IBM 1620. If that doesn't date me, I don't know what will! :-) Two small comments about the above formula: 1. [2.6m - 0.2] can be calculated as [(13m - 1)/5] to avoid the overhead (and possible inaccuracy) of floating-point arithmetic. (Although not stated in the formulation, the square brackets [...] imply integer truncation.) 2. This applies only to the current (Gregorian) calendar, which was established October 15, 1582, but was not adopted by Great Britain (and the American colonies) until 1752. The formula is particularly efficient for computer solution since it involves only short integer arithmetic and a single conditional test (for January-February). And, unlike many other day-of-the-week solutions I've seen, this one handles non-leap century years (such as 1900 and 2100) correctly. Bob Freed Internet: Robert_A_Freed@cup.portal.com Newton Centre, MA UUCP: sun!portal!cup.portal.com!Robert_A_Freed
fulton@navion.dec.com (10-Feb-1988 0958) (02/11/88)
Robert_A_Freed@cup.portal.com writes: >In article <1217@mtuxo.UUCP> khreb@mtuxo.UUCP (01274-K.ROSEN) writes >to sci.math: > >>The day of the week of day k, of month m (where a year is >>considered to start in March, so that March is month 1 of that year and >>January is considered the 11th month of the previous year and >>February the twelfth month of that year), of year >>100C + Y, where C is the century and Y is the year of the >>century, is given by the remainder of >> >> k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4] >> >>when divided by 7, where Sunday is represented by a remainder of 0, >>Monday by 1, etc. >> >>For instance, for January 1, 1900 we have C=18, Y=99, m=11, and k=1 >>(since January is considered the 11th month of 1899 for this >>calculation). The formula becomes 1+28-36+99+4+24 which leaves a >>remainder of 1 when divided by 7. Hence this day was a Monday. >> >>For a derivation of this formula see my book ELEMENTARY NUMBER THEORY >>AND ITS APPLICATIONS, Addison-Wesley, either first edition 1984 or >>the new second edition, 1988. The formula is messy because of the >>problem of different numbers of days in months and leap years occurring >>every 4 years, except for even century years not divisible by 400. >> >> Ken Rosen, AT&T >> 201-957-3691 > >(A similar, but slightly less elegant, formula was recently discussed in >comp.sys.ibm.pc as well.) > >I believe this is known as Zeller's congruence. It's also cited in the >text book, Elementary_Number_Theory, by Uspensky and Heaslet. I first >noticed this little gem in a 1965 book, Problems_for_Computer_Solution, >by Fred Gruenberger and George Jaffray. (The subject computer was the >IBM 1620. If that doesn't date me, I don't know what will! :-) > >Two small comments about the above formula: > >1. [2.6m - 0.2] can be calculated as [(13m - 1)/5] to avoid the > overhead (and possible inaccuracy) of floating-point arithmetic. > (Although not stated in the formulation, the square brackets [...] > imply integer truncation.) > >2. This applies only to the current (Gregorian) calendar, which was > established October 15, 1582, but was not adopted by Great Britain > (and the American colonies) until 1752. > >The formula is particularly efficient for computer solution since it >involves only short integer arithmetic and a single conditional test >(for January-February). And, unlike many other day-of-the-week >solutions I've seen, this one handles non-leap century years (such as >1900 and 2100) correctly. > >Bob Freed Internet: Robert_A_Freed@cup.portal.com >Newton Centre, MA UUCP: sun!portal!cup.portal.com!Robert_A_Freed I have been intrigued by the above formula, and I coded it up in Logitech Modula-2 to try it out. It appears that there are some cases where it doesn't work quite right. For instance: October 1, 1910 has: k = 1 m = 8 C = 19 Y = 10 Thus you achieve: k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4] = 1 + [2.6 * 8 - 0.2] - 2 * 19 + 10 + [10 / 4] + [19 / 4] = 1 + [20.8 - 0.2] - 38 + 10 + [2.5] + [4.75] = 1 + [20.6] - 38 + 10 + 2 + 4 = 1 + 20 - 38 + 10 + 2 + 4 = -1 Then you have -1 MOD 7 => -1, which does not equate to any of the numbers assigned to Sunday thru Saturday, namely 0 thru 6. There are many cases in which the above formula generates a negative number, and it is not always -1. (I used a program I wrote that generates correct dates (it accounts correctly for leap year, as does the above formula) and ran the output of that program into the input of my program for the above formula; that's how I discovered this problem.) For all cases in which the above formula generates a negative number, applying the following fix before doing the MOD 7 works: WHILE DayOfWeek < 0 DO DayOfWeek := DayOfWeek + 7; END (* while *); (Note: I actually code DayOfWeek := DayOfWeek + 7; as INC( DayOfWeek, 7 ); I showed it the way I did for those of you not familiar with Modula-2.) I guess that this is an after-the-fact kludge; perhaps the original formula could be changed so that the result doesn't require "fixing" if it comes out negative. - Cathy Fulton uucp: ...decwrl!comet.dec.com!fulton ARPA: fulton@comet.dec.com
andrew@stl.stc.co.uk (Andrew Macpherson) (03/20/88)
fulton@navion.dec.com (10-Feb-1988 0958) writes: | | I have been intrigued by the above formula, and I coded it up in [Original discussion of Zeller's Congruence moved to the end of this [article | Logitech Modula-2 to try it out. It appears that there are some | cases where it doesn't work quite right. For instance: | [ Discussion of modula2's principle of maximum surprise deleted | | There are many cases in which the above formula generates a | negative number, and it is not always -1. (I used a program I | wrote that generates correct dates (it accounts correctly for | leap year, as does the above formula) and ran the output of that | program into the input of my program for the above formula; | that's how I discovered this problem.) [more deletion | I guess that this is an after-the-fact kludge; perhaps the | original formula could be changed so that the result doesn't | require "fixing" if it comes out negative. | | - Cathy Fulton | | uucp: ...decwrl!comet.dec.com!fulton | ARPA: fulton@comet.dec.com This procedure implements the formula correctly: PROCEDURE Zeller(d: DATE): WEEKDAY; (* zeller : date -> Weekday Pre: InvDate(d) % date after 14-Sep-1752 in UK Post: true zeller(d) == let m1 == month(d) - 2, y1 == year(d) in let m == if m1 < 1 then m1 + 12 else m1, y2 == if m1 < 1 then y1 - 1 else y1 in let c == y2 truncate 100, y == y2 mod 100 in weekdays[(((((26 m) - 2) truncate 10) + (day(d) + ((c truncate 4) + ((5 c) + ((y truncate 4) + y))))) mod 7) + 1]; What's going on? The first catch in this function is February --- it's an 'odd man out' as far as the months go, so let's redefine the start of year as the 1st March, then we need only worry about leap-years in the 'year' part of the formula. Next: We want a function which gives a mapping: 1->2, 2->5, 3->7 etc ie the number of days ''extra'' over a 28 day month. This is the '((26 m) -2) truncate 10' term to this we have to add the offset into the month so that when we look at it mod 7 we have a mapping to weekday. Oh by the way this term also gives a constant offset of 2. This chap Zeller was very clever at hiding it! Unfortunately it isn't that simple: there is an extra day in each year (mod 7) so add y (the year in the centuary). Right so far, but leap years? Well *within* a centuary these are regular -- every 4 years, hence y truncate 4. Ok so why emphasise within? well centuaries are only leap-years if they are divisible by 400. We've already divided by 100 to get c so our term becomes c truncate 4. Now about other centuaries: 100 mod 7 = 2, that is to say the -2c in the original formula. Catch is some programming languages do strange things on Modulus a negative number (Modula2 in particular) so let's use a positive term instead: +5c gives the correct result. *) VAR k, m, C, Y, temp: INTEGER; BEGIN k := d.day; m := INTEGER(ORD(d.month)) -1; (* Really -2, but enums start with 0 *) (* Which either proves that Modula-2 is innappropriate in this context, or * that an enumeration is. Unfortunately an enumeration is a requirement, * for this exercise, and unlike C++ I can't chose the values of types in * an enumeration in Modula-2. There is of course also the limitation of * this implementation which prevents DATE being a real obscured DATA Type * (only pointers)... Modula2 Gah! *) temp := d.year; IF m < 1 THEN m := m + 12; temp := temp - 1; END; C := temp DIV 100; Y := temp MOD 100; RETURN VAL(WEEKDAY,CARDINAL(((26*m - 2) DIV 10 + k + Y + Y DIV 4 + C DIV 4 + 5C) MOD 7)); END Zeller; [Original discussion follows (press j if familiar with this)] | Robert_A_Freed@cup.portal.com writes: | >khreb@mtuxo.UUCP (01274-K.ROSEN) writes to sci.math: | > | >>For a derivation of this formula see my book ELEMENTARY NUMBER THEORY | >>AND ITS APPLICATIONS, Addison-Wesley, either first edition 1984 or | >>the new second edition, 1988. The formula is messy because of the | >>problem of different numbers of days in months and leap years occurring | >>every 4 years, except for even century years not divisible by 400. | >> | >> Ken Rosen, AT&T | >> 201-957-3691 | > | >I believe this is known as Zeller's congruence. It's also cited in the | >text book, Elementary_Number_Theory, by Uspensky and Heaslet. I first | >noticed this little gem in a 1965 book, Problems_for_Computer_Solution, | >by Fred Gruenberger and George Jaffray. (The subject computer was the | >IBM 1620. If that doesn't date me, I don't know what will! :-) | > | >Two small comments about the above formula: | > | >1. [2.6m - 0.2] can be calculated as [(13m - 1)/5] to avoid the | > overhead (and possible inaccuracy) of floating-point arithmetic. | > (Although not stated in the formulation, the square brackets [...] | > imply integer truncation.) | > | >2. This applies only to the current (Gregorian) calendar, which was | > established October 15, 1582, but was not adopted by Great Britain | > (and the American colonies) until 1752. | > | >The formula is particularly efficient for computer solution since it | >involves only short integer arithmetic and a single conditional test | >(for January-February). And, unlike many other day-of-the-week | >solutions I've seen, this one handles non-leap century years (such as | >1900 and 2100) correctly. | > | >Bob Freed Internet: Robert_A_Freed@cup.portal.com | >Newton Centre, MA UUCP: sun!portal!cup.portal.com!Robert_A_Freed -- Andrew Macpherson andrew@stl.stc.co.uk - or - ...!mcvax!ukc!stl!andrew "It is always a great mistake to treat the individual on the chance that he may become a crowd" -- Mr Justice Codd: (A.P.Herbert)