The implementation of calculating the number of days between 2 dates

Question

What's the most efficient way to calculate the number of days between 2 dates? Basically I'm asking how our favourate datetime libraries are implemented.

I quickly implemented a solution that is ~O(n) as I run through 1 iteration per 4 years. (Code attached below)

I was asked by an intro to problem solving with computers class to implement this, but they're simply iterating through everyday instead of every 4 years.. so I'm not content with that solution and came up with the one below. However, is there a more efficient solution available? If so, how do they accomplish it?

#include <iostream>

using namespace std;

#define check_leap(year) ((year % 400 == 0) || ((year % 4 == 0) && (year % 100 != 0)))
#define debug(n) cout << n << endl

int get_days(int month, bool leap){
    if (month == 2){
        if (leap) return 29;
        return 28;
    } else if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12){
        return 31;
    } else {
        return 30;
    }
}


int days[] = {31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};

#define days_prior_to_month(n) days[n-2]
int num_days_between(int month1, int day1, int month2, int day2, bool leap){
    if (month2 > month1)
        return ((days_prior_to_month(month2) - days_prior_to_month(month1+1)) + get_days(month1, leap) - day1 + 1 + day2) + ((leap &&  month1 <= 2 && 2 <= month2) ? 1 : 0);
    else if (month2 == month1)
        return day2;
    return -1;
}

int main(int argc, char * argv[]){
    int year, month, day, year2, month2, day2;
    cout << "Year: "; cin >> year;
    cout << "Month: "; cin >> month;
    cout << "Day: "; cin >> day;
    cout << "Year 2: "; cin >> year2;
    cout << "Month 2: "; cin >> month2;
    cout << "Day 2: "; cin >> day2;

    int total = 0;
    if (year2 != year){
        int leapyears = 0;
        total += num_days_between(month, day, 12, 31, check_leap(year));
        debug(total);
        total += num_days_between(1, 1, month2, day2, check_leap(year2));
        debug(total);
        int originalyear = year;
        year++;
        year = year + year % 4;
        while (year <= year2-1){
            leapyears += check_leap(year) ? 1 : 0;
            year += 4;
        }

        total += leapyears * 366;
        debug(total);
        total += max(year2 - originalyear - leapyears - 1, 0) * 365;
        debug(total);

    } else {
        total = num_days_between(month, day, month2, day2, check_leap(year));
    }
        cout << "Total Number of Days In Between: " << total << endl;
    system("PAUSE");
    return 0;
} 

Answer 1

You can convert a date to a Julian day number in O(1).

Subtract the two Julian day numbers.

Answer 2

All division is integer division, operator % is modulus.

Given integer y, m, d, calculate day number g as:

function g(y,m,d)
m = (m + 9) % 12
y = y - m/10
return 365*y + y/4 - y/100 + y/400 + (m*306 + 5)/10 + ( d - 1 )

Difference between two dates = g(y2,m2,d2) - g(y1,m1,d1)

Answer 3

Tyler Durden's solution is most elegant, but may need some explanation.

The beauty of the algorithm is the statement:

(m*306 + 5)/10

Which returns the number of days between March 1st, and the start of the 'm'th month after March. (If you want to prove it, just remember to use 'integer division' which truncates decimal parts)

To shoe horn standard dating conventions into this function, input values for month and year are shifted so that the calendar 'starts' in March instead of January.

m = (m + 9) % 12
y = y - m/10

Implementing this handles the problem of calculating "days per month" and leaves only 'days per year' to be calculated. Wikipedia provides sufficient explanation for that part.

http://en.wikipedia.org/wiki/Leap_year#Algorithm

Answer 4

The solution is in python, and it shouldn't be hard to convert to any other language.

def isLeapYear(year):
    if year%4 == 0:
        if year%100 == 0:
            if year%400 == 0:
                return True
            else:
                return False
        else:
            return True
    else:
        return False

