DOW algorithm
Timothy H. White
(i.e. Tuesday) for any date input. I've seen them around before, but
can't seem to find one now when I need it. Any ideas are appreciated,
please send them via email as I don't visit this newsgroup regularly.
TIA,
Timothy
=========== PGP 2.3a Public Key Available - finger me! ===========
"They that can give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
- Benjamin Franklin
____
\ / (Freedom cannot be given, it must be taken.)
\/
==================================================================
Jamshid Afshar
>I'm looking for a C or C++ algorithm to calculate the day of the week
>(i.e. Tuesday) for any date input. I've seen them around before, but
>can't seem to find one now when I need it. Any ideas are appreciated,
>please send them via email as I don't visit this newsgroup regularly.
Please remember to read a newsgroup's Frequently Asked Questions list
before posting to that newsgroup. I'm posting a followup instead of
emailing this reply in the hopes that others won't repeat the
comp.lang.c FAQ answer, or worse, give an incorrect answer, which
often happens with this question. Btw, I recommend just using
<time.h> functions.
If you're programming in C++ consider searching Nikke Locke's Class
Libraries FAQ for a date class. FAQs are posted monthly and available
anytime at rtfm.mit.edu in pub/usenet/comp.whatever/*.
-----from Steve Summit's (C) comp.lang.c FAQ-------
17.28: How can I find the day of the week given the date?
A: Use mktime (see questions 12.6 and 12.7), or Zeller's
congruence. Here is one quick implementation posted by Tomohiko
Sakamoto:
dayofweek(y, m, d) /* 0 = Sunday */
int y, m, d; /* 1 <= m <= 12, y > 1752 or so */
{
static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
y -= m < 3;
return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}
----------------
Mark Brader
> 17.28: How can I find the day of the week given the date?
>
> A: Use mktime (see questions 12.6 and 12.7), or Zeller's
> congruence. Here is one quick implementation posted by Tomohiko
Just for the record, the comp.lang.c FAQ list is wrong in calling
Sakamoto's code an implementation of Zeller's congruence. If you're
now curious and want to see the actual Zeller's congruence, look for
the same question in the FAQ list for sci.math; it's the second method
given there.
--
Mark Brader "Relax -- I know the procedures backwards."
m...@sq.com "Yeah, well, that's a quick way to get killed."
SoftQuad Inc., Toronto -- Chris Boucher, STAR COPS
This article is in the public domain.
Tomohiko Sakamoto
m...@sq.sq.com (Mark Brader) writes:
> If you're
> now curious and want to see the actual Zeller's congruence, look for
> the same question in the FAQ list for sci.math; it's the second method
> given there.
The FAQ list for sci.math says:
> The following formula, which is for the Gregorian calendar only, may be
> more convenient for computer programming. Note that in some programming
> languages the remainder operation can yield a negative result if given
> a negative operand, so "mod 7" may not translate to a simple remainder.
>
> W == (k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4]) mod 7
> where [] denotes the integer floor function (round down),
> k is day (1 to 31)
> m is month (1 = March, ..., 10 = December, 11 = Jan, 12 = Feb)
> Treat Jan & Feb as months of the preceding year
> C is century (1987 has C = 19)
> Y is year (1987 has Y = 87 except Y = 86 for Jan & Feb)
> W is week day (0 = Sunday, ..., 6 = Saturday)
>
> Here the century & 400 year corrections are built into the formula.
> The [2.6m-0.2] term relates to the repetitive pattern that the 30-day
> months show when March is taken as the first month.
I want someone to explain how to get the value of W for the date Jan 1, 1900.
--
T. Sakamoto
Colin Plumb
Tomohiko Sakamoto <saka...@sm.sony.co.jp> wrote:
>The FAQ list for sci.math says:
>
>> The following formula, which is for the Gregorian calendar only, may be
>> more convenient for computer programming. Note that in some programming
>> languages the remainder operation can yield a negative result if given
>> a negative operand, so "mod 7" may not translate to a simple remainder.
>>
>> W == (k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4]) mod 7
>> where [] denotes the integer floor function (round down),
>> k is day (1 to 31)
>> m is month (1 = March, ..., 10 = December, 11 = Jan, 12 = Feb)
>> Treat Jan & Feb as months of the preceding year
>> C is century (1987 has C = 19)
>> Y is year (1987 has Y = 87 except Y = 86 for Jan & Feb)
>> W is week day (0 = Sunday, ..., 6 = Saturday)
>>
>> Here the century & 400 year corrections are built into the formula.
>> The [2.6m-0.2] term relates to the repetitive pattern that the 30-day
>> months show when March is taken as the first month.
>
>I want someone to explain how to get the value of W for the date Jan 1, 1900.
>
Well, that's the first day of the 11th month of the year 1899, so...
(1 + floor(28.6+0.2) - 36 + 99 + 24 + 4) mod 7
= (1 + 28 + 63 + 28) mod 7
= (1 + 7*4 + 7*9 + 7*4) mod 7
= 1
So it's a monday. Checking with "cal 1 1900":
January 1900
S M Tu W Th F S
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31
It seems to be the agreed-upon correct day.
Tomohiko Sakamoto
saka...@sm.sony.co.jp (Tomohiko Sakamoto) wrote:
> The FAQ list for sci.math says:
>
>> The following formula, which is for the Gregorian calendar only, may be
>> more convenient for computer programming. Note that in some programming
>> languages the remainder operation can yield a negative result if given
>> a negative operand, so "mod 7" may not translate to a simple remainder.
>>
>> W == (k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4]) mod 7
>> where [] denotes the integer floor function (round down),
>> k is day (1 to 31)
>> m is month (1 = March, ..., 10 = December, 11 = Jan, 12 = Feb)
>> Treat Jan & Feb as months of the preceding year
>> C is century (1987 has C = 19)
>> Y is year (1987 has Y = 87 except Y = 86 for Jan & Feb)
>> W is week day (0 = Sunday, ..., 6 = Saturday)
>>
>> Here the century & 400 year corrections are built into the formula.
>> The [2.6m-0.2] term relates to the repetitive pattern that the 30-day
>> months show when March is taken as the first month.
>
> I want someone to explain how to get the value of W for the date Jan 1, 1900.
I have got many replies by e-mail, and I appreciate their kindness.
They all say: k = 1, m = 11, C = 18, Y = 99
Now I can program the day-of-week routine.
int dayofweek(int y, int m, int d)
{
int k, C, Y;
if (m < 3) { m += 10; --y; } else { m -= 2; }
k = d; C = y / 100; Y = y % 100;
return (k + (int)(2.6*m - 0.2) - 2*C + Y + Y/4 + C/4) % 7;
}
But it does not work for the date March 1, 1900:
for k = 1, m = 1, C = 19, and Y = 0,
(k + (int)(2.6*m - 0.2) - 2*C + Y + Y/4 + C/4) % 7
= (1 + 2 - 38 + 0 + 0 + 4) % 7
= (-31) % 7
= -3
(the % operatoin for a negative operand is system-dependent)
To avoid it, I rewrite the last return statement:
return (k + (int)(2.6*m - 0.2) + 5*C + Y + Y/4 + C/4) % 7;
^^^^^
(7*C) % 7 == 0 ---> (-2*C) % 7 == (-2*C + 7*C) % 7 == (5*C) % 7
I don't like floating-point operations:
return (k + (13*m - 1)/5 + 5*C + Y + Y/4 + C/4) % 7;
^^^^^^^^^^^^
Y = y % 100 and C = y / 100 ---> Y = y - 100*C
(5*C + Y + Y/4 + C/4) % 7
= (5*C + (y - 100*C) + (y/4 - 25*C) + C/4) % 7
= (y + y/4 + C/4 - 120*C) % 7
= (y + y/4 + C/4 - (7*17 + 1)*C) % 7
= (y + y/4 + C/4 - C) % 7
= (y + y/4 + y/400 - y/100) % 7
Now the last statement is:
return (k + (13*m - 1)/5 + y + y/4 + y/400 - y/100) % 7;
month: Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
m: 11 12 1 2 3 4 5 6 7 8 9 10
(13*m-1)/5: 28 30 2 5 7 10 12 15 18 20 23 25
modulo 7: 0 2 2 5 0 3 5 1 4 6 2 4
Using this table,
if (m < 3) { m += 10; } else { m -= 2; } and (13*m - 1)/5
---> static int t[] = { 0, 2, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
if (m < 3) --y;
return (d + t[m-1] + y + y/4 + y/400 - y/100) % 7;
I don't mind calling this code an implementation of Zeller's congruence.
But I programmed it independently. I programmed it from scratch with
the knowledge "leap = year%4 == 0 && year%100 != 0 || year%400 == 0."
--
T. Sakamoto
dayofweek(y,m,d){y-=m<3;return(y+y/4-y/100+y/400+"-bed=pen+mad."[m]+d)%7;}
Sean Dockery
| The FAQ list for sci.math says:
|
| > The following formula, which is for the Gregorian calendar only, may be
| > more convenient for computer programming. Note that in some programming
| > languages the remainder operation can yield a negative result if given
| > a negative operand, so "mod 7" may not translate to a simple remainder.
| >
| > W == (k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4]) mod 7
| > where [] denotes the integer floor function (round down),
| > k is day (1 to 31)
| > m is month (1 = March, ..., 10 = December, 11 = Jan, 12 = Feb)
| > Treat Jan & Feb as months of the preceding year
| > C is century (1987 has C = 19)
| > Y is year (1987 has Y = 87 except Y = 86 for Jan & Feb)
| > W is week day (0 = Sunday, ..., 6 = Saturday)
| >
| > Here the century & 400 year corrections are built into the formula.
| > The [2.6m-0.2] term relates to the repetitive pattern that the 30-day
| > months show when March is taken as the first month.
|
| I want someone to explain how to get the value of W for the date Jan 1, 1900.
How about the following function:
int DOW (char *month, int day, int year)
{
int century, leftover, monthval;
int i; /* everyone's favourite counter */
char *months[] = {
"Mar", "Apr", "May", "Jun", "Jul", "Aug",
"Sep", "Oct", "Nov", "Dec", "Jan", "Feb"
};
for (i = 0; strcmp (months[i], month) && i < 12; i++)
;
month_val = i + 1;
if (month_val > 12) {
fprintf (stderr, "DOW: invalid month string");
return 0;
}
else if (month_val > 10)
year--;
century = year / 100;
leftover = year % 100;
/* W == (k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4]) mod 7 */
return ((day + (int)(floor ((2.6 * month_val - 0.2))) - 2 * century + leftover + (leftover / 4) + (century / 4)) % 7);
} /* DOW */
I haven't tested this yet, but my calculator returns 1 (ie: Monday). Does
anyone have a calendar from 1900 to confirm this? :-)
--
Sean Dockery
doc...@griffin.cuc.ab.ca
Tomohiko Sakamoto
saka...@sm.sony.co.jp (Tomohiko Sakamoto) wrote:
> month: Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
> m: 11 12 1 2 3 4 5 6 7 8 9 10
> (13*m-1)/5: 28 30 2 5 7 10 12 15 18 20 23 25
^^31
> modulo 7: 0 2 2 5 0 3 5 1 4 6 2 4
^3
> ---> static int t[] = { 0, 2, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
^3
Sorry for my errors.
/************ trivial comments
(1) If a character array is used, space is saved.
static char t[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
(2) If a dummy element is used, t[m-1] becomes t[m]. Is it smart?
static char t[] = { '-', 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
(3) If a character string constant is used, the variable t disapears.
t[m] --> "-\0\3\2\5\0\3\5\1\4\6\2\4"[m]
(4) If the character code is ASCII, the following trick is available.
"-\0\3\2\5\0\3\5\1\4\6\2\4"[m] --> "-bed=pen+mad."[m]
But ......
(5) If the variable y is declared as unsigned, most compilers generate
better object code for y/4.
======================================================================
dayofweek(y, m, d)
unsigned int y, m, d;
{
y -= m < 3;
return (y + y/4 - y/100 + y/400 + "-bed=pen+mad."[m] + d) % 7;
}
======================================================================
*********/
--
T. Sakamoto
Eric Roode
Sean Dockery <doc...@griffin.cuc.ab.ca> wrote:
>saka...@sm.sony.co.jp wrote the following article:
>
>| The FAQ list for sci.math says:
>| > where [] denotes the integer floor function (round down),
>| > k is day (1 to 31)
>| > m is month (1 = March, ..., 10 = December, 11 = Jan, 12 = Feb)
>| > Treat Jan & Feb as months of the preceding year
>| > C is century (1987 has C = 19)
>| > Y is year (1987 has Y = 87 except Y = 86 for Jan & Feb)
>| > W is week day (0 = Sunday, ..., 6 = Saturday)
>| >
>| > Here the century & 400 year corrections are built into the formula.
>| > The [2.6m-0.2] term relates to the repetitive pattern that the 30-day
>| > months show when March is taken as the first month.
> /* W == (k + [2.6m - 0.2] - 2C + Y + [Y/4] + [C/4]) mod 7 */
>
> return ((day + (int)(floor ((2.6 * month_val - 0.2))) - 2 * century + leftover + (leftover / 4) + (century / 4)) % 7);
It should be noted that this formula has a serious flaw.
"[2.6m - 0.2]" is for mathematicians who have infinite precision. Don't
mess with floating-point on a computer -- not if you're doing integer
operations. There are cases where the above code, due to roundoff errors,
will yield incorrect results. Plus, it's not portable -- different
machines will have different roundoff errors.
Plus, your program now has to link in floating-point libraries.
Zeller's original formula had no such fp operations. It was integer-only.
See Dr Dobb's Journal, Oct 1990. The formula given in that article
substitutes
[(26 * m+1)/10]
for
[2.6m - 0.2]
I do not subscribe to sci.math; however, I would respectfully suggest
that the person in charge of its FAQ update it.
--
----
Eric
"If anyone finds this offensive, I am prepared not only to retract my
words, but also to deny under oath that I ever said them." -- Tom Lehrer
----
Mark Brader
> >
> > return ((day + (int)(floor ((2.6 * month_val - 0.2))) ...
> It should be noted that this formula has a serious flaw.
> "[2.6m - 0.2]" is for mathematicians who have infinite precision. Don't
> mess with floating-point on a computer -- not if you're doing integer
> operations. There are cases where the above code, due to roundoff errors,
The flaw is therefore not in the formula "[2.6m - 0.2]" (as noted,
"mathematicians have infinite precision"), but in the incorrect
implementation of it as (int)(floor ((2.6 * month_val - 0.2))).
The sci.math FAQ list entry is correct.
> Zeller's original formula had no such fp operations. It was integer-only.
> See Dr Dobb's Journal, Oct 1990.
I don't know where Zeller's formula was originally published (would that
article tell me, if I looked it up?), but it was a lot longer ago than 1990.
If I remember correctly, I first saw it in 1971, in the form of an
implementation in a FORTRAN-like language.
--
Mark Brader Summary of issue: Fix FORTRAN-8x.
m...@sq.com Committee Response: This proposal contains
SoftQuad Inc. insurmountable technical errors.
Toronto -- X3J11 responses to 2nd public review
pwpa...@news.delphi.com
>> month: Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
>> ---> static int t[] = { 0, 2, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
> ^3
Let's reexamine this for a moment...it's a simple parlor trick to to the
following in your head:
Last two digits of the year
+ (int) Last two digits of the year / 4
+ Day of the Month
+ Month Offset Code
Sum these four numbers and divide by 7. The result is the day of the
week in the form of Sun=1, Mon=2, ..., Sat = 0
Add 2 for the 1800s and 6 for the 2000s.
The month offset code is: (Jan...Dec):
1, 4, 4, 0, 2, 5, 0, 3, 6, 1, 4, 6
(use 0, 3 for Jan, Feb in leap years)
if you compare it /c the previous list of offsets (and allow for modulo
arithmetic):
0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4
then this list still does not look right.
here's a piece of REXX code which works (I don't have C loaded on this
machine and can't find the version I converted to C)
ld = year // 100
m1 = ( month + 9 ) // 12 + 1
m2 = m1 // 11
m2 = trunc( 0.8 * ( 2 * m2 + 1 ) + m2
m2 = m2 - ( leapyear * (m1 % 11) )
w = ld + ld%4 + day + m2 ) // 7
w will return 0=Sun, 1=Mon, ..., 6=Sat (--1 from the previous example)
leapyear = 1 for a leapyear, 0 for non-leapyear.