static const int daysToMonth365[13] = {

0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365

};

static const int daysToMonth366[13] = {

0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366

};

int DaysInMonth(int year, int month) {

const int* days = IsLeapYear(year) ? daysToMonth366

: daysToMonth365;

return days[month] - days[month - 1];

}

So, what's wrong with this code. Well, frankly, nothing at all ...

*unless*you're playing Gregorian Date Calculation Golf.

The main problem is that, as any schoolchild can tell you, you only need to know if the year is a leap year when asked for the number of days in February. The code above calls "IsLeapYear(year)" for

*all*months. Determining if a year is actually a leap year is (relatively) non-trivial, so things seem to be less than optimal. Another point is that the constant arrays "daysToMonth365" and "daysToMonth366" are used in other algorithms in their library, but the subtraction due to re-use seems to be slightly heavy-handed. Optimizing compilers understandably have a tough time improving matters.

Here's another stab at the function:

static const int daysInMonth365[12] = {

31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31

};

int DaysInMonth(int year, int month) {

if ((month == February) && IsLeapYear(year)) {

return 29;

}

return daysInMonth365[month - 1];

}

In the true spirit of Gregorian Date Calculation Golf, a pedant might point out that the table memory references may have an adverse effect on CPU pipelining and caching (but only if they are blind to the enormous "if" statement preceding it!). If that's truly the case, the following implementation packs the table into a 64-bit constant that gets embedded in the machine code:

int DaysInMonth64(int year, int month) {

if ((month == February) && IsLeapYear(year)) {

return 29;

}

const uint64_t magic = 0x0FFBFEFFFDFF7F9F;

return int(magic >> ((month - 1) * 5)) & 31;

}

Again, on my machine compiled for x64, this is a smidgen faster than using the array-lookup. Not surprisingly, it performs terribly on 32-bit instruction sets because of the 64-bit shift involved.

A non-table version

*can*be written for 32-bit instruction sets by storing each table entry as two bits:

int DaysInMonth32(int year, int month) {

if ((month == February) && IsLeapYear(year)) {

return 29;

}

const int magic = 0x03BBEECC;

return ((magic >> (month << 1)) | -4) + 32;

}

A quick google for those magic numbers scores no hits, which suggests that these algorithms may be quite novel. I wonder why...

I spoke too soon. There are indeed algorithms out there that use just this kind of magic number. See http://chilliant.blogspot.co.uk/2015/06/gregorian-date-calculation-golf-2a.html

ReplyDelete