17
\$\begingroup\$

A couple of date-related questions have come up recently, and on both occasions I have been taken back to my 'early' days where one of my first forays in to programming involved implementing Zeller's Congruence.

Zeller's congruence is a neat calculation because it involves a mathematical approach to date manipulation, and the math relies on both modular and integral arithmetic, combined with a smart way of visualizing time progression.

$$ \begin{align} h =&\ \left(q + \left\lfloor \frac{13(m + 1)}{5} \right\rfloor + K + \left\lfloor \frac{K}{4} \right\rfloor + 5J + \left\lfloor \frac{J}{4} \right\rfloor \right) \mod7\\ where\\ h =&\ \text{the day of the week (0 is Saturday ... 6 is Friday)}\\ q =&\ \text{the day of the month}\\ m =&\ \text{the month (3 = March, 4 = April, ..., 13 = January, 14 = February)}\\ &\ \text{If Jan or Feb, then you have to adjust the year back by 1 year}\\ &\ \text{Jan 2001 is month 13 of year 2000}\\ K =&\ \text{the century count} \implies \left\lfloor\ \frac{\mathtt{adj.year}}{100}\right\rfloor\\ J =&\ \text{the adjusted year in the century} \implies (\ \mathtt{adj.year} \mod 100)\\ \end{align} $$

The two recent questions that have inspired me to go back and re-implement Zeller's Congruence are:

As a secondary exercise, I tested the code using the new-in-Java8 time API.


Zeller's Congruence

Note: The code contains comments which go some way to explaining how the congruence works

