🚀 go-pugleaf

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)