Zeller's Algorithm

Zeller's Algorithm

[Paul A Storm]

Help!

I am trying to find a Ada implementation of Zeller's algorithm that
works!  I have found several on the web
but none of them have worked right.

For example I tried this one from
http://www.adapower.com/alg/zeller.html  Inputting June 19 2002 returns
Wednesday, correct.  Inputting June 19 1999 produces Sunday, incorrect. 
That's a Saturday. Inputting
February 3, 2002 produces Friday, incorrect.  That's a Sunday.  What
gives?

I have had similar weird results using other similar Ada Zeller versions
I've found on the web.

I'm wondering if maybe there's a difference in rounding down.  Perhaps a
83 vs. 95 peculiarity?
I don't think so.  It produces compilation errors using the -gnat83
switch.

I'm running gnat 3.13a on Sun 2.6

Argh!  Anybody got any ideas on how to fix this or know of an Ada
implementation of Zeller's algorithm
that works?

Paul Storm

Re: Zeller's Algorithm

[Thomas Wolf]

paul.a.storm@lmco.com wrote:
> Help!
> 
> I am trying to find a Ada implementation of Zeller's algorithm that
> works!  I have found several on the web
> but none of them have worked right.
> 
> For example I tried this one from
> http://www.adapower.com/alg/zeller.html  Inputting June 19 2002 returns
> Wednesday, correct.  Inputting June 19 1999 produces Sunday, incorrect. 
> That's a Saturday. Inputting
> February 3, 2002 produces Friday, incorrect.  That's a Sunday.  What
> gives?
> 
> I have had similar weird results using other similar Ada Zeller versions
> I've found on the web.

You might try the Util.Calendar packages from my Util subsystem,
available at the URL

http://home.tiscalinet.ch/t_wolf/tw/ada95/util/

Util.Calendars.Universal.Day_Of_Week produces the correct results.
See the test driver in ./test/calendar_test.adb for some examples.

The Util subsystem is published under the GMGPL.

-- 
-----------------------------------------------------------------
Thomas Wolf                          e-mail: t_wolf@angelfire.com

Re: Zeller's Algorithm

[Paul A Storm]

Thomas Wolf wrote:

I downloaded your code and ran the test routine, np.  I'll check out the
contents.  I had already
decided to use a Julian conversion with a mod 7 as a basis for "Plan
B".  Thanks for your
reply.

I am still confused as to why the Zeller algorithm wouldn't work.  Since
the algorithm has been
around since 1875 I figure it has proven out.  Although I am still
cogitating on whether it
takes into account for centennial non-leap years(1800,1900, etc.) and
quatra-centennial leap years(i.e. 2000).
It bugs me when I can't figure out the reason for some code not
working.  Know what I mean?

Did you try to compile the program from the link I gave and did you have
any problems like I had?

> 
> paul.a.storm@lmco.com wrote:
> > Help!
> >
> > I am trying to find a Ada implementation of Zeller's algorithm that
> > works!  I have found several on the web
> > but none of them have worked right.
> >
> > For example I tried this one from
> > http://www.adapower.com/alg/zeller.html  Inputting June 19 2002 returns
> > Wednesday, correct.  Inputting June 19 1999 produces Sunday, incorrect.
> > That's a Saturday. Inputting
> > February 3, 2002 produces Friday, incorrect.  That's a Sunday.  What
> > gives?
> >
> > I have had similar weird results using other similar Ada Zeller versions
> > I've found on the web.
> 
> You might try the Util.Calendar packages from my Util subsystem,
> available at the URL
> 
> http://home.tiscalinet.ch/t_wolf/tw/ada95/util/
> 
> Util.Calendars.Universal.Day_Of_Week produces the correct results.
> See the test driver in ./test/calendar_test.adb for some examples.
> 
> The Util subsystem is published under the GMGPL.
> 
> --
> -----------------------------------------------------------------
> Thomas Wolf                          e-mail: t_wolf@angelfire.com

-- 
My perspicacity is only eclipsed by my pertinacity

Re: Zeller's Algorithm

