12,406,649 members (52,433 online)
alternative version

94.9K views
28 bookmarked
Posted

# Ultra-fast Algorithms for Working with Leap Years.

, 9 Jun 2004 LGPL3
 Rate this:
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; }```

## Share

 Software Developer (Senior) United States
No Biography provided

## You may also be interested in...

 First Prev Next
 C function T800G15-Nov-13 9:18 T800G 15-Nov-13 9:18
 Divide by four optimization. Rafa_10-Sep-09 1:27 Rafa_ 10-Sep-09 1:27
 Re: Divide by four optimization. Rafa_10-Sep-09 1:53 Rafa_ 10-Sep-09 1:53
 Re: Divide by four optimization. Ted Nguyen11-Sep-09 13:17 Ted Nguyen 11-Sep-09 13:17
 New Algorithms for Leap year Joshua.Chien27-Aug-05 3:28 Joshua.Chien 27-Aug-05 3:28
 Re: New Algorithms for Leap year Ted Nguyen29-Aug-05 11:29 Ted Nguyen 29-Aug-05 11:29
 Re: New Algorithms for Leap year Joshua.Chien29-Aug-05 14:50 Joshua.Chien 29-Aug-05 14:50
 COUNT_YEARS breaks down? Anonymous29-Jun-05 3:32 Anonymous 29-Jun-05 3:32
 Excellent Find!!! Ted Nguyen29-Jun-05 22:13 Ted Nguyen 29-Jun-05 22:13
 What???? zirconia22-Jun-04 6:30 zirconia 22-Jun-04 6:30
 "Columbus Egg" or "Every Cycle Counts" Ted Nguyen22-Jun-04 8:53 Ted Nguyen 22-Jun-04 8:53
 Re: "Columbus Egg" or "Every Cycle Counts" Anonymous22-Jun-04 11:59 Anonymous 22-Jun-04 11:59
 Good Stuff.. Chris Meech10-Jun-04 2:48 Chris Meech 10-Jun-04 2:48
 Comments peterchen10-Jun-04 1:53 peterchen 10-Jun-04 1:53
 Macros are NOT intuitive. WREY10-Jun-04 0:48 WREY 10-Jun-04 0:48
 Macros are defined in the ANSI standard ! Kochise10-Jun-04 3:01 Kochise 10-Jun-04 3:01
 Re: Macros are defined in the ANSI standard ! John A. Johnson10-Jun-04 6:46 John A. Johnson 10-Jun-04 6:46
 Re: Macros are NOT intuitive. Ted Nguyen10-Jun-04 6:27 Ted Nguyen 10-Jun-04 6:27
 Re: Macros ARE intuitive. caedisius17-Jun-04 16:36 caedisius 17-Jun-04 16:36
 Re: Macros are NOT intuitive. Frank Dowling1-Sep-05 8:16 Frank Dowling 1-Sep-05 8:16
 Last Visit: 31-Dec-99 18:00     Last Update: 30-Jul-16 13:03 Refresh 1