Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++: Converting Julian dates to Gregorian

I need to write a function that converts a Julian dates (Year, Day of Year, Hour of Day and Minutes) into a standard form (Year, Month, Day of Month, Hour of Day and Minutes) and express it as a string. I figure there's got to be someone who's already written a library or component which can do the conversion from Day Of Year to Month and Day of Month. I've looked at several well-known datetime libraries:

  • ctime - Specifically using a tm struct and mktime(tm *timeptr) as this generally sets the values of the tm struct to the appropriate places except that "The original values of the members tm_wday and tm_yday of timeptr are ignored..." which doesn't help.
  • Boost::DateTime - Gregorian is constructed date(greg_year, greg_month, greg_day) which doesn't help. However, they do have a date_from_tm(tm datetm) but "The fields: tm_wday , tm_yday , tm_hour, tm_min, tm_sec, and tm_isdst are ignored." Again, no help.
  • COleDateTime - This project contains COM so why not? The COleDateTime constructor COleDateTime( int nYear, int nMonth, int nDay, int nHour, int nMin, int nSec ) doesn't help. And I don't see any other conversion functions to go with it.

As you can see, these all need Month and Day of Month which is exactly what I'm trying to avoid in the first place. I must be either missing something or haven't looked in the right places (not perfect, as much as I try.)

Anyone can help? I'd prefer to avoid writing my own as there's almost always bound to be some gotcha I miss.

like image 309
wheaties Avatar asked Apr 14 '10 14:04

wheaties


1 Answers

I stumbled across this old question, and thought I might be able to add some new information to it. The single existing answer as I write this by Thomas Pornin is a good answer, and I've upvoted it. However I've taken it as a challenge to better it. What if we could produce the same answer twice as fast? Maybe even faster?

To test this effort, I've wrapped Thomas' answer up in a function:

#include <tuple>

std::tuple<int, int, int>
ymd_from_ydoy1(int year, int day_of_year)
{
    static const int month_len[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

    int leap = (year % 4 == 0) && (year % 100 != 0 || year % 400 == 0);
    int day_of_month = day_of_year;
    int month;
    for (month = 0; month < 12; month ++) {
        int mlen = month_len[month];
        if (leap && month == 1)
            mlen ++;
        if (day_of_month <= mlen)
            break;
        day_of_month -= mlen;
    }
    return {year, month, day_of_month};
}

And my attempt to better it is based off of:

chrono-compatible Low-Level Date Algorithms

The above article does not address this situation directly. However it does go into detailed descriptions of the algorithms involved with date manipulations, and even includes a "day of year" concept, though that concept is different than what is specified in this question:

In this question "day of year" is a 1-based count with Jan 01 being the start of the year (Jan 1 == day 1). chrono-compatible Low-Level Date Algorithms has a similar "day of year" concept in the algorithm civil_from_days but it is days past Mar 01 (Mar 1 == day 0).

My thought is that I could pick bits and pieces from civil_from_days and create a new ymd_from_ydoy which did not need to iterate over the 12 months to find the desired result. Here is what I came up with:

std::tuple<int, int, int>
ymd_from_ydoy2(int year, int day_of_year)
{
    int leap = (year % 4 == 0) && (year % 100 != 0 || year % 400 == 0);
    if (day_of_year < 60 + leap)
        return {year, day_of_year/32, day_of_year - (day_of_year/32)*31};
    day_of_year -= 60 + leap;
    int mp = (5*day_of_year + 2)/153;
    int day_of_month = day_of_year - (153*mp+2)/5 + 1;
    return {year, mp + 2, day_of_month};
}

There are still branches, but fewer of them. To test both the correctness and performance of this alternative I wrote the following:

#include <iostream>
#include <chrono>
#include <cassert>

template <class Int>
constexpr
bool
is_leap(Int y) noexcept
{
    return  y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}

constexpr
unsigned
last_day_of_month_common_year(unsigned m) noexcept
{
    constexpr unsigned char a[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    return a[m-1];
}

template <class Int>
constexpr
unsigned
last_day_of_month(Int y, unsigned m) noexcept
{
    return m != 2 || !is_leap(y) ? last_day_of_month_common_year(m) : 29u;
}
int
main()
{
    using namespace std;
    using namespace std::chrono;
    typedef duration<long long, pico> picoseconds;
    picoseconds ps1{0};
    picoseconds ps2{0};
    int count = 0;
    const int ymax = 1000000;
    for (int y = -ymax; y <= ymax; ++y)
    {
        bool leap = is_leap(y);
        for (int doy = 1; doy <= 365 + leap; ++doy, ++count)
        {
            auto d1 = ymd_from_ydoy1(y, doy);
            auto d2 = ymd_from_ydoy2(y, doy);
            assert(d1 == d2);
        }
    }
    auto t0 = high_resolution_clock::now();
    for (int y = -ymax; y <= ymax; ++y)
    {
        bool leap = is_leap(y);
        for (int doy = 1; doy <= 365 + leap; ++doy)
        {
            auto d1 = ymd_from_ydoy1(y, doy);
            auto d2 = ymd_from_ydoy1(y, doy);
            assert(d1 == d2);
        }
    }
    auto t1 = high_resolution_clock::now();
    for (int y = -ymax; y <= ymax; ++y)
    {
        bool leap = is_leap(y);
        for (int doy = 1; doy <= 365 + leap; ++doy)
        {
            auto d1 = ymd_from_ydoy2(y, doy);
            auto d2 = ymd_from_ydoy2(y, doy);
            assert(d1 == d2);
        }
    }
    auto t2 = high_resolution_clock::now();
    ps1 = picoseconds(t1-t0)/(count*2);
    ps2 = picoseconds(t2-t1)/(count*2);
    cout << ps1.count() << "ps\n";
    cout << ps2.count() << "ps\n";
}

There are three loops in this test:

  1. Test that the two algorithms produce the same results over a range of +/- a million years.
  2. Time the first algorithm.
  3. Time the second algorithm.

It turns out that both algorithms are wicked fast ... a handful of nanoseconds on the iMac Core i5 I'm testing on. And thus the introduction of picoseconds to get a first-order estimate of fractional nanoseconds.

    typedef duration<long long, pico> picoseconds;

I'd like to point out two things:

  1. How cool is it that we are starting to use picoseconds as a unit of measurement?
  2. How cool is it that std::chrono makes it so easy to interoperate with picoseconds?

For me this test prints out (approximately):

8660ps
2631ps

Indicating that ymd_from_ydoy2 is approximately 3.3 times faster than ymd_from_ydoy1.

Hope this helps. Important things to get from this answer:

  1. chrono-compatible Low-Level Date Algorithms has useful and efficient algorithms for date manipulation. They can be useful even if you have to pick the algorithms apart and reassemble them, as in this example. The explanations of the algorithms are there to enable you to pick them apart and reapply them in examples such as this.
  2. <chrono> can be very flexible in measuring very fast functions. Three times faster than very fast is still a good win.
like image 145
Howard Hinnant Avatar answered Oct 05 '22 01:10

Howard Hinnant