def daysBetweenDates(year1, month1, day1, year2, month2, day2):
    cumDays = [0,31,59,90,120,151,181,212,243,273,304,334] #cumulative Days by month
    leapcumDays = [0,31,60,91,121,152,182,213,244,274,305,335] # Cumulative Days by month for leap year
    totdays = 0
    if year1 == year2:
        if isLeapYear(year1):
            return (leapcumDays[month2-1] + day2) - (leapcumDays[month1-1] + day1)
        else:
            return (cumDays[month2-1] + day2) - (cumDays[month1-1] + day1)

    if isLeapYear(year1):
        totdays = totdays + 366 - (leapcumDays[month1-1] + day1)
    else:
        totdays = totdays + 365 - (cumDays[month1-1] + day1)

    year = year1 + 1
    while year < year2:
        if isLeapYear(year):
            totdays = totdays + 366
        else:
            totdays = totdays + 365
        year = year + 1

    if isLeapYear(year2):
        totdays = totdays + (leapcumDays[month2-1] + day2)
    else:
        totdays = totdays + (cumDays[month2-1] + day2)
    return totdays

Answer 5

I wrote this formula based on suggestion from Doug Currie. I tested it till 2147483647 days back from today.

static int daysElapsed(int yearOne,int monthOne,int daysOne,int yearTwo,int monthTwo,int daysTwo)
{
    return (daysTwo-32075+1461*(yearTwo+4800+(monthTwo-14)/12)/4+367*(monthTwo-2-(monthTwo-14)/12*12)/12-3*((yearTwo+4900+(monthTwo-14)/12)/100)/4)-
                   (daysOne-32075+1461*(yearOne+4800+(monthOne-14)/12)/4+367*(monthOne-2-(monthOne-14)/12*12)/12-3*((yearOne+4900+(monthOne-14)/12)/100)/4);            
    }

Answer 6

You can also use the origin-based algorithm. You can count all days before the start date and end date and then find the difference between those counts:

totalDays = end_date_count - start_date_count

So for example (java code):

public class Origincount {
public static class Dates {
    private final Integer day;
    private final Integer month;
    private final Integer year;

    public Dates(String date) {
        String[] s = date.split("/");
        this.day = Integer.valueOf(s[0]);
        this.month = Integer.valueOf(s[1]);
        this.year = Integer.valueOf(s[2]);
    }
    public Integer getDay() {
        return day;
    }
    public Integer getMonth() {
        return month;
    }
    public Integer getYear() {
        return year;
    }
}

private static final Map<Integer, Integer> daysOfMonth = new HashMap<Integer, Integer>();

static {
    daysOfMonth.put(1, 31);
    daysOfMonth.put(2, 28);
    daysOfMonth.put(3, 31);
    daysOfMonth.put(4, 30);
    daysOfMonth.put(5, 31);
    daysOfMonth.put(6, 30);
    daysOfMonth.put(7, 31);
    daysOfMonth.put(8, 31);
    daysOfMonth.put(9, 30);
    daysOfMonth.put(10, 31);
    daysOfMonth.put(11, 30);
    daysOfMonth.put(12, 31);
}

public static Integer countLeapYears(Dates date) {
    Integer y = date.getYear();
    if(date.getMonth() <= 2) { y--; }
    return (y/4) - (y/100) + (y/400);
}

public static Integer daysMonth(Dates date) {
    Integer days = 0;
    for(int i=1; i<date.getMonth(); i++) {
        days += daysOfMonth.get(i);
    }
    return days;
}

public static void main(String[] args) {
    Dates start = new Dates("1/1/1901");
    Dates end = new Dates("31/12/2999");
    Integer countStart = (start.getYear()*365) + countLeapYears(start) + daysMonth(start) + start.getDay();
    Integer countEnd = (end.getYear()*365) + countLeapYears(end) + daysMonth(end) + end.getDay();

    System.out.println("Total days: "  + (countEnd-countStart));
}
}

Answer 7

Maybe this could help: (this program was written in c)

#include<stdio.h>


