Ultra-fast Algorithms for Working with Leap Years.

Introduction

A couple of years ago, I was trying to fix the Date object in a JavaScript interpreter for an embedded browser project. The bug was easy enough to fix because the code did not count the year 2000 as a leap year. What I found more disturbing was the way that code converts from the number of seconds since 1970 to a calendar day. There was a while() loop that subtracts the number of seconds in a year from the time value until that value becomes too small to continue. It takes into account whether a year is a leap year or not; but a lot of precious CPU cycles are wasted in that loop.

I tried searching the Internet for a better algorithm; but I kept running into different variations of that same while() loop. I gave up after many hours of searching that night. When I was reclining in my dentist's office the next day, I thought working on a puzzle like this would take my mind off the remodeling project going on inside my mouth.

I came up with a handful of macros for converting between days and years without the use of any loop or branches. I am sure somebody out there is already using something similar to these macros. I am only posting them here because I was not able to find them anywhere.

Leap Year

Please refer to this excellent article on the history and logic of determining a leap year: Leap Years. Here is a summary of the rules:

1. A year that is divisible by 4 is a leap year. (Y % 4) == 0
2. Exception to rule 1: a year that is divisible by 100 is not a leap year. (Y % 100) != 0
3. Exception to rule 2: a year that is divisible by 400 is a leap year. (Y % 400) == 0

These rules can be easily captured in a macro:

#define IS_LEAP_YEAR(Y)     ( ((Y)>0) && !((Y)%4) && ( ((Y)%100) || !((Y)%400) ) )

This macro counts the number of leap days up to January 1st of a given year. Keep in mind that if specified year is a leap year, the leap day has not happened before January 1st of that year. A counting algorithm requires a reference point. Any reference point is reasonable; but I chose midnight (12:00AM) January 1st of year 1 A.D.. The problem is reduced to counting the number of years that are divisible by 4 without the years that are divisible by 100, then add back in the number of years that are divisible by 400.

#define COUNT_LEAPS(Y)   ( ((Y)-1)/4 - ((Y)-1)/100 + ((Y)-1)/400 )

Counting Days and Years

This macro uses the macro above to count the number of days up to January 1st of the specified year.

#define COUNT_DAYS(Y)  ( ((Y)-1)*365 + COUNT_LEAPS(Y) )

This macro counts the number of years spanned by a given number of days. When I tried to take the inverse of the formula in the COUNT_DAYS() macro, it gets real messy. I took another approach that proves to render the same numerical result. I could just divide the number of days by 365 if I did not have to account for those leap years. The problem is just removing the pesky leap days from the total number of days. Then I had to account for the fact that my reference point starts at year 1 A.D..

#define COUNT_YEARS(D)  ( 1 + ( (D) - COUNT_LEAPS((D)/365) )/365 )

Conversions

This macro is useful for finding the year that results from adding a number of days to January 1st of starting year. This is the original problem I was trying to solve. JavaScript stores a time value as the number of seconds since midnight January 1st, 1970. The time value is called epoch time and midnight January 1st, 1970 is the epoch. Once epoch time is converted to number of days since the epoch, this macro will calculate the calendar year that the time value represents.

#define YEAR_PLUS_DAYS(Y,D)  COUNT_YEARS(  D + COUNT_DAYS(Y) )

This macro calculates the number of days from January 1st of year A to January 1st of year B.

#define DAYS_BETWEEN_YEARS(A,B)  (COUNT_DAYS(B) - COUNT_DAYS(A))

Benefits

• When a parameter is a constant like 1970, the compiler will collapse most expressions into a constant.
• All these macros use integer arithmetic. They can be used on even the simplest embedded processor.
• Did I mention these are fast? No overhead for loops. No branches to mess up the predictive processor cache.

Template Functions

Here are the equivalent template functions for C++:

template <class T> IsLeapYear(const T& y)
{ return (y>0) && !(y%4) && ( (y%100) || !(y%400) ); }
template <class T> CountLeaps(const T& y)
{ return (y-1)/4 - (y-1)/100 + (y-1)/400; }
template <class T> CountDays(const T& y)
{ return (y-1)*365 + CountLeaps(y); }
template <class T> CountYears(const T& d)
{ return 1 + ( d - CountLeaps(d/365) )/365; }