Dec 132017
Text file describing Zeller’s congruence (day-of-the-week algorithm) with C source. | |||
---|---|---|---|
File Name | File Size | Zip Size | Zip Type |
ZELLER.TXT | 16384 | 4921 | deflated |
Download File ZELLERC.ZIP Here
Contents of the ZELLER.TXT file
DAY-OF-THE-WEEK REVISITED
Recently (COMPUTER LANGUAGE, March 1988, pp. 9-10) readers
Solomon and Pancake each describe and suggest the use of Zeller's
congruence for calculating the day-of-the-week for any date
within the Gregorian calendar. The described algorithm is indeed
elegant. It can also be treacherous if implemented carelessly.
For example, the calculation INT(2.6 * Month# - 0.2) yields the
wrong result for a number of adjusted months when the constants
2.6 and 0.2 are used as assigned numbers as in Figure 1a. The
explanation of this result requires a deeper understanding of
both the algorithm and the computational process.
********************************************************************
main() adj month# value
{ 1 2
float f1, f2; 2 4 WRONG
int i, j; 3 7
4 10
f1 = 2.6; 5 12
f2 = 0.2; 6 15
printf("adj month# value"); 7 17 WRONG
for(i=1; i<13; i++) { 8 20
j = i * f1 - f2; 9 23
printf("\n %2d %2d",i, j); 10 25
} 11 28
} 12 30 WRONG
a) code that produces errors
main() adj month# value
{ 1 2
int i, j; 2 5
3 7
printf("adj month# value"); 4 10
for(i=1; i<13; i++) { 5 12
j = i * 2.6 - 0.2; 6 15
printf("\n %2d %2d",i, j); 7 18
} 8 20
} 9 23
10 25
11 28
12 31
b) code that produces the correct response
Figure 1. Two implementations of Zeller's algorithm using Turbo C
v. 1.0 on a PC's Limited AT clone.
********************************************************************
To understand the algorithm requires a brief review how the
current calendar came into existance. At some time around 45
B.C.,Julius Caesar introduced the "Julian calendar" based on a
year of 365.25 days. Because the actual year contains (very
nearly) 365.2422 days, the accumulated error by the sixteenth
century was having a noticeable effect on the calculation of
religious seasons. An adjustment was made in Catholic Europe
under Pope Gregory XIII in 1582. The adjustment modified the leap
year rule. Three out of the four "century" years, those years not
divisible by 400, are no longer leap years in the Gregorian
calendar.
********************************************************************
Zeller's algorithm contains two parts. Part 1 "adjusts" the year
to go from March (month 1) thru February (month 12) as follows:
if(UnadjMonth# < 2) THEN
AdjMonth# = UnadjMonth# + 12
AdjYear = UnadjYear - 1
ELSE
AdjMonth# = UnadjMonth# - 2
AdjYear = UnadjYear
END IF,
where UnadjYear and UnadjMonth# are the starting year and month, e.g.,
January (month 1) thru December(month 12), and AdjYear and AdjMonth#
are the adjusted year and month.
Part 2 of the algorithm evaluates the following congruence:
DayOfWeek = [INT(2.6 * Month# - 0.2) - 2 * YFir2dgts +
INT(YFir2dgts / 4) + YLas2dgts +
INT(YLas2dgts / 4) + Day#] MOD 7
where: Day# is the starting day number,
Month# is the previously adjusted month from Part 1,
YFir2dgts is the adjusted century,
YLas2dgts is the adjusted year within the century,
INT is the integer operator,
MOD is the modulo operator, and
DayOfWeek contains the values 0 thru 6 representing
the days Sunday thru Saturday.
FIGURE 2. Zeller's algorithm for computing day-of-the-week
***********************************************************************
This description makes it easy to identify how the date
information is used in Zeller's congruence, which is described in
Figure 2. For instance, each day in the original "date" causes a
one day change in the day-of-the-week and is associated with Day#
in the congruence.
Each one-out-of-four "century" leap years also causes a one day
change in the day-of-the-week and is obviously associated with
the term INT(YFir2dgts/4). Since this value represents all leap
years that are also century years, the "standard" leap year
calculation must not count any leap year that occurs on a century
year. This is done by first calculating all leap years and then
subtracting a correction factor. (This has the effect of
simultanously adding and subtracting one day-of-the-week, a net
change of zero) The correction factor is simply the century
number since each century is always a leap year, e.g., 100/4 is
an integer.
Each "standard" leap year also causes a one day change in the
day-of-the-week congruence. It is simply the integer part of the
adjusted year divided by four minus the century correction
factor. Expressing the adjusted year as the sum of its century
(YFir2dgts * 100) and the year within the century (YLas2dgts)
produces
(YFir2dgts * 100 + YLas2dgts) / 4 - YFir2dgts (1)
= YFir2dgts * 24 + YLas2dgts/4 (2)
= YFir2dgts * 3 + YLas2dgts/4. (3)
The last step is justified because everything is taken modulo 7
and 24 MOD 7 is congruent to 3. Thus YLas2dgts/4 associates
immediately with a like term in Zeller's congruence and we hope
the other term will combine appropriately with some term yet to
be determined.
Each integer year comprises 365 days. 365 is congruent to one
modulo 7. Thus each year also adds a one day change in the day-
of-the-week congruence. Again, expressing the adjusted year as
the sum of its century and year within the century yields
YFir2dgts * 100 + YLas2dgts (4)
= YFir2dgts * 2 + YLas2dgts (5)
Equation 5 is also justified because everything is taken modulo 7
and 100 MOD 7 is congruent to 2. Combining this result with the
unassociated term (first term after the equals sign in Equation
3) in the "standard" leap year gives
YFir2dgts * 3 + YFir2dgts * 2 + YLas2dgts (6)
= YFir2dgts * 5 + YLas2dgts (7)
= -2 * YFir2dgts + YLas2dgts, (8)
which corresponds to two of the three unassociated terms in the
Zeller congruence. The last term, INT(2.6 * Month# - 0.2), must
now be shown to associate with the adjusted month.
********************************************************************
month# month days/ col 3 col 4 col 5 col 8 2.6 *
month MOD 7 offset +2 - 0.2 month#
1 March 31 3 2 2.4 2.6
2 April 30 2 3 5 5.0 5.2
3 May 31 3 2 7 7.6 7.8
4 June 30 2 3 10 10.2 10.4
5 July 31 3 2 12 12.8 13.0
6 August 31 3 3 15 15.4 15.6
7 September 30 2 3 18 18.0 18.2
8 October 31 3 2 20 20.6 20.8
9 November 30 2 3 23 23.2 23.4
10 December 31 3 2 25 25.8 26.0
11 January 31 3 3 28 28.4 28.6
12 February 3 31 31.0 31.2
Table 1. Zeller's algorithm using the adjusted month
********************************************************************
Table 1 shows the adjusted month number, month and days per month
in columns 1-3. Column 4 is the remainder of the days per month
modulo 7, the number of days in a week. This must be dropped one
month as in column 5 since, to reach the start of April one
accumulates 3 days of the week from March. To reach the start of
May one accumulates from March and then April 3 and then 2 (total
of 5) days of the week. Column 6 contains this cumulative value
plus a bias of 2 to yield the more "natural" 0-6 being Sunday
thru Saturday. Column 6 represents the number of days offset
produced by all prior months and represents the integer value of
column 7. Column 8 and 7 contain the intermediate steps in
Zeller's congruence, e.g.,2.6 * Month# and then 2.6 * Month# - 0.2.
********************************************************************
/* INT(2.6 * Month# - 0.1) */
main()
{
float f1, f2;
int i, j;
f1 = 2.6;
f2 = 0.1;
printf("adj month# value");
for(i=1; i<13; i++) {
j = i * f1 - f2;
printf("\n %2d %2d",i, j);
}
}
a) Figure 1a code with 0.1 produces correct response
/* INT(2.6 * Month# - 0.1) */
main()
{
int i, j;
printf("adj month# value");
for(i=1; i<13; i++) {
j = i * 2.6 - 0.2;
printf("\n %2d %2d",i, j);
}
}
b) Figure 1b code with 0.1 still correct
/* INT(2.6 * Month#) */
main()
{
float f1;
int i, j;
f1 = 2.6;
printf("adj month# value");
for(i=1; i<13; i++) {
j = i * f1;
printf("\n %2d %2d",i, j);
}
}
c) 0.2 deleted also produces correct response
Figure 3. Zeller's algorithm with 0.2 replaced by 0.1 and Null
********************************************************************
Columns 6, 7, and 8 show that the maximum value that can be
subtracted form the 2.6 * Month# term is 0.2. Any larger number
causes an error for months April, September and February. In a
similar way the minimum number which can be subtracted is just
over zero since using zero causes an error for months July and
December. Because this algorithm uses the 0.2 value, it has
little margin for computational inaccuracy. A better choice which
provides equal margin between the two extremes is to use a value
of 0.1. The use of INT(2.6 * Month# - 0.1) worked correctly in
all my limited tests (see Figure 3).
Numbers such as 2.6 and 0.2 are called real or float numbers in
languages such as FORTRAN, PASCAL and C. Such numbers are
normally stored in a floating point format. One example is the
IEEE floating point number format as in some implementations of
the Language C. Real values here are called float and have 4
bytes, consisting of a sign bit, an 8-bit excess 127 binary
exponent, and a 23-bit mantissa. The mantissa represents the
number between 1.0 and 2.0. In these machines, after assignment,
0.2 will be stored exactly while 2.6 is stored as 2.5999999. When
multiplied by 12, for example, the value is 31.199998.
Subtracting 0.2 produces 30.999998 which truncates to 30, not the
required 31. This produced the type of error seen by running the
code in Figure 1a. Storage of the constants for the code of
Figure 1b is in double, using (typically on a pc) twice the
number of bits. Calculations are then made in double precision
arithmetic, and only then is the answer trimmed down to regular
float size. This double precision computation and how the
trimming is done allows the code of Figure 1b to yield the proper
result.
In general, whenever the difference of two noninteger numbers are
calculated (and especially when one or both are multiplied by
other factors so that any inaccurate representation is amplified
and then thresholded) the resultant answer should be suspect,
since it may not be exactly what is expected.
Since the value 2.599999 can be thought of as 2.6 minus a small
delta slightly larger than zero an interesting experiment was to
try using the other bound, subtracting zero instead of the 0.2
(see Figure 3c). Sure enough the resultant values are correct and
it even saves one operation and storage of one constant. But,
living on the edge, either edge, is definitely not recommended.
An exact, although less elagent algorithm, can be formulated by
noting each adjusted month contributes at least 30 plus 1 or 0
days. Table 2 shows this form using 2 for 30 modulo 7. The
desired values of column 6 are the sum of the previous values in
columns 7 and 8, e.g.,
Month#
2 * Month# + bits per Table 2, col 8 (9)
1
This method requires storage of a single 12 bit word and the
ability to shift a copy of the word by an amount equal to the
adjusted month number while counting the logical ones passing a
fixed position. Figure 4 shows one implementation using the
Language C that produces the correct result.
********************************************************************
month# month days/ col 3 col 4 col 5 col 7 col 8
month MOD 7 offset +2
1 March 31 3 2 2 0
2 April 30 2 3 5 2 1
3 May 31 3 2 7 2 0
4 June 30 2 3 10 2 1
5 July 31 3 2 12 2 0
6 August 31 3 3 15 2 1
7 September 30 2 3 18 2 1
8 October 31 3 2 20 2 0
9 November 30 2 3 23 2 1
10 December 31 3 2 25 2 0
11 January 31 3 3 28 2 1
12 February 3 31 2 1
Table 2. Alternative method also using the adjusted month
********************************************************************
********************************************************************
/* alternative integer algorithm */
typedef struct {
unsigned bit0 : 1;
unsigned bit1 : 1;
unsigned bit2 : 1;
unsigned bit3 : 1;
unsigned bit4 : 1;
unsigned bit5 : 1;
unsigned bit6 : 1;
unsigned bit7 : 1;
unsigned bit8 : 1;
unsigned bit9 : 1;
unsigned bit10 : 1;
unsigned bit11 : 1;
unsigned bit12 : 1;
unsigned bit13 : 1;
unsigned bit14 : 1;
unsigned bit15 : 1;
} flag_t;
union {
int iflag;
flag_t flag;
} u;
int i, j, m;
main()
{
printf("adj month# value");
for(i=1; i<13; i++) {
m = 2 * i;
u.iflag = 6868;
for(j=0; j u.iflag = u.iflag >> 1;
if(u.flag.bit0) m++;
}
printf("\n %2d %2d",i, m);
}
}
Figure 4. Alternative all integer algorithm
********************************************************************
}
Figure 4. Alternative all integer algorithm
*********************************************
Recently (COMPUTER LANGUAGE, March 1988, pp. 9-10) readers
Solomon and Pancake each describe and suggest the use of Zeller's
congruence for calculating the day-of-the-week for any date
within the Gregorian calendar. The described algorithm is indeed
elegant. It can also be treacherous if implemented carelessly.
For example, the calculation INT(2.6 * Month# - 0.2) yields the
wrong result for a number of adjusted months when the constants
2.6 and 0.2 are used as assigned numbers as in Figure 1a. The
explanation of this result requires a deeper understanding of
both the algorithm and the computational process.
********************************************************************
main() adj month# value
{ 1 2
float f1, f2; 2 4 WRONG
int i, j; 3 7
4 10
f1 = 2.6; 5 12
f2 = 0.2; 6 15
printf("adj month# value"); 7 17 WRONG
for(i=1; i<13; i++) { 8 20
j = i * f1 - f2; 9 23
printf("\n %2d %2d",i, j); 10 25
} 11 28
} 12 30 WRONG
a) code that produces errors
main() adj month# value
{ 1 2
int i, j; 2 5
3 7
printf("adj month# value"); 4 10
for(i=1; i<13; i++) { 5 12
j = i * 2.6 - 0.2; 6 15
printf("\n %2d %2d",i, j); 7 18
} 8 20
} 9 23
10 25
11 28
12 31
b) code that produces the correct response
Figure 1. Two implementations of Zeller's algorithm using Turbo C
v. 1.0 on a PC's Limited AT clone.
********************************************************************
To understand the algorithm requires a brief review how the
current calendar came into existance. At some time around 45
B.C.,Julius Caesar introduced the "Julian calendar" based on a
year of 365.25 days. Because the actual year contains (very
nearly) 365.2422 days, the accumulated error by the sixteenth
century was having a noticeable effect on the calculation of
religious seasons. An adjustment was made in Catholic Europe
under Pope Gregory XIII in 1582. The adjustment modified the leap
year rule. Three out of the four "century" years, those years not
divisible by 400, are no longer leap years in the Gregorian
calendar.
********************************************************************
Zeller's algorithm contains two parts. Part 1 "adjusts" the year
to go from March (month 1) thru February (month 12) as follows:
if(UnadjMonth# < 2) THEN
AdjMonth# = UnadjMonth# + 12
AdjYear = UnadjYear - 1
ELSE
AdjMonth# = UnadjMonth# - 2
AdjYear = UnadjYear
END IF,
where UnadjYear and UnadjMonth# are the starting year and month, e.g.,
January (month 1) thru December(month 12), and AdjYear and AdjMonth#
are the adjusted year and month.
Part 2 of the algorithm evaluates the following congruence:
DayOfWeek = [INT(2.6 * Month# - 0.2) - 2 * YFir2dgts +
INT(YFir2dgts / 4) + YLas2dgts +
INT(YLas2dgts / 4) + Day#] MOD 7
where: Day# is the starting day number,
Month# is the previously adjusted month from Part 1,
YFir2dgts is the adjusted century,
YLas2dgts is the adjusted year within the century,
INT is the integer operator,
MOD is the modulo operator, and
DayOfWeek contains the values 0 thru 6 representing
the days Sunday thru Saturday.
FIGURE 2. Zeller's algorithm for computing day-of-the-week
***********************************************************************
This description makes it easy to identify how the date
information is used in Zeller's congruence, which is described in
Figure 2. For instance, each day in the original "date" causes a
one day change in the day-of-the-week and is associated with Day#
in the congruence.
Each one-out-of-four "century" leap years also causes a one day
change in the day-of-the-week and is obviously associated with
the term INT(YFir2dgts/4). Since this value represents all leap
years that are also century years, the "standard" leap year
calculation must not count any leap year that occurs on a century
year. This is done by first calculating all leap years and then
subtracting a correction factor. (This has the effect of
simultanously adding and subtracting one day-of-the-week, a net
change of zero) The correction factor is simply the century
number since each century is always a leap year, e.g., 100/4 is
an integer.
Each "standard" leap year also causes a one day change in the
day-of-the-week congruence. It is simply the integer part of the
adjusted year divided by four minus the century correction
factor. Expressing the adjusted year as the sum of its century
(YFir2dgts * 100) and the year within the century (YLas2dgts)
produces
(YFir2dgts * 100 + YLas2dgts) / 4 - YFir2dgts (1)
= YFir2dgts * 24 + YLas2dgts/4 (2)
= YFir2dgts * 3 + YLas2dgts/4. (3)
The last step is justified because everything is taken modulo 7
and 24 MOD 7 is congruent to 3. Thus YLas2dgts/4 associates
immediately with a like term in Zeller's congruence and we hope
the other term will combine appropriately with some term yet to
be determined.
Each integer year comprises 365 days. 365 is congruent to one
modulo 7. Thus each year also adds a one day change in the day-
of-the-week congruence. Again, expressing the adjusted year as
the sum of its century and year within the century yields
YFir2dgts * 100 + YLas2dgts (4)
= YFir2dgts * 2 + YLas2dgts (5)
Equation 5 is also justified because everything is taken modulo 7
and 100 MOD 7 is congruent to 2. Combining this result with the
unassociated term (first term after the equals sign in Equation
3) in the "standard" leap year gives
YFir2dgts * 3 + YFir2dgts * 2 + YLas2dgts (6)
= YFir2dgts * 5 + YLas2dgts (7)
= -2 * YFir2dgts + YLas2dgts, (8)
which corresponds to two of the three unassociated terms in the
Zeller congruence. The last term, INT(2.6 * Month# - 0.2), must
now be shown to associate with the adjusted month.
********************************************************************
month# month days/ col 3 col 4 col 5 col 8 2.6 *
month MOD 7 offset +2 - 0.2 month#
1 March 31 3 2 2.4 2.6
2 April 30 2 3 5 5.0 5.2
3 May 31 3 2 7 7.6 7.8
4 June 30 2 3 10 10.2 10.4
5 July 31 3 2 12 12.8 13.0
6 August 31 3 3 15 15.4 15.6
7 September 30 2 3 18 18.0 18.2
8 October 31 3 2 20 20.6 20.8
9 November 30 2 3 23 23.2 23.4
10 December 31 3 2 25 25.8 26.0
11 January 31 3 3 28 28.4 28.6
12 February 3 31 31.0 31.2
Table 1. Zeller's algorithm using the adjusted month
********************************************************************
Table 1 shows the adjusted month number, month and days per month
in columns 1-3. Column 4 is the remainder of the days per month
modulo 7, the number of days in a week. This must be dropped one
month as in column 5 since, to reach the start of April one
accumulates 3 days of the week from March. To reach the start of
May one accumulates from March and then April 3 and then 2 (total
of 5) days of the week. Column 6 contains this cumulative value
plus a bias of 2 to yield the more "natural" 0-6 being Sunday
thru Saturday. Column 6 represents the number of days offset
produced by all prior months and represents the integer value of
column 7. Column 8 and 7 contain the intermediate steps in
Zeller's congruence, e.g.,2.6 * Month# and then 2.6 * Month# - 0.2.
********************************************************************
/* INT(2.6 * Month# - 0.1) */
main()
{
float f1, f2;
int i, j;
f1 = 2.6;
f2 = 0.1;
printf("adj month# value");
for(i=1; i<13; i++) {
j = i * f1 - f2;
printf("\n %2d %2d",i, j);
}
}
a) Figure 1a code with 0.1 produces correct response
/* INT(2.6 * Month# - 0.1) */
main()
{
int i, j;
printf("adj month# value");
for(i=1; i<13; i++) {
j = i * 2.6 - 0.2;
printf("\n %2d %2d",i, j);
}
}
b) Figure 1b code with 0.1 still correct
/* INT(2.6 * Month#) */
main()
{
float f1;
int i, j;
f1 = 2.6;
printf("adj month# value");
for(i=1; i<13; i++) {
j = i * f1;
printf("\n %2d %2d",i, j);
}
}
c) 0.2 deleted also produces correct response
Figure 3. Zeller's algorithm with 0.2 replaced by 0.1 and Null
********************************************************************
Columns 6, 7, and 8 show that the maximum value that can be
subtracted form the 2.6 * Month# term is 0.2. Any larger number
causes an error for months April, September and February. In a
similar way the minimum number which can be subtracted is just
over zero since using zero causes an error for months July and
December. Because this algorithm uses the 0.2 value, it has
little margin for computational inaccuracy. A better choice which
provides equal margin between the two extremes is to use a value
of 0.1. The use of INT(2.6 * Month# - 0.1) worked correctly in
all my limited tests (see Figure 3).
Numbers such as 2.6 and 0.2 are called real or float numbers in
languages such as FORTRAN, PASCAL and C. Such numbers are
normally stored in a floating point format. One example is the
IEEE floating point number format as in some implementations of
the Language C. Real values here are called float and have 4
bytes, consisting of a sign bit, an 8-bit excess 127 binary
exponent, and a 23-bit mantissa. The mantissa represents the
number between 1.0 and 2.0. In these machines, after assignment,
0.2 will be stored exactly while 2.6 is stored as 2.5999999. When
multiplied by 12, for example, the value is 31.199998.
Subtracting 0.2 produces 30.999998 which truncates to 30, not the
required 31. This produced the type of error seen by running the
code in Figure 1a. Storage of the constants for the code of
Figure 1b is in double, using (typically on a pc) twice the
number of bits. Calculations are then made in double precision
arithmetic, and only then is the answer trimmed down to regular
float size. This double precision computation and how the
trimming is done allows the code of Figure 1b to yield the proper
result.
In general, whenever the difference of two noninteger numbers are
calculated (and especially when one or both are multiplied by
other factors so that any inaccurate representation is amplified
and then thresholded) the resultant answer should be suspect,
since it may not be exactly what is expected.
Since the value 2.599999 can be thought of as 2.6 minus a small
delta slightly larger than zero an interesting experiment was to
try using the other bound, subtracting zero instead of the 0.2
(see Figure 3c). Sure enough the resultant values are correct and
it even saves one operation and storage of one constant. But,
living on the edge, either edge, is definitely not recommended.
An exact, although less elagent algorithm, can be formulated by
noting each adjusted month contributes at least 30 plus 1 or 0
days. Table 2 shows this form using 2 for 30 modulo 7. The
desired values of column 6 are the sum of the previous values in
columns 7 and 8, e.g.,
Month#
2 * Month# + bits per Table 2, col 8 (9)
1
This method requires storage of a single 12 bit word and the
ability to shift a copy of the word by an amount equal to the
adjusted month number while counting the logical ones passing a
fixed position. Figure 4 shows one implementation using the
Language C that produces the correct result.
********************************************************************
month# month days/ col 3 col 4 col 5 col 7 col 8
month MOD 7 offset +2
1 March 31 3 2 2 0
2 April 30 2 3 5 2 1
3 May 31 3 2 7 2 0
4 June 30 2 3 10 2 1
5 July 31 3 2 12 2 0
6 August 31 3 3 15 2 1
7 September 30 2 3 18 2 1
8 October 31 3 2 20 2 0
9 November 30 2 3 23 2 1
10 December 31 3 2 25 2 0
11 January 31 3 3 28 2 1
12 February 3 31 2 1
Table 2. Alternative method also using the adjusted month
********************************************************************
********************************************************************
/* alternative integer algorithm */
typedef struct {
unsigned bit0 : 1;
unsigned bit1 : 1;
unsigned bit2 : 1;
unsigned bit3 : 1;
unsigned bit4 : 1;
unsigned bit5 : 1;
unsigned bit6 : 1;
unsigned bit7 : 1;
unsigned bit8 : 1;
unsigned bit9 : 1;
unsigned bit10 : 1;
unsigned bit11 : 1;
unsigned bit12 : 1;
unsigned bit13 : 1;
unsigned bit14 : 1;
unsigned bit15 : 1;
} flag_t;
union {
int iflag;
flag_t flag;
} u;
int i, j, m;
main()
{
printf("adj month# value");
for(i=1; i<13; i++) {
m = 2 * i;
u.iflag = 6868;
for(j=0; j u.iflag = u.iflag >> 1;
if(u.flag.bit0) m++;
}
printf("\n %2d %2d",i, m);
}
}
Figure 4. Alternative all integer algorithm
********************************************************************
}
Figure 4. Alternative all integer algorithm
*********************************************
December 13, 2017
Add comments