int gauss(int y)
{
int r;
r=(1+(5*((y-1)%4))+(4*((y-1)%100))+(6*((y-1)%400)))%7;
return r;
/*
 using gauss's algorithm to figure out the first day of the given year
 * visit:          https://en.wikipedia.org/wiki/Determination_of_the_day_of_the_week#Gauss.27s_algorithm

 */
 }
 int julian(int d,int m,int y){
 int j;
 j=(d + (((153*m)+2)/5) + (365*y) + (y/4) - (y/100) + (y/400));
 return j;
 /*
  * calculating julian number for a date so that we can calculate number of   days passed between the 
 * first day of that year and the given date
 * visit: http://www.had2know.com/society/number-days-between-two-dates.html 
 */
 }

 int main(){
 int d1,m1,y1,j1,j2,n,r,n1,abs;

 int d,m,y;

/*
 * d1= day date
 * d=d1
 * m1= month given by the user
 * m= month required for calculation
 * y1= year given by the user
 * y=year required for calculation
 */
 printf("Enter the day number of date: ");
 scanf("%d",&d1);
 printf("\nEnter the month number of date: ");
 scanf("%d",&m1);
 printf("\nEnter the year of date: ");
 scanf("%d",&y1);
 if(m1<13&&m1>2){
    m=m1-3;
    d=d1;
    y=y1;
    j1=julian(1,10,y-1);//did y-1 as for jan and feb we did the same

    j2=julian(d,m,y);

 }
 else if(m1==1 || m1==2)
 {
    m=m1+9;
    d=d1;
    y=y1-1;
     j1=julian(1,10,y);

    j2=julian(d,m,y);

  }
 printf("\ndate: %d/%d/%d",d1,m1,y1);

 r=gauss(y1);

 abs=(j1-j2);

 if(abs<0){
     abs=0-abs;
 }

 n=(abs)%7;


 n1=(n+r)%7;


 if(n1==0)
 {
    printf("\nThe day is: Sunday");
 }
 else if(n1==1)
 {
    printf("\nThe day is: Monday");
 }
 else if(n1==2)
 {
    printf("\nThe day is: Tuesday");
 }
else if(n1==3)
{
    printf("\nThe day is: Wednesday");
}
else if(n1==4)
{
    printf("\nThe day is: Thursday");
}
else if(n1==5)
{
    printf("\nThe day is: Friday");
}
else if(n1==6)
{
    printf("\nThe day is: Saturday");
}
return 0;

}

Answer 8

Simple Algorithm using Python:

   #Calculate the Days between Two Date

    daysOfMonths = [ 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

    def isLeapYear(year):

        # Pseudo code for this algorithm is found at
        # http://en.wikipedia.org/wiki/Leap_year#Algorithm
        ## if (year is not divisible by 4) then (it is a common Year)
        #else if (year is not divisable by 100) then (ut us a leap year)
        #else if (year is not disible by 400) then (it is a common year)
        #else(it is aleap year)
        return (year % 4 == 0 and year % 100 != 0) or year % 400 == 0

    def Count_Days(year1, month1, day1):
        if month1 ==2:
            if isLeapYear(year1):
                if day1 < daysOfMonths[month1-1]+1:
                    return year1, month1, day1+1
                else:
                    if month1 ==12:
                        return year1+1,1,1
                    else:
                        return year1, month1 +1 , 1
            else: 
                if day1 < daysOfMonths[month1-1]:
                    return year1, month1, day1+1
                else:
                    if month1 ==12:
                        return year1+1,1,1
                    else:
                        return year1, month1 +1 , 1
        else:
            if day1 < daysOfMonths[month1-1]:
                 return year1, month1, day1+1
            else:
                if month1 ==12:
                    return year1+1,1,1
                else:
                        return year1, month1 +1 , 1


    def daysBetweenDates(y1, m1, d1, y2, m2, d2,end_day):

        if y1 > y2:
            m1,m2 = m2,m1
            y1,y2 = y2,y1
            d1,d2 = d2,d1
        days=0
        while(not(m1==m2 and y1==y2 and d1==d2)):
            y1,m1,d1 = Count_Days(y1,m1,d1)
            days+=1
        if end_day:
            days+=1
        return days


    # Test Case

    def test():
        test_cases = [((2012,1,1,2012,2,28,False), 58), 
                      ((2012,1,1,2012,3,1,False), 60),
                      ((2011,6,30,2012,6,30,False), 366),
                      ((2011,1,1,2012,8,8,False), 585 ),
                      ((1994,5,15,2019,8,31,False), 9239),
                      ((1999,3,24,2018,2,4,False), 6892),
                      ((1999,6,24,2018,8,4,False),6981),
                      ((1995,5,24,2018,12,15,False),8606),
                      ((1994,8,24,2019,12,15,True),9245),
                      ((2019,12,15,1994,8,24,True),9245),
                      ((2019,5,15,1994,10,24,True),8970),
                      ((1994,11,24,2019,8,15,True),9031)]

        for (args, answer) in test_cases:
            result = daysBetweenDates(*args)
            if result != answer:
                print "Test with data:", args, "failed"
            else:
                print "Test case passed!"
    test()