Path: utzoo!mnetor!uunet!mcvax!ukc!stl!andrew From: andrew@stl.stc.co.uk (Andrew Macpherson) Newsgroups: comp.sys.ibm.pc Subject: Re: perpetual calendar (also day of week) Message-ID: <641@acer.stl.stc.co.uk> Date: 20 Mar 88 13:23:15 GMT References: <8802101657.AA08427@decwrl.dec.com> Reply-To: andrew@stl.stc.co.uk (Andrew Macpherson) Organization: STL,Harlow,UK. Lines: 148 Summary: Explanation of how it works, + Modula-2 implementation 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)