Algorithms for calculating the difference of dates in days

# 1. Introduction

While demystifying the magic constant 116444736000000000, I had to calculate how many days lie between two dates. A quick internet search gave several online calculators, so after some seconds I had the answer. Some time afterwards however, I thought about how to calculate this difference and did another web search about algorithms for this task. Unfortunately this search was quite less successful: Only very few search results revealed - most of them used built-in date objects of the particular languages (e.g. the DateTime class of .NET), other direct implementations were less documented and not easy to understand.
Therefore I decided to stop my search pretty soon and think about for myself about this problem. The result is following three algorithms on how to calculate the difference of two dates in days (note that the names are invented by me ;) ) :

• Increment-Day Algorithm
• Direct Three-Step Algorithm
• Origin-based Algorithm

Note: I have invented the names of the algorithms myself, so probably you won't find those expressions anywhere else...

This article explains those three algorithms as well as my sample implementation in C# including some little related utility functions.

## 1.1 Technical prerequisites & conventions

• A date defined by three integer values: y (year), m (month) and d (day).
• Input for each algorithm is two dates: date1 = (y1, m1, d1) and date2 = (y2 m2 d2).
• Precondition: Date1 lies before date2.
Note that this just simplifies the explanation, but is actually no contraint because the dates can be easily swapped before passed as input to any algorithm.
• Date1 is also called the preceding date while date2 is also called the subsequent date.
• Example dates are given in form YYYY-MM-DD, e.g. 1983-03-18 means March 18th 1983.

Ok, so let's start!

# 2. Increment-Day Algorithm

This algorithm uses a simple approach: While date1 lies before date2, increment date1 by one day until date1 equals date2. The result is the number of increments. Easy, huh? Let's have a more detailed look...

At first, determine if date1 lies before date2. So first check the year: If y1 < y2 date1 lies before date2. If y1 > y2 then not. More interesting is the case when y1 equals y2: Then we have to look at the months: if m1 < m2, date1 precedes date2; if m1 > m2, then date1 is after date2. Again, if m1 == m2, we have finally to check d1 against d2. Here an exemplary implementation:

public static bool IsDate1BeforeThanDate2(int y1, int m1, int d1, int y2, int m2, int d2)
{
return (y1 < y2 ? true : (y1 == y2 ? (m1 < m2 ? true : (m1 == m2 ? d1 < d2 : false) : false);
}

The second issue is the increment of a date by one day. Most cases are simple, e.g. 2014-10-03 incremented by one will result in 2014-10-04.
However, special care have to be taken if the day is the last one in current month. Then the next day is the first one of the following month. Keep in mind that the number of days in Februaray depends if the current year is a leap year or not. Finally, another special case is December 31st where the next day is January 1st of the following year.

If we think further, let's first declare three helper functions:

a) A function to detect if the current year is a leap year. A leap year is divisable by 4 but not divisable by 100, with the exception that if it's divisable by 400 it's again a leap year. Here a sample implementation:

public static bool IsLeapYear(int year)
{
return (year % 4 == 0) && ( (year % 100 != 0) || (year % 400 == 0) );
}

b) A function to check if the current day is the last day in a month. A sample implementation taking correctly leap years into account may look like this:

public static bool IsLastDayInMonth(int year, int month, int day)
{ /* check for month in valid range [1, 12] discarded here */
return ((month == 1 && day == 31) ||
(IsLeapYear(year) ? (month == 2 && day == 29) : (month == 2 && day == 28)) ||
(month == 3 && day == 31) ||
(month == 4 && day == 30) ||
(month == 5 && day == 31) ||
(month == 6 && day == 30) ||
(month == 7 && day == 31) ||
(month == 8 && day == 31) ||
(month == 9 && day == 30) ||
(month == 10 && day == 31) ||
(month == 11 && day == 30) ||
(month == 12 && day == 31)
);
}

Note that in the conclusion chapter you find another implementation of IsLastDayInMonth() using a lookup tables.

c) Finally a function for the special case if the current day is the last day in the year (thus is the 12-31). That's pretty easy: use the IsLastDayInMonth() method and check additionally if month equals 12.

Using those utlity functions, we can define a method to increment a given date by one day. We assume here that the date is given by global variables year, month and day:

public void IncreaseDateByOneDay()
{
if (IsLastDayInMonth(year, month, day))
{
if (IsLastMonthInYear(month))
{
month = 1;
day = 1;
year++;
}
else
{
day = 1;
month++;
}
}
else
{
day++;
}
}

