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

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

*********************************************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