El problema

Estoy escribiendo una clase para celebrar fechas en c ++, y encontré el siguiente problema:

Tengo un numero de diasN desde una fecha de referencia (en mi caso, sería el 1 de enero de 0001 AD), incluidos los días bisiestos transcurridos desde el día de referencia.¿Cómo puedo convertir este número a un año?YmesM y diaD eficientemente?

Me gustaría hacerlo de la manera más eficiente posible, por lo que la mejor implementación obviamente tendría una complejidad O (1).

Las siguientes secciones explicarán algunas de las cosas que ya aprendí.

Años bisiestos

Para determinar si un año es bisiesto o no, hay algunas reglas:

Los años divisibles por 4 son salto.Excepción a la regla 1: los años que son divisibles con 100 no saltanExcepción a la regla 2: los años que son divisibles con 400 son salto

Esto se traduciría en un código como este:

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

Un método eficiente para calcular cuántos años se saltan antes de un año sería:

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

Calculando el mes

Una vez que encuentre el año, puedo calcular cuántos días hay hasta el año actual, y puedo restar este número de N. Esto me dará el día del año.

Manteniendo una tabla con el número del día en que comienza cada mes, podemos calcular fácilmente el mes. También creé una función que agregará 1 si el año es un salto, y el mes es mayor o igual a 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];
}

Mi idea

Mi algoritmo es bastante complicado, y se ve así:

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

La función puede tener algunos errores (por ejemplo, no funcionó cuando N era 0).

Otras notas

Espero que mi algoritmo siga siendo correcto, porque hice algunos cambios con respecto al original para esta pregunta. Si perdí algo, o si algo estuvo mal, hágamelo saber para modificarlo. Y lo siento por la larga pregunta.