[Thomas Wolf]

paul.a.storm@lmco.com wrote:
> 
> I am still confused as to why the Zeller algorithm wouldn't work.  Since
> the algorithm has been
> around since 1875 I figure it has proven out.  Although I am still
> cogitating on whether it
> takes into account for centennial non-leap years(1800,1900, etc.) and
> quatra-centennial leap years(i.e. 2000).

Yes it does.

> It bugs me when I can't figure out the reason for some code not
> working.  Know what I mean?

Zeller's *algorithm* does work for dates in the Gregorian calendar.
It's just the poor, buggy *implementation* posted at AdaPower that
doesn't work.

> Did you try to compile the program from the link I gave and did you have
> any problems like I had?

No, I didn't try to run that program. It is flawed in two ways:

1. The "if Month < 3" stuff should be moved out of GetValidDate into
   UseZeller.
2. UseZeller shouldn't add 1 at the end.

For a working implementation of Zeller's algorithm, try this:

   type Weekday is (Mon, Tue, Wed, Thu, Fri, Sat, Sun);
   --  ISO starts the week on a monday, so let's do the same here...

   function Day_Of_Week
     (Date : in Ada.Calendar.Time)
     return Weekday
   is
     --  Returns the day of the week. Works for dates of the 
     --  Gregorian calendar.

      Day   : Ada.Calendar.Day_Number;
      Month : Ada.Calendar.Month_Number;
      Year  : Ada.Calendar.Year_Number;
      Secs  : Ada.Calendar.Day_Duration;

      M, Y, Century, Z : Integer;

   begin
      --  This is Zeller's formula.
      Ada.Calendar.Split (Date, Year, Month, Day, Secs);
      if Month < 3 then
         M := Integer (Month) + 10;
         Y := Integer (Year) - 1;
      else
         M := Integer (Month) - 2;
         Y := Integer (Year);
      end if;
      Century := Y / 100; Y := Y mod 100;
      Z :=
        (Integer (Day) + (13 * M - 1) / 5 + Y + Y / 4 +
         Century / 4 - 2 * Century) mod 7;
      --  The left operand of the "mod" may be negative, but "mod 7"
      --  does the right thing and gives us a positive remainder in
      --  the range 0 .. 6.
      --  
      --  Now 0 is Sunday, 1 is Monday, and so on. Map this such that
      --  0 is Mon, 1 is Tue, and 6 is Sun.
      return Weekday'Val ((Z + 6) mod 7);
   end Day_Of_Week;

I'll make available this function in a future release of
my Util subsystem.

-- 
-----------------------------------------------------------------
Thomas Wolf                          e-mail: t_wolf@angelfire.com

Re: Zeller's Algorithm

[Robert Dewar]

Thomas Wolf <t_wolf@angelfire.com> wrote in message news:<MPG.17af1b07795920d8989693@news.ip-plus.net>...


> Zeller's *algorithm* does work for dates in the Gregorian calendar.

What is the reference for this algorithm. I learned it as a child (it is
something you can learn to compute in your head quite easily).

Re: Zeller's Algorithm

[Thomas Wolf]

dewar@gnat.com wrote:

> > Zeller's *algorithm* does work for dates in the Gregorian calendar.
> 
> What is the reference for this algorithm. I learned it as a child (it is
> something you can learn to compute in your head quite easily).
> 

Chr. Zeller, "Kalender-Formeln", Acta Mathematica, Vol. 9, pp. 131--136. 
(Nov. 1886). In German.

See also the URL <http://www.merlyn.demon.co.uk/zeller-c.htm>, an 
excellent page on Zeller's congruence.

-- 
-----------------------------------------------------------------
Thomas Wolf                          e-mail: t_wolf@angelfire.com

Re: Zeller's Algorithm

[Rick Maffei]

