CS3172 > Mats > Assig.#4 > algorithms

J. Blustein

Web-centric Computing

[Course | Announcements | Materials | Resources]

Assig. #4: Calendar Algorithms

Below are three algorithms to help you: (1) Zeller's Algorithm (for computing the day of the week) with a (2) note about computing modulus division for negative values, and (3)  an algorithm to determine if a given year is a leap year.

Zeller's Algorithm for Day of the Week

Notation

× represents
multiplication
÷ represents
integer division (fractional portions are truncated)
a % b represents
modulo division of a by b
|x| represents
the absolute value of x
⌈x⌉ represents
the ceiling of x

Variables

Let

month be
the month of the year, with March=1, April=2,…, December=10, January=11, February=12
N.B.: January and February are considered to be part of the previous year.  If the month is January or February then you must subtract one from year (which is defined below).
day be
the day of the month
century be
the century
year be
the year within the century
See the note (above) about how the months of January and February change the value of year
weekday be
0 for Sunday, 1 for Monday, 2 for Tuesday,…, 6 for Saturday

then

weekday = ((13 × month − 1) ÷ 5 + year ÷ 4 + century ÷ 4 + day + year − 2 × century) % 7

For example: 14 May 2002

variable value
day 14
month  3
year  2
century 20

((13 × month − 1) ÷ 5 + year ÷ 4 + century ÷ 4 + day + year − 2 × century) % 7
= ((13 ×  3 − 1) ÷ 5
+  2 ÷ 4
+ 20 ÷ 4
+ 14
+ 2 − (2 × 20)) % 7
= (7 + 0 + 5 + 14 + −38) % 7
= −12 % 7 [see below for details on negative n]
= 2

So, 14 May 2002 was a Tuesday.

When n < 0

An easily programmed solution to compute the modulo division of a negative n  by a positive base  is to repeatedly increment n  by base  until an equivalent non-negative value for n is found.  In pseudo-code the appropriate algorithm is
while(n<0) {n ← n+base}

Since the number of times through the loop will be ⌈|n| / base⌉, so we can do the computation faster by applying the following

Equivalence for negative values of n 

n % base ≡ (n + (base × ⌈|n| / base⌉)) % base

In MathML notation that looks like: n (mod base) ≡ (n+base × ⌈|n|/base⌉ )(mod base)

Example (n = −12 and base = 7)
−12 % 7 ≡ (−12 + (7 ×⌈|−12|/7⌉)) % 7
≡ (−12 +(7 ×⌈12/7⌉)) % 7
≡ (−12 +(7 × ⌈1 + 5/7⌉)) % 7
≡ (−12 +(7 × 2)) % 7
≡ (−12 +14) % 7
≡ 2% 7
−12 % 7 ≡ 2

Leap Year Computation

In a leap year, February has 29 days; Otherwise it has 28 days.  A year is a leap year if it is divisible by 4 but not by 100, except that years divisble by 400 are leap years. (full citation below).  Pseudo-code based on the C code by K&R is 

function isleap(Y : CardinalNumber) : Boolean { [Y = 100×century + year]
  assert(Y > 0);
  if (0 = (Y % 400))
  then { isleap ← true; }
  else {
    if ((0 = (Y % 4)) and (not (0 = (Y % 100))))
    then { isleap ← true; }
    else { isleap ← false; }
  }
}

Examples

1900, 1984, and 2000 were leap years.  1899, 1977, and 2001 were not leap years.

To check our accuracy we can use the Unix cal (1) program: 

Unix% which cal
/usr/bin/cal
Unix% cal 2 1900
   February 1900
Su Mo Tu We Th Fr Sa
             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

Unix% cal 2 1984
   February 1984
Su Mo Tu We Th Fr Sa
          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

Unix% cal 2 2000
   February 2000
Su Mo Tu We Th Fr Sa
       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

Unix% cal 2 1899
   February 1899
Su Mo Tu We Th Fr Sa
          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

Unix% cal 2 1977
   February 1977
Su Mo Tu We Th Fr Sa
       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

Unix% cal 2 2001
   February 2001
Su Mo Tu We Th Fr Sa
             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

Unix%

References

Zeller's Algorithm is from
FORTRAN 77 for engineers and scientists by Larry Nyhoff and Sanford Leestma; © 1985 by Macmillan Publishing Company.
Chapter 16 Exercise #16 (page 236)
I added the part about negative values of n
Leap Year Algorithm is from
The C Programming Language (second edition) by Brian Kernighan and Dennis Ritchie; © 1988, 1978 by Bell Telephone Laboratories, Incorporated; Published by Prentice-Hall.
Page 41
The MathML Markup is courtesy of
itex2mml (© March 2001 Paul Gartside)
I used the online conversion form at <URL:http://pear.math.pitt.edu/mathzilla/itex2mmlFrag.html> on 17-Dec-2007 to create the single line of math markup.