// Used for a quick validation of days in a month.
// Note filler at MONTHDAYS[0] because months are 1-based.
private static final int[] MONTHDAYS =
        { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

private static final boolean isLeap(final int year) {
    return (year % 4) == 0 && (year % 100 != 0 || year % 400 == 0);
}

/**
 * Calculate the day of the week (1=Monday, 7=Sunday) for the supplied
 * (valid) date.
 * @param year The year to calculate (year 1 or more recent)
 * @param month The month (1 through 12 for January through December) 
 * @param day The Day-in-month (1 through 28/29/30/31 depending on the month) 
 * @return The day of the week (1 represents Monday, 7 represents Sunday).
 * @throws IllegalArgumentException if the input values are not a valid date
 */
public static final int computeDayOfWeek(final int year, final int month, final int day)
        throws IllegalArgumentException {

    // easy checks for valid dates.
    if (year < 1 || month < 1 || month > 12 || day < 1 || day > MONTHDAYS[month]) {
        throw new IllegalArgumentException(String.format(
                "%04d-%02d-%02d is not a valid date", year, month, day));
    }
    // leap year validation
    if (day == 29 && month == 2 && !isLeap(year)) {
        throw new IllegalArgumentException(
                String.format(
                        "%04d-%02d-%02d is not a valid date (Feb 29 but not a leap year)",
                        year, month, day));
    }

    // Forumla is here: https://en.wikipedia.org/wiki/Zeller%27s_congruence
    // Using the wikipedia's variable names:

    // h = (q + floor((13*(m+1)/5)) + K + floor(K/4) + floor(J/4) + 5J)

    // translate variable names in to algorithm components.

    // q is the day of month.
    final int q = day;
    // m is the month, but Jan and Feb need to be month 13 and 14
    // respectively
    final int m = month + (month < 3 ? 12 : 0);
    // if the month is jan, or feb, then year is of the previous year.
    final int calcyear = year - (month < 3 ? 1 : 0);
    // K is the year-in-century
    final int K = calcyear % 100;
    // J is the century number
    final int J = calcyear / 100;

    /*
    Algorithm works by following a concept of adding days in to a
    sequence, and performing modular arithmetic. The fundamental concept 
    is that if you know one specific date's day-of-week,  then all you
    need to do is calculate how many days you are in front of, or behind
    that day.

    If you know the days, you can perform a %7 on that, and get the day
    difference.

    If you choose your algorithm to start on a specific day and call it
    0, then the difference from the %7 is simply the day. As it happens,
    to make things work well, starting with Saturday as day 0 is right.
    */

    // how many days (possibly %7) are we offset at this point in time?
    int offset = 0;

    /*

    Now, how to calculate the days between. Well, there are 36524 days in
    a century, unless the century is divisible by 4, in which case there is
    an extra day. so, the days between epoch and now is the number of
    centuries * days-in-century + number-of-4-centuries.

    But, because we only need extra days, we can do these things %7. So,
    since 36524%7 is 5, we need to add 5 days for each century since epoch.
    Additionally, we need to add another day for each of those special
    leap years that are divisible by 400
     */

    // 5 days per century plus the number of 400 years too.
    offset += J * 5 + J / 4;

    // now, inside a century, there's leap years....
    // a normal year has 365 days, which is 52 weeks and 1 day.
    // so, each year since the start, is 1 more day of offset. And, each
    // leap year adds another...
    offset += K + K / 4;

    /*
    So, that gives us the right number of offset days to get us to the
    current year.
    Now, if we start our logical year on March 1st, we don't need to
    worry about the odd day at the end of february. Also, the number of
    days in a month, starting from March, is:

    Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec,Jan,Feb
    31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 31, 28/29

    Notice how Aug and Jan are at positions 5 and 10?

    Also, a 30-day month adds 2 days of offset, and a 31-day month adds 3
    days of offset.  So, for each 30 day month we add 2 days, and for each
    31 day month we add 3.

    This formula can be hard-coded as (13 * (m + 1))/5

     */
    offset += (13 * (m + 1)) / 5;

    // Now all we need to do is add the days in our current month, to get
    // the final offset:
    offset += q;

    // Then, the actual day of week is the zero-day + offset % 7
    int h = offset % 7;

    // Now adjust the 0-6 based Saturday-Friday to a 1-7 based Monday-Sunday
    return ((h + 5) % 7) + 1;
}

Test Code

I used the Time API to test the code. Obviously, the time API's LocalDateTime class is able to give you the weekday for a given date. The above code is completely reinventing the wheel... I used that LocalDateTime to validate the results:

/*
 * method for testing only.
 */
private static final void check(LocalDateTime then, boolean print) {
    // do an us vs. them comparison
    int us = computeDayOfWeek(
            then.get(ChronoField.YEAR),
            then.get(ChronoField.MONTH_OF_YEAR),
            then.get(ChronoField.DAY_OF_MONTH));

    int them = then.get(ChronoField.DAY_OF_WEEK);

    if (us != them || print) {
        System.out.printf("%14s %14s is %s%n",
                then.toString(), DayOfWeek.of(them), DayOfWeek.of(us));
    }

    if (us != them) {
        throw new IllegalStateException(String.format(
                "Unable to correlate our calculation %d to the system %d",
                us, them));
    }
}

public static void main(String[] args) {

    LocalDateTime now = LocalDateTime.now().truncatedTo(ChronoUnit.DAYS);
    LocalDateTime past = LocalDateTime.of(1, 1, 1, 0, 0);

    LocalDateTime then = past;
    // test every day since 1 Jan, 0001 through to today
    while (then.isBefore(now)) {
        check(then, false);
        then = then.plusDays(1);
    }
    check(now, true);

    then = LocalDateTime.of(2, 1, 1, 0, 0);
    // recheck, and print the first year's dates.
    while (then.isAfter(past)) {
        then = then.minusDays(1);
        check(then, true);
    }

    LocalDateTime future = now.plusYears(1);
    then = now;
    // check, and print the next year's dates.
    while (then.isBefore(future)) {
        check(then, true);
        then = then.plusDays(1);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ As a general note: you might want to move away from those half-manual tests and utilize a proper test framework such as JUnit to run tests automatically. \$\endgroup\$ – Ingo Bürk Oct 26 '14 at 9:27
  • \$\begingroup\$ "If it needs a comment it should be a function." That said I think you have too many comments. The name of the algorithm and the wiki link should be enough if you use descriptive names. \$\endgroup\$ – Emily L. Oct 26 '14 at 10:32
7
\$\begingroup\$
final int q = day;
final int m = month + (month < 3 ? 12 : 0);
final int calcyear = year - (month < 3 ? 1 : 0);
final int K = calcyear % 100;
final int J = calcyear / 100;

int offset = 0;
offset += J * 5 + J / 4;
offset += K + K / 4;
offset += (13 * (m + 1)) / 5;

offset += q;

int h = offset % 7;

return ((h + 5) % 7) + 1;

That's the code without any comments. I'm going to try to optimize it, although you'll have to do your own performance testing.

A couple things come to mind already:

final int m = month + (month < 3 ? 12 : 0);
final int calcyear = year - (month < 3 ? 1 : 0);

Assign the month < 3 to isJanOrFeb instead.

final boolean isJanOrFeb = month < 3;
final int m = month + (isJanOrFeb ? 12 : 0);
final int calcyear = year - (isJanOrFeb ? 1 : 0);

Don't do unnecessary assignment...

int offset = 0;
offset += J * 5 + J / 4;

It's a waste.

int offset = J * 5 + J / 4;

There's only 1 usage of m...

offset += (13 * (m + 1)) / 5; 

And since it's final only one set too

final int m = month + (month < 3 ? 12 : 0);

So maybe combine the + 1?

final int m = month + (isJanOrFeb ? 13 : 1);
offset += (13 * m) / 5;

This bit of code can be collapsed easily...

int h = offset % 7;

return ((h + 5) % 7) + 1;

To this

int h = (offset + 5) % 7;

return h + 1;

But then again, one wonders why you don't declare h as final... or whether you need it at all.

return ((offset + 5) % 7) + 1;

All I did was remove the h line and replace h with offset.


Final code:

final int q = day;
final boolean isJanOrFeb = month < 3;
final int m = month + (isJanOrFeb ? 12 : 0) + 1;
final int calcyear = year - (isJanOrFeb ? 1 : 0);
final int K = calcyear % 100;
final int J = calcyear / 100;

int offset = q;
offset += (13 * m) / 5;
offset += K + (K / 4);
offset += (J * 5) + (J / 4);

return ((offset + 5) % 7) + 1;

I moved the statements around so it looks more like the original function.

\$\endgroup\$
  • \$\begingroup\$ then why not just return ((q + (13 * m) / 5 + K + K / 4 + J * 5 + J / 4 + 5) % 7) + 1; ? \$\endgroup\$ – rolfl Oct 24 '14 at 10:48
  • \$\begingroup\$ @rolfl I spent a good 20 minutes writing that I want to collapse the code to an inline call, then deleting it, and rewriting it. Then deleting it again. At the end of the day, you went with a commented approach. Thus the code should serve the comments. One could also simply have said "we use this algorithm, wikipedia link, and we add 5 here because link says this is for ISO date and we add 1 here because mon-sun instead sat-fri." \$\endgroup\$ – Pimgd Oct 24 '14 at 10:52
  • \$\begingroup\$ @rolfl So I'm a bit conflicted still whether you should keep it as expanded as it is or whether you should inline everything. I gave improvements for both ways (adding isJanOrFeb would be good for readability, the rest is good for simplifying). \$\endgroup\$ – Pimgd Oct 24 '14 at 10:53
  • \$\begingroup\$ Soo... you spent 20 minutes doing what the compiler already does for you? \$\endgroup\$ – Emily L. Oct 26 '14 at 10:30
  • \$\begingroup\$ @EmilyL. We ended up running tests. In the end we managed to get 40% performance increase. Mostly by doing nasty things like (J >> 2). Removing q from the equation and just adding day also made things a lot faster. \$\endgroup\$ – Pimgd Oct 26 '14 at 13:48
2
\$\begingroup\$

Since the method is only concerned up to days and the day of the week, I think you can opt for the "simpler" LocalDate type for your testing.

DayOfWeek also has a static from() method that works directly on TemporalAccessor types, of which LocalDate inherits. Therefore, you can replace:

DayOfWeek.of(then.get(ChronoField.DAY_OF_WEEK))

With just:

DayOfWeek.from(then)

On the topic of testing, you probably have good reasons for just using public static void main, but for the sake of any beginners who may have stumbled upon this question while they are learning about unit testing, may I suggest something in that vein instead?

Sample implementation (I'm using TestNG and Hamcrest matchers below):

private static final LocalDate now = LocalDate.now();
private static final LocalDate past = LocalDate.of(1, 1, 1);
private static final LocalDate future = now.plusYears(1);

private static final void check(final LocalDate then, boolean print) {
    DayOfWeek actual = DayOfWeek.of(computeDayOfWeek(then.get(ChronoField.YEAR),
            then.get(ChronoField.MONTH_OF_YEAR), then.get(ChronoField.DAY_OF_MONTH)));
    DayOfWeek expected = DayOfWeek.from(then);
    if (print) {
        System.out.printf("%14s %14s is %s%n", then.toString(), expected, actual);
    }
    assertThat(then.toString() + " is on " + expected, actual, equalTo(expected));
}

@Test
public void testPast() {
    LocalDate then = past;
    // test every day since 1 Jan, 0001 through to today
    while (then.isBefore(now)) {
        check(then, false);
        then = then.plusDays(1);
    }
}

@Test
public void testToday() {
    check(now, true);
}

@Test
public void testFirstYear() {
    LocalDate then = past.plusYears(1);
    while (then.isAfter(past)) {
        then = then.minusDays(1);
        check(then, true);
    }
}

@Test
public void testFuture() {
    LocalDate then = now;
    while (then.isBefore(future)) {
        check(then, true);
        then = then.plusDays(1);
    }
}

P.S.: I usually prefer using TestNG's DataProvider annotations for parameterized testing, but I figured that telling TestNG to iterate through all the dates since 1st January 1 AD may be too much... hence the manual looping in each test method here.

P.P.S.: One very minor point, if I were you I will also consider putting the two validation if statements in their own validation method.

\$\endgroup\$
  • \$\begingroup\$ I missed the notification of this answer somehow. Thanks for the good feedback. I am more familiar with jUnit, but your point about testing is good, and the pointers in to the static DayOfWeek methods too. \$\endgroup\$ – rolfl Oct 26 '14 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.