Efficient algorithm for converting number of days to years (including leap years)

Question

The problem

I am writing a class for holding dates in c++, and I found the following problem:

I have a number of days N since a reference date (in my case that would be Jan 1, 0001 AD), including the leap days that passed since the reference day. How can I convert this number to a year Y, month M and day D efficiently?

I would like to do this as efficiently as possible, so the best implementation would obviously have O(1) complexity.

The next sections will explain some of the things I already learned.

Leap years

To determine if a year is leap or not, there are a few rules:

1. Years which are divisible by 4 are leap
2. Exception to rule 1: years that are divisible with 100 are not leap
3. Exception to rule 2: years that are divisible with 400 are leap

This would translate in code like this:

bool IsLeapYear(int year)
{
    // Corrected after Henrick's suggestion
    if (year % 400 == 0) return true;
    if ((year % 4 == 0) && (year % 100 != 0)) return true;
    return false;
}

An efficient method to calculate how many years are leap before an year would be:

int LeapDaysBefore(int year)
{
    // Years divisible by 4, not divisible by 100, but divisible by 400
    return ((year-1)/4 - (year-1)/100 + (year-1)/400);
}

Calculating the month

Once I find the year, I can calculate how many days there are until the current year, and I can subtract this number from N. This will give me the day of the year.

Keeping a table with the day number on which every month starts, we can easily calculate the month. I also created a function which will add 1 if the year is leap, and the month is greater or equal to 2.

// What day each month starts on (counting from 0)
int MonthDaySt[] = { 0, 31, 59, 90, 120, 151, 181, 212, 
    243, 273, 304, 334, 365 };

int MonthDayStart(int month, bool leap)
{
   if (leap && month >= 2) return MonthDaySt[month]+1;
   return MonthDaySt[month];
}

My idea

My algorithm is pretty complicated, and it looks like this:

void GetDate(int N, int &Y, int &M, int &D)
{
    int year_days;

    // Approximate the year, this will give an year greater or equal
    // to what year we are looking for.
    Y = N / 365 + 1;

    // Find the actual year, counting leap days
    do {
        Y--;

        // Calculate the actual number of days until the
        // approximate year
        year_days = Y * 365 + LeapDaysBefore(year);

    } while (year_days > N);

    // Add 1, because we start from year 1 AD (not 0)
    Y++;

    // Calculate month
    uint64_t diff = N - year_days; // Will give us the day of the year
    bool leap = IsLeapYear(Y);  // Is current year leap?

    // Use table to find month
    M = 0;
    while (MonthDayStart(M, leap) <= diff && M <= 12)
        M++;

    // Calculate day
    D = diff - MonthDayStart(M - 1, leap) + 1;
}

The function may have a few bugs (for example, it didn't work when N was 0).

Other notes

I hope that my algorithm is still correct, because I made some changes from the original for this question. If I missed something, or something was wrong, let me know to modify it. And sorry for the long question.

Answer 1

To use the punchline of an old joke, "I wouldn't start from here".

You'll want to read up about various changes to calendaring before "modern" times, for example, what happened in 1752