Paul A Storm wrote:
> 
> Help!
> 
> I am trying to find a Ada implementation of Zeller's algorithm that
> works!  I have found several on the web
> but none of them have worked right.
> 
> For example I tried this one from
> http://www.adapower.com/alg/zeller.html  Inputting June 19 2002 returns
> Wednesday, correct.  Inputting June 19 1999 produces Sunday, incorrect.
> That's a Saturday. Inputting
> February 3, 2002 produces Friday, incorrect.  That's a Sunday.  What
> gives?
> 
> I have had similar weird results using other similar Ada Zeller versions
> I've found on the web.
> 
> I'm wondering if maybe there's a difference in rounding down.  Perhaps a
> 83 vs. 95 peculiarity?
> I don't think so.  It produces compilation errors using the -gnat83
> switch.
> 
> I'm running gnat 3.13a on Sun 2.6
> 
> Argh!  Anybody got any ideas on how to fix this or know of an Ada
> implementation of Zeller's algorithm
> that works?
> 
> Paul Storm

While reviewing the latest Risks Digest, I came across the following
item titled "Possible day-of-week error" concerning the Zeller
algorithm:

http://catless.ncl.ac.uk/Risks/22.18.html#subj10.1

Just thought it may be of interest in this thread.

Rick Maffei

Re: Zeller's Algorithm

[Paul A Storm]

Rick Maffei wrote:

> 
> While reviewing the latest Risks Digest, I came across the following
> item titled "Possible day-of-week error" concerning the Zeller
> algorithm:
> 
> http://catless.ncl.ac.uk/Risks/22.18.html#subj10.1
> 
> Just thought it may be of interest in this thread.
> 
> Rick Maffei

Thanks.

Re: Zeller's Algorithm

[Thomas Wolf]

Paul A Storm <paul.a.storm@lmco.com> wrote in message news:<3D470EEE.811F758D@lmco.com>...
> Rick Maffei wrote:
> 
> > 
> > While reviewing the latest Risks Digest, I came across the following
> > item titled "Possible day-of-week error" concerning the Zeller
> > algorithm:
> > 
> > http://catless.ncl.ac.uk/Risks/22.18.html#subj10.1
> > 
> > Just thought it may be of interest in this thread.
> > 
> > Rick Maffei
> 
> Thanks.

That message in the Risks Digest relates to the possibility of
the left operand of the final "mod" operation in Zeller's formula
becoming negative in some cases. This may be a problem in languages
such as C, where e.g. -30 % 7 = -2. In Ada 95, using "mod", this is
not a problem, for A mod B is defined to return a modulus in the
range 0 .. B-1 for positive B, regardless of the sign of A.

If you want to avoid a negative left operand altogether, use the
formula

  Z := (Integer (Day) + (13 * M - 1) / 5 + Y + Y / 4 +
        Century / 4 + 5 * Century) mod 7;

instead of Zeller's

  Z := (Integer (Day) + (13 * M - 1) / 5 + Y + Y / 4 +
        Century / 4 - 2 * Century) mod 7;
 
Adding 7 * Century doesn't change the final result (because it's
a multiple of 7), but ensures that the left operand is always
positive.

--
-------------------------------------------------------------------
Thomas Wolf                            e-mail: t_wolf@angelfire.com

Re: Zeller's Algorithm

[Frank J. Lhota]

> This may be a problem in languages
> such as C, where e.g. -30 % 7 = -2.

Actually, the C standard does not require that (-30) % 7 == (-2). The
standard has somewhat loose requirements here that would allow the C "%"
operator to behave either like the Ada "rem" operator, or like the Ada "mod"
operator. The drive to standardize C, unfortunately, came after there were
many divergent implementations of the language. The need to validate
existing implementations tied the hands of the standards committee.

Re: Zeller's Algorithm

[Robert A Duff]

"Frank J. Lhota" <NOSPAM.lhota.adarose@verizon.net> writes:

> > This may be a problem in languages
> > such as C, where e.g. -30 % 7 = -2.
> 
> Actually, the C standard does not require that (-30) % 7 == (-2). The
> standard has somewhat loose requirements here that would allow the C "%"
> operator to behave either like the Ada "rem" operator, or like the Ada "mod"
> operator. The drive to standardize C, unfortunately, came after there were
> many divergent implementations of the language. The need to validate
> existing implementations tied the hands of the standards committee.