Now we have everything we need and the actual implementation using above functions is as easy as pie:

public override int GetDifference(int y1, int m1, int d1, int y2, int m2, int d2)
{
/* save preceding date to class variables which are modified by IncreaseDateByOneDay */
int year = y1;
int month = m1;
int day = d1;

int days = 0;
while (IsDate1BeforeThanDate2(year, month, day, y2, m2, d2))
{
days++;
IncreaseDateByOneDay(); /* works on year, month and day variables */
}

return days;
}

# 3. Direct Three-Step Algorithm

As the name suggests, this algorithm works in three steps where in each step one part of the date difference is calculated. The sum of the calculated difference of each step is the result. Those are the three steps:

1. Calculate the remaing days in the preceding year. In other words, calculate the difference of y1-m1-d1 until y1-12-31.
2. Count the whole years between both dates and get the number of days.
3. Calculate the outstanding days in the subsequent year. In other words, calculate the difference of y2-01-01 (excluding) until y2-m2-d2.

Example: Get the difference from 2002-11-12 until 2005-08-20

1. Calculate the remaining days from 2002-11-12 to 2002-12-31. Those are n1 = 49 days.
2. Calculate the days of all full years. 2003 has 365 days and 2004 has 366 days (leap year!), that are in total n2 = 731 days.
3. Calculate the remaining days in the last year, from 2004-12-31 to 2005-08-20. Those are n3 = 232 days. (Note that we start from the 31st December as the starting day is not included.)

The final result is: n1 + n2 + n3 = 49 + 731 + 232 = 1012 days

For this algorithm, a lookup table is used which holds the accumulated days of all whole months. The month is used as the index for access. E.g. for March, we get 59 because January and February (which are the preceding full months of March) have together 59 days (31+28). As you might guess now, we will use actually two lookup table, one for leap years and the other for non-leap years as the values differ starting from February. Do not get confused by the fact we start counting the months from 1 (January) while the arrays are naturaly zero-based. Here are both tables:

int[] daysUpToMonth = { 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334 };
int[] daysUpToMonthLeapYear = { 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335 };

1. To get the remaining days in a year, calculate the days from the beginning of the year until date1 (so from y1-01-01 to y1-m1-d1) using our lookup tables and subtract them from the total number of this year.

Using the example from above, let's get the remaining days in year 2002 from 11-12 onwards: From non-leap year lookup table we get 304 for November. Adding the 12 remaining days in November results in 316. Those are the number of days from 2002-01-01 (including) until 2002-11-12. So to get the remaining days in 2002 from 2002-11-12, we just subtract the 316 from the total number of days of 2002, so 365 - 316 = 49 days.

Here the code of the function GetRemainingDaysInYear:

public int GetRemainingDaysInYear(int month, int day, bool isLeapYear)
{
if (isLeapYear)
{
return 366 - (daysUpToMonthLeapYear[month - 1] + day);
}
else
{
return 365 - (daysUpToMonth[month - 1] + day);
}
}

2. Calculating the days of all full years is easy. We just iterate over all years and add 365 days for non-leap years respectively 366 for leap years. I'll skip the code at this point, we will see it in the full listing.

3. Calculate the remaining days in the last year is also easy, because we have already discussed it in step 1!

public int GetDaysInYearTillDate(int month, int day, bool isLeapYear)
{
if (isLeapYear)
{
return daysUpToMonthLeapYear[month - 1] + day;
}
else
{
return daysUpToMonth[month - 1] + day;
}
}

So now we have all intermediate steps, ready to be assembled to our final implementation... But wait, what happens if both given dates d1 and d2 lie in the same year???

Well, if you think about, our current implementation does not correctly handle it. Even the first step would already add too many days, so we have to handle this case especially:
Again we use the lookup tables and subtract the lookup values of both months to get intermediate difference diff1 (solely for the months). Additionally we subtract both day values and add this difference to diff1. Note that this works even if day2 is smaller than day1 as the difference is negative in this case and thus we actually subtract those days from diff1. As always, leap years have to be considered again, this result in following implementation:

public int GetDiffInDaysInSameYear(int month1, int day1, int month2, int day2, bool isLeapYear)
{
if (isLeapYear)
{
return daysUpToMonthLeapYear[month2 - 1] - daysUpToMonthLeapYear[month1 - 1] + (day2 - day1);
}
else
{
return daysUpToMonth[month2 - 1] - daysUpToMonth[month1 - 1] + (day2 - day1);
}
}

