Date calculation optimizations are often overlooked because of the scope for subtle errors. If you are writing production code that is going to be used in anger, I

*strongly*suggest you check and re-check everything you see hereafter. At the very least, run it through a thorough test suite.

So, what are the rules of "Gregorian Date Calculation Golf"? Well...

- Pseudo-code must be presented in C/C++/C# flavour.
- The integer type "int" is expected to be at least 32 bits long.
- The integer type "long" is expected to be at least 64 bits long.
- A (proleptic) Gregorian year is assumed to be between 1 (meaning 1 CE) and 65535 inclusive.
- A Gregorian month is assumed to be between 1 (January) and 12 (December) inclusive.
- Leap days must be handled correctly.
- Time and timezones are ignored.
- Integer, arithmetic divisions (and their cousins) are not permitted.

Rule 8 is where the fun starts!

To warm up, let's assume we want to decide whether a Gregorian year is a leap year.

According to Wikipedia, the logic is:

if(yearis not exactly divisible by 4)then(it is a common year)elseif(yearis not exactly divisible by 100)then(it is a leap year)elseif(yearis not exactly divisible by 400)then(it is a common year)else(it is a leap year)

So here's an obvious implementation:

bool IsLeapYear(int year) {

if ((year % 4) != 0) {

return false;

}

if ((year % 100) != 0) {

return true;

}

if ((year % 400) != 0) {

return false;

}

return true;

}

However, the "%" modulo operator involves an implicit division, violating our Rule 8. We can remove two of the divisions by using the bitwise-and operator "&":

bool IsLeapYear(int year) {

if ((year & 3) != 0) {

return false;

}

int century = year / 100;

if ((century * 100) != year) {

return true;

}

if ((century & 3) != 0) {

return false;

}

return true;

}

However, there's still a division by a constant (100). Fortunately, we can use the fact that:

x / c = x * (1 / c)

This technique is known as "Integer Division by Constants". Indeed, any optimizing compiler worth its salt will convert the division in the code above to a multiplication. But, in the spirit of Gregorian Date Calculation Golf, we'll do it explicitly.

bool IsLeapYear(int year) {

if ((year & 3) != 0) {

return false;

}

int century = (((year * 0x47AF) >> 16) + year) >> 7;

if ((century * 100) != year) {

return true;

}

if ((century & 3) != 0) {

return false;

}

return true;

}

This can be needlessly re-factored to:

bool IsLeapYear(int year) {

if ((year & 3) == 0)

{

int century = (((year * 0x47AF) >> 16) + year) >> 7;

return ((century * 100) != year) || ((century & 3) == 0);

}

return false;

}

So, can we convert Gregorian year/month/day triplets to and from serials (i.e. the number of days since an epochal date)? Of course we can! Next time.

## No comments:

## Post a Comment