Click here to Skip to main content
15,867,308 members
Articles / Programming Languages / C
Article

Ultra-fast Algorithms for Working with Leap Years.

Rate me:
Please Sign up or sign in to vote.
3.48/5 (12 votes)
9 Jun 2004LGPL34 min read 115.7K   28   21
Algorithms for counting leap years and converting between calendar year and epoch year.

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; }

License

This article, along with any associated source code and files, is licensed under The GNU Lesser General Public License (LGPLv3)


Written By
Software Developer (Senior)
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
SuggestionC function Pin
T800G15-Nov-13 9:18
T800G15-Nov-13 9:18 
GeneralDivide by four optimization. Pin
Rafa_10-Sep-09 1:27
Rafa_10-Sep-09 1:27 
GeneralRe: Divide by four optimization. Pin
Rafa_10-Sep-09 1:53
Rafa_10-Sep-09 1:53 
GeneralRe: Divide by four optimization. Pin
Ted Nguyen11-Sep-09 13:17
Ted Nguyen11-Sep-09 13:17 
GeneralNew Algorithms for Leap year Pin
Joshua.Chien27-Aug-05 3:28
Joshua.Chien27-Aug-05 3:28 
GeneralRe: New Algorithms for Leap year Pin
Ted Nguyen29-Aug-05 11:29
Ted Nguyen29-Aug-05 11:29 
GeneralRe: New Algorithms for Leap year Pin
Joshua.Chien29-Aug-05 14:50
Joshua.Chien29-Aug-05 14:50 
QuestionCOUNT_YEARS breaks down? Pin
Anonymous29-Jun-05 3:32
Anonymous29-Jun-05 3:32 
AnswerExcellent Find!!! Pin
Ted Nguyen29-Jun-05 22:13
Ted Nguyen29-Jun-05 22:13 
GeneralCongratulations - Universally Useful Algorithms Pin
JSadleir16-Jun-05 1:53
JSadleir16-Jun-05 1:53 
QuestionWhat???? Pin
zirconia22-Jun-04 6:30
zirconia22-Jun-04 6:30 
Answer&quot;Columbus Egg&quot; or &quot;Every Cycle Counts&quot; Pin
Ted Nguyen22-Jun-04 8:53
Ted Nguyen22-Jun-04 8:53 
GeneralRe: &quot;Columbus Egg&quot; or &quot;Every Cycle Counts&quot; Pin
Anonymous22-Jun-04 11:59
Anonymous22-Jun-04 11:59 
GeneralGood Stuff.. Pin
Chris Meech10-Jun-04 2:48
Chris Meech10-Jun-04 2:48 
GeneralComments Pin
peterchen10-Jun-04 1:53
peterchen10-Jun-04 1:53 
GeneralMacros are NOT intuitive. Pin
WREY10-Jun-04 0:48
WREY10-Jun-04 0:48 
GeneralMacros are defined in the ANSI standard ! Pin
Kochise10-Jun-04 3:01
Kochise10-Jun-04 3:01 
GeneralRe: Macros are defined in the ANSI standard ! Pin
andyj11510-Jun-04 6:46
andyj11510-Jun-04 6:46 
GeneralRe: Macros are NOT intuitive. Pin
Ted Nguyen10-Jun-04 6:27
Ted Nguyen10-Jun-04 6:27 
GeneralRe: Macros ARE intuitive. Pin
caedisius17-Jun-04 16:36
caedisius17-Jun-04 16:36 
GeneralRe: Macros are NOT intuitive. Pin
1-Sep-05 8:16
suss1-Sep-05 8:16 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.