Finally, using our developed helper functions, we can now built now the actual implementation as follows:

public override int GetDifference()
{
if (yearPreceding == yearSubsequent)
{ /* same year, easy special case */
return GetDiffInDaysInSameYear(monthPreceding, dayPreceding, monthSubsequent, daySubsequent, DateDiffUtil.IsLeapYear(yearPreceding));
}
else
{
int resultDays = 0;
/* Step 1: handle first (incomplete) year */
resultDays = GetRemainingDaysInYear(monthPreceding, dayPreceding, DateDiffUtil.IsLeapYear(yearPreceding));
/* first year is now handled */
yearPreceding++;
/* Step 2: handle 'full' years */
while (yearPreceding < yearSubsequent)
{
resultDays += DateDiffUtil.IsLeapYear(yearPreceding) ? 366 : 365;
yearPreceding++;
}
/* Step 3: handle last (incomplete) year */
resultDays += GetDaysInYearTillDate(monthSubsequent, daySubsequent, DateDiffUtil.IsLeapYear(yearSubsequent));
return resultDays * (IsDate1AfterDate2 ? -1 : 1);
}
}

# 4. Origin-based Algorithm

The Origin-based algorithm defines an articifial origin or zero-point in time. In our case we define the date 01-01-01 (January 1st in year 1) as this origin. To calculate the difference of two dates:

• first calculate the differences of both dates to this origin
• then subtract those differences from each other to get the actual result

As we will see below, the zero-point 01-01-01 makes it easy and fast to calculate the time span from any date to this origin. This algorithm uses the same tables daysUpToMonth and daysUpToMonthLeapYear as described previously.

The actual core of this algorithm is the fast calculation of the duration of any date to the origin.

1. Assume we just want to get the difference from 01-01 of any year to the origin, thus only full years. Well, what we have need is the number of leap years in this duration - this gives us the number of additional days to add. Because the origin year is 1, we can derive following formula:

numOfLeapsYear = (year-1) / 4 - (year-1) / 100 + (year-1) / 400

We have to subtract one because we start at origin year 1 - so e.g. for year 4, there is no leap year inbetween. To calculate the number of days, multiply the number of years with 365 and add the value of numOfLeapsYear because this is exactly the number of additional days of the leap years.

2. To add the remaining days of the given date, use again the lookup tables to add the remaining duration of the whole months and finally the remaining days.

Example: Get the difference from 1089-02-18 to the origin

1. numOfLeapsYear = (1089-1) / 4 - (1089-1) / 100 + (1089-1) / 400 = 264.
2. Number of days between 1089-1-1 to origin: res = 365 * (1089-1) + numOfLeapsYear = 365 * (1089-1) + 264 = 397384.
3. Add the remaining in years 1089: result = result + 49 = 397384 + 49 = 397433.

So for each given date date1 and date2, calculate the number of days to the origin and then get the difference date2-date1. One special case have again to be considered if the the given date is a leap year - then we have to use the leap year lookup table. So the final implementation looks like the following:

public int GetDifference()
{
int daysOffset = GetDaysOffsetFromOrigin(y1, m1, d1);
int daysOffset2 = GetDaysOffsetFromOrigin(y2, m2, d2);

return (daysOffset2 - daysOffset);
}

public int GetDaysOffsetFromOrigin(int year, int month, int day)
{
if (DateDiffUtil.IsLeapYear(year))
{
year--;
int numOfLeapsYear = year / 4 - year / 100 + year / 400;
return year * 365 + numOfLeapsYear + daysUpToMonthLeapYear[month - 1] + day - 1;
}
else
{
year--;
int numOfLeapsYear = year / 4 - year / 100 + year / 400;
return year * 365 + numOfLeapsYear + daysUpToMonth[month - 1] + day - 1;
}
}

# 5. Conclusion

Well, not much to say... Just three different algorithms to calculate the difference in days of two dates.
As promised in chapter 1, here is another implementation of IsLastDayInMonth function using lookup tables:

public static bool IsLastDayInMonth(int year, int month, int day)
{ /* The check for valid month values [1, 12] is discarded here */
int[] daysPerMonth = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int[] daysPerMonthLeapYear = { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
if (IsLeapYear(year))
{
return (daysPerMonthLeapYear[month-1] == day);
}
else
{
return (daysPerMonth[month-1] == day);
}
}

Hope you liked it! Drop me a line you could use some of my code or even have implemented other approaches to solve this problem - I am interested!

Sunshine, November 2014