Doesn't this make the % operator totally useless for negative numbers?
I mean, how do you write code that gets some useful "right" answer,
if you're doing % on negative numbers?

- Bob

Re: Zeller's Algorithm

[Darren New]

Robert A Duff wrote:
> Doesn't this make the % operator totally useless for negative numbers?

Yes.

> I mean, how do you write code that gets some useful "right" answer,
> if you're doing % on negative numbers?

You fix it manually, just like most other C gaffes. :-)

x = a % 23;
if (x < 0) x += 23;


-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
** http://home.san.rr.com/dnew/DNResume.html **
** http://images.fbrtech.com/dnew/ **

Things to be thankful for, #37:
   No sausage was served at the Last Supper.

Re: Zeller's Algorithm

[Hyman Rosen]

Darren New wrote:
> Robert A Duff wrote:
>>Doesn't this make the % operator totally useless for negative numbers?
> Yes.

No. It is required in C or C++ that for non-zero b,
	a / b * b + a % b == a

When division rounds towards zero, as is usually desired
(the C++ standard claims that this is what the Fortran
standard requires), this forces the remainder operation
to return negative results. Eg., we want -3 / 2 == -1,
so we must have -3 % 2 == -1 for the requirement to hold.

Re: Zeller's Algorithm

[Frank J. Lhota]

"Hyman Rosen" <hyrosen@mail.com> wrote in message
news:1028145549.13341@master.nyc.kbcfp.com...
> No. It is required in C or C++ that for non-zero b,
> a / b * b + a % b == a
>
> When division rounds towards zero, as is usually desired
> (the C++ standard claims that this is what the Fortran
> standard requires), this forces the remainder operation
> to return negative results. Eg., we want -3 / 2 == -1,
> so we must have -3 % 2 == -1 for the requirement to hold.

You're absolute right, but with the caveat that the C standard does not
require that integer division round to zero. It is acceptable for a C
implementation to round to minus infinity, in which case (-3) / 2 == -2 and
therefore (-3) % 2 == 1.

This decision on the part of the C Standards committee is most unfortunate,
since as Mr. Rosen correctly indicates, virtually all platforms round to
zero. Life could have been made simpler for C programmers if this was
required for all implementations, but apparently there was some platform,
with politically powerful allies, that did not round to zero.

Re: Zeller's Algorithm

[Robert A Duff]

Hyman Rosen <hyrosen@mail.com> writes:

> Darren New wrote:
> > Robert A Duff wrote:
> >>Doesn't this make the % operator totally useless for negative numbers?
> > Yes.
> 
> No. It is required in C or C++ that for non-zero b,
> 	a / b * b + a % b == a
> 
> When division rounds towards zero, as is usually desired
> (the C++ standard claims that this is what the Fortran
> standard requires), this forces the remainder operation
> to return negative results. Eg., we want -3 / 2 == -1,
> so we must have -3 % 2 == -1 for the requirement to hold.

Hmm.  You're just "blaming" the fact that "%" is ill-defined on the fact
that "/" is ill-defined.  Wouldn't it be easier to understand that the
code is portable (and correct), if rounding were deterministic?
Can you give an example of an algorithm that takes advantage of the
above equivalence, but doesn't care which way rounding goes?

It's OK to blame this language flaw on history (C was implemented before
being standardized, unlike Ada -- we could have a nice thread discussing
the advantages and disadvantages of each approach), but to claim it's
not a flaw seems wrong.

By the way, how often do folks use "mod" or "rem" on negative numbers?
In *my* code, the numbers are (almost?) always nonnegative (and the
compiler knows that, because of subtype ranges, and can optimize
accordingly).

If I need to know the difference between "mod" and "rem", I have to look
it up every time, because I can't remember it.

- Bob

Re: Zeller's Algorithm

[Hyman Rosen]

Robert A Duff wrote:
 > to claim it's not a flaw seems wrong.

I didn't claim it's not a flaw, I just claimed that it wasn't
totally useless. In any case, every machine I ever worked on
has used round towards zero, but as you go on to say, when I
use %, I tend to make sure that the arguments are not negative.

Re: Zeller's Algorithm

[Robert A Duff]

Hyman Rosen <hyrosen@mail.com> writes:

> Robert A Duff wrote:
>  > to claim it's not a flaw seems wrong.
> 
> I didn't claim it's not a flaw, I just claimed that it wasn't
> totally useless.

Fair enough.  How about, "nigh unto useless"?  ;-)

That is, we haven't seen any examples that take advantage of the
well-defined relationship between % and / without also knowing the
rounding behavior.

>... In any case, every machine I ever worked on
> has used round towards zero, but as you go on to say, when I
> use %, I tend to make sure that the arguments are not negative.

And I guess it implies that (in practise, for me), Ada's "mod" and
"rem", and C's "%" are all equivalent: don't use them on negative
numbers.  At least, that's true when *writing* code.  When *reading*
code, I must think to myself, "prove it's nonnnegative, or else go look
it up."

- Bob

Re: Zeller's Algorithm

[Hyman Rosen]

I found an interesting paper that seems to be more
than you ever wanted to know about computer integer
division.

<http://www.cs.uu.nl/~daan/papers/divmodnote-letter.pdf>

Re: Zeller's Algorithm

[Frank J. Lhota]

Thanks for the reference. I actually found the article very interesting,
clearly demonstrating that I've been doing way too much abstract
mathematics. Time to enter a twelve step program :)

Re: Zeller's Algorithm

[Dan Nagle]

Hello,

The Fortran 95 standard has two intrinsic functions,
mod() and modulo(), which have subtly different definitions.

I wonder which one the C++ committee thought they were modeling?

BTW, the Fortran 2000 standard doesn't change anything here,
so you can check this for free at http://www.j3-fortran.org
and clicking on Fortran 200x for a few megabytes of PDF
of the current draft standard.

-- 
Cheers!

Dan Nagle
Purple Sage Computing Solutions, Inc.

On Wed, 31 Jul 2002 16:01:27 -0400, Hyman Rosen <hyrosen@mail.com>
wrote:

>Darren New wrote:
>> Robert A Duff wrote:
>>>Doesn't this make the % operator totally useless for negative numbers?
>> Yes.
>
>No. It is required in C or C++ that for non-zero b,
>	a / b * b + a % b == a
>
>When division rounds towards zero, as is usually desired
>(the C++ standard claims that this is what the Fortran
>standard requires), this forces the remainder operation
>to return negative results. Eg., we want -3 / 2 == -1,
>so we must have -3 % 2 == -1 for the requirement to hold.

Re: Zeller's Algorithm

[Hyman Rosen]

Dan Nagle wrote:
> The Fortran 95 standard has two intrinsic functions,
> mod() and modulo(), which have subtly different definitions.
> 
> I wonder which one the C++ committee thought they were modeling?

They thought they were modelling Fortran integer *division*,
which they say rounds toward zero.

Re: Zeller's Algorithm

[Matthew Woodcraft]

In article <kzS19.1$dz5.0@nwrddc01.gnilink.net>,
Frank J. Lhota <NOSPAM.lhota.adarose@verizon.net> wrote:
>> This may be a problem in languages
>> such as C, where e.g. -30 % 7 = -2.
>
>Actually, the C standard does not require that (-30) % 7 == (-2).

I believe it does; that is to say, this was 'fixed' in C99. It seems
likely that the C++ people will pick this up next time round.

-M-

Re: Zeller's Algorithm

[Thomas Wolf]

NOSPAM.lhota.adarose@verizon.net wrote:
> > This may be a problem in languages
> > such as C, where e.g. -30 % 7 = -2.
> 
> Actually, the C standard does not require that (-30) % 7 == (-2). 

In the new 1999 ISO C standard (ISO/IEC 9899:1999), it *is* required.
In the superseded ISO/IEC 9899:1990 C standard, the result was 
implementation-defined, either -2 or 5.

-- 
-----------------------------------------------------------------
Thomas Wolf                          e-mail: t_wolf@angelfire.com