Howard Hinnant
2021-09-01

chrono-Compatible Low-Level Date Algorithms

Contents

Introduction

The purpose of this paper is not to propose a date class. For an example date library based on these algorithms see date v2.

This paper derives and documents key algorithms that enable one to write their own date class. The purpose of this paper is to allow everyone to easily write their own date class, using algorithms that are well documented, and easily modified to meet individual needs. The algorithms presented are efficient. They require no external tables. They do not require C++11 or C++1y features, though if C++11 is available, the algorithms should be noexcept, and if C++1y is available, they can trivially be made constexpr.

This paper does not document a library. It is a how-to manual for writing the algorithm part of your own date class. The syntax and some of the language features come from C++11 and even C++1y. However the algorithms can be ported to any language.

The algorithms are interoperable with every known implementation of std::chrono::system_clock, though that interoperability depends on an unspecified property of the system_clock: its epoch. Example code will be shown how these algorithms can take advantage of the common (but unspecified) system_clock epoch.

The algorithms implement a proleptic Gregorian calendar. That is, the rules which adopted the Julian calendar in 1582 in Rome are applied both backwards and forwards in time. This includes a year 0, and then negative years before that, all following the rules for the Gregorian calendar. From hence forth this paper will refer to this as the civil calendar. The accuracy of the algorithms under these rules is exact, until overflow occurs. Using 32 bit arithmetic, overflow occurs approximately at +/- 5.8 million years. Using 64 bit arithmetic overflow occurs far beyond +/- the age of the universe. The intent is to make range checking superfluous.

The algorithms implement no validity checking. The intent is that any desired validity checking on the triple year/month/day can be added on top of these algorithms if and where desired.

Ten low-level algorithms are presented:

  1. Convert from a year/month/day triple to a serial day number.

    template <class Int>
    constexpr
    Int
    days_from_civil(Int y, unsigned m, unsigned d) noexcept;
    
  2. Convert from a serial day number to a year/month/day triple.

    template <class Int>
    constexpr
    std::tuple<Int, unsigned, unsigned>
    civil_from_days(Int z) noexcept;
    
  3. Determine if a year is a leap year.

    template <class Int>
    constexpr
    bool
    is_leap(Int y) noexcept;
    
  4. Given the month, return the last day of the month of a common year.

    constexpr
    unsigned
    last_day_of_month_common_year(unsigned m) noexcept;
    
  5. Given the month, return the last day of the month of a leap year.

    constexpr
    unsigned
    last_day_of_month_leap_year(unsigned m) noexcept;
    
  6. Given the year and month, return the last day of the month.

    template <class Int>
    constexpr
    unsigned
    last_day_of_month(Int y, unsigned m) noexcept;
    
  7. Convert from a serial day number to a day of the week.

    template <class Int>
    constexpr
    unsigned
    weekday_from_days(Int z) noexcept;
    
  8. Subtract one weekday from another (e.g. Sun - Sat is 1, and Sat - Sun is 6).

    constexpr
    unsigned
    weekday_difference(unsigned x, unsigned y) noexcept;
    
  9. Get the weekday following a weekday (e.g. Mon follows Sun).

    constexpr
    unsigned
    next_weekday(unsigned wd) noexcept;
    
  10. Get the weekday prior to a weekday (e.g. Sat comes before Sun).

    constexpr
    unsigned
    prev_weekday(unsigned wd) noexcept;
    

The algorithms are templated on year number type and serial day number type so that you can easily vary the range (use int, long long, big_num, or whatever). For those fields that are known to be unsigned and small (e.g. month) unsigned is used. Feel free to substitute any type you like. The use of unsigned is just to demonstrate that this particular field is constrained in the algorithm to always remain within a non-negative range.

Building upon these low-level algorithms, higher-level algorithms can easily be written, and this paper shows several examples of such higher-level algorithms.

days_from_civil

First the algorithm, and then the explanation:

// Returns number of days since civil 1970-01-01.  Negative values indicate
//    days prior to 1970-01-01.
// Preconditions:  y-m-d represents a date in the civil (Gregorian) calendar
//                 m is in [1, 12]
//                 d is in [1, last_day_of_month(y, m)]
//                 y is "approximately" in
//                   [numeric_limits<Int>::min()/366, numeric_limits<Int>::max()/366]
//                 Exact range of validity is:
//                 [civil_from_days(numeric_limits<Int>::min()),
//                  civil_from_days(numeric_limits<Int>::max()-719468)]
template <class Int>
constexpr
Int
days_from_civil(Int y, unsigned m, unsigned d) noexcept
{
    static_assert(std::numeric_limits<unsigned>::digits >= 18,
             "This algorithm has not been ported to a 16 bit unsigned integer");
    static_assert(std::numeric_limits<Int>::digits >= 20,
             "This algorithm has not been ported to a 16 bit signed integer");
    y -= m <= 2;
    const Int era = (y >= 0 ? y : y-399) / 400;
    const unsigned yoe = static_cast<unsigned>(y - era * 400);      // [0, 399]
    const unsigned doy = (153*(m > 2 ? m-3 : m+9) + 2)/5 + d-1;  // [0, 365]
    const unsigned doe = yoe * 365 + yoe/4 - yoe/100 + doy;         // [0, 146096]
    return era * 146097 + static_cast<Int>(doe) - 719468;
}

As explained in the introduction, the type of year is templated so that you can easily set your own range based on your own needs. And if you dislike the use of unsigned for month and day, please change them to whatever suits you. Doing so will not impact the correctness of the algorithm. And if you're not compiling under C++1y constexpr rules, you will need to remove (or comment out) the constexpr. If you are compiling in C++98/03 you can substitute throw() for noexcept, or remove the exception specification entirely.

The first two algorithms also do some static checking on the range of Int and unsigned. It is possible to port these algorithms to a 16 bit machine. It just involves being more careful with casts, and the use of integral types that are known to be at least 32 bits in a few key places. For the purposes of presentation, and because it has been a long time since I've personally come in contact with a 16 bit machine, I've chosen to assume the machine is at least 32 bits, but documented that assumption with static_assert. If you are interested in porting these algorithms to a 16 bit machine, then you need to pay attention to the lines which are commented with the ranges of the variable being computed.

These algorithms internally assume that March 1 is the first day of the year. This is convenient because it puts the leap day, Feb. 29 as the last day of the year, or actually the preceding year. That is, Feb. 15, 2000, is considered by this algorithm to be the 15th day of the last month of the year 1999. Don't worry, this complication is securely encapsulated in this and the other algorithms. This detail is only important for understanding how the algorithm works, and is not exposed to the client of these algorithms.

Additionally the first two algorithms make use of the concept of an era. This concept is not exposed to the client, but is very handy in creating an algorithm that is valid over extremely large ranges. In these algorithms, an era is a 400 year period. As it turns out, the civil calendar exactly repeats itself every 400 years. And so these algorithms will first compute the era of a year/month/day triple, or the era of a serial date, and then factor the era out of the computation. The rest of the computation centers on concepts such as:

The wonderful thing about this approach is that you only need to debug a single era (146097 days), and the transformation to and from eras, and then you have all time debugged. Below is a table of eras mapped to civil dates. Note that in this table the year number is the civil year number for Jan. and Feb., not the internal year number used within the algorithm.

erastart dateend date
-2-0800-03-01-0400-02-29
-1-0400-03-010000-02-29
00000-03-010400-02-29
10400-03-010800-02-29
20800-03-011200-02-29
31200-03-011600-02-29
41600-03-012000-02-29
52000-03-012400-02-29

So the first thing the days_from_civil algorithm does is transform the year number to the internal one for Jan. and Feb. And then the era is computed. For non-negative years, the era is simply y/400. But for negative years one has to be careful that years [-400, -1] map to era -1. By using floored or Euclidean division, negative years are correctly accounted for. Also note that in C++98/03 it is implementation defined whether integral division is implemented as truncated, floored or Euclidean. Only C++11 specifies truncated division. So if you are using a C++98/03 compiler that implements floored or Euclidean division you can actually simplify the computation of the era to simply y / 400. Again, once the algorithm takes negative years into account in this one place, everything else can be done with unsigned arithmetic: everything else is non-negative.

Once the era is known (this is generally a signed number of unknown range), the year-of-era can easily be computed by subtracting off the year from era * 400. This is the same as the modulo operation, but assuming floored or Euclidean division, as opposed to the truncated division/modulo operation that C++11 specifies. This will result in an unsigned number in the range of [0, 399], whether the era is negative or non-negative.

At the same time as the yoe computation is happening, we can also compute the day-of-year (doy) which is an unsigned number in the range of [0, 364] for a non-leap year, and for leap years has a range of [0, 365]. A value of 0 corresponds to Mar 1, and a value of 364 corresponds to Feb. 28 of the following (civil) year.

The doy computation is quite unintuitive and deserves an in-depth explanation.

Computing day-of-year from month and day-of-month

We need a formula that maps Mar. 1 to 0, Mar. 2 to 1, etc. up to Feb. 29 of the following year to 365. This computation can be broken down into several parts:

Let's start with the second bullet: Map a month number m' in the range [0, 11] (Mar. - Feb.) into a range such that the first day of the month m' is x number of days after Mar. 1.

This can be exactly expressed as a table:

monthm'days after m'-01
Mar00
Apr131
May261
Jun392
Jul4122
Aug5153
Sep6184
Oct7214
Nov8245
Dec9275
Jan10306
Feb11337

However we would like to translate this table into a linear polynomial.

a1 m' + a0

Note that a beautiful property of this table is that it does not depend upon whether or not the current year is a leap year. The leap day is either applied to the end of the last month in the table or not, and can not impact any rows in the table, not even the last row.

The slope of this straight line can be easily computed by 337/11 == 30.63636363636364. However integral round off complicates this formula, and the y-intercept of this linear equation can be manipulated to give the desired results. Assume we have the following function but with known constants for a1 and a0:

int
doy_from_month(int mp)
{
    return a1 * mp + a0;
}

With this we can easily write a comprehensive unit test for doy_from_month:

#include <cassert>

// Returns day of year for 1st day of month mp, mp == 0 is Mar, mp == 11 is Feb.
int
doy_from_month(int mp)
{
    return a1 * mp + a0;
}

int
main()
{
    int a[12] = {0, 31, 61, 92, 122, 153, 184, 214, 245, 275, 306, 337};
    for (int mp = 0; mp < 12; ++mp)
        assert(doy_from_month(mp) == a[mp]);
}

If we make a1 == 30 or a1 == 31, there is no value for a0 we can assign to make this unit test pass. However we can manipulate the y-intercept (a0) in a very fine manner if we express the equation as:

return (b1 * mp + b0) / a0;

The first best guess is to make b1 == 337 and a0 == 11. However when doing so there is no value of b0 that will pass the unit test. However if we make b1 == 306 and a0 == 10 (i.e. 306/10 ≈ 30.63636363636364) then there are actually two formulations that pass all unit tests:

I first arbitrarily selected the second. However note that the first can be simplified down to:

For reasons I do not fully understand, this latter formula tests slightly faster (about 2%) than the others.

Now mp represents m' or the month number that starts with Mar == 0. We also need to map the civil month number (Mar == 3) (m) to our internal month number (mp). This can be done by adding 9 to m, and taking the modulus of the result by 12:

mp = (m + 9) % 12;

This formula results in the following relationship:

m123456789101112
mp10110123456789

After some performance testing I discovered that replacing the % with a branch was actually slightly faster, at least on the Core i5 I'm testing on:

mp = m + (m > 2 ? -3 : 9);

Putting this together we now have a formula for taking a civil month number and computing the number of days between the first of that month, and Mar 1:

(153*(m + (m > 2 ? -3 : 9)) + 2)/5

Now to get the day-of-year from the double month/day one simply adds the day-of-the-month, minus 1:

const unsigned doy = (153*(m + (m > 2 ? -3 : 9)) + 2)/5 + d - 1;

One can spot-check this formula in a few places:

m322
d12928
doy0365364

Now given year-of-era (yoe) and day-of-year (doy), we can easily calculate the day-of-era (doe). This is simply 365 days for every year, plus another day for every 4 years, minus a day for every hundred years, plus the day-of-year:

const unsigned doe = yoe * 365 + yoe / 4 - yoe / 100 + doy;

Those familiar with this particular computation might question the lack of the term:

+ yoe / 400

in the above formula. It would actually be correct to put it in. However note that yoe is always in the range [0, 399], and so the contribution of this term is always 0.

The final computation in days_from_civil is computing the serial date from the era and from the day-of-era (doe). This is simply:

return era * 146097 + static_cast<Int>(doe)

which gives the number of days, before, or after, 0000-03-01. However note that I've also subtracted 719468 from this final computation in the actual days_from_civil code. This is a shift which aligns this algorithm with all known implementations of std::chrono::system_clock. It makes the serial date 0 be equivalent to 1970-01-01 instead of 0000-03-01.

All known implementations of std::chrono::system_clock count seconds from 1970-01-01, neglecting leap seconds. This is known as unix time. Implementations are not required by the standard to use this measure. But it can be handy to take advantage of it.

civil_from_days

Now that we can use days_from_civil to convert a year/month/day triple into a serial date, it is really handy to be able to go the other way: convert a serial date into a year/month/day triple. And this is exactly what civil_from_days does. First the algorithm, and then the explanation:

// Returns year/month/day triple in civil calendar
// Preconditions:  z is number of days since 1970-01-01 and is in the range:
//                   [numeric_limits<Int>::min(), numeric_limits<Int>::max()-719468].
template <class Int>
constexpr
std::tuple<Int, unsigned, unsigned>
civil_from_days(Int z) noexcept
{
    static_assert(std::numeric_limits<unsigned>::digits >= 18,
             "This algorithm has not been ported to a 16 bit unsigned integer");
    static_assert(std::numeric_limits<Int>::digits >= 20,
             "This algorithm has not been ported to a 16 bit signed integer");
    z += 719468;
    const Int era = (z >= 0 ? z : z - 146096) / 146097;
    const unsigned doe = static_cast<unsigned>(z - era * 146097);          // [0, 146096]
    const unsigned yoe = (doe - doe/1460 + doe/36524 - doe/146096) / 365;  // [0, 399]
    const Int y = static_cast<Int>(yoe) + era * 400;
    const unsigned doy = doe - (365*yoe + yoe/4 - yoe/100);                // [0, 365]
    const unsigned mp = (5*doy + 2)/153;                                   // [0, 11]
    const unsigned d = doy - (153*mp+2)/5 + 1;                             // [1, 31]
    const unsigned m = mp < 10 ? mp+3 : mp-9;                            // [1, 12]
    return std::tuple<Int, unsigned, unsigned>(y + (m <= 2), m, d);
}

Many of the same concepts used in developing days_from_civil are reused here. If you've skipped that section because you're just interested in this algorithm, you may want to go back and read it anyway, as the concepts will not be re-explained here.

The first step in the computation is to shift the epoch from 1970-01-01 to 0000-03-01:

z += 719468;

Now we can compute the era from the serial date by simply dividing by the number of days in an era (146097). Again floored or Euclidean division must be used to correctly handle negative days.

const Int era = (z >= 0 ? z : z - 146096) / 146097;

The day-of-era (doe) can then be found by subtracting the era number times the number of days per era, from the serial date. This is the same as the modulo operation, but assuming floored or Euclidean division. This always results in a doe in the range [0, 146096].

const unsigned doe = static_cast<unsigned>(z - era * 146097);

From the day-of-era (doe), the year-of-era (yoe, range [0, 399]) can be computed. This formula can be derived one piece at a time. To start, the yoe can be approximated by simply dividing doe by 365:

const unsigned yoe = doe / 365;

This is actually correct for doe in the range [0, 1459], yielding a yoe in the range of [0, 3]. However 1460 / 365 is 4. But there are 1461 days in the first 4 years of an era (4*365+1), which are labeled as years 0 thru 3. So we must alter the formula so that 1460 (the last day of year 3) results in 3, but 1461 (the first day of year 4) results in 4:

const unsigned yoe = (doe - doe / 1460) / 365;

Now the formula is accurate for doe in the range [0, 36523], yielding a yoe in the range of [0, 99]. but the first hundred years of an era has 36524 days in it (365 * 100 + 100/4 - 1 == 36524). 36524 (the first day of year 100) should yield 100, but instead yields 99 in the above formula which is incorrect. To correct this the formula can be augmented again:

const unsigned yoe = (doe - doe/1460 + doe/36524) / 365;

Now inputing 36524 yields 100. And indeed the formula is now correct up until the very last day in an era, day number 146096. On this day, the last day of the era, and the last day of year 399, the above formula yields 400 instead of 399. The formula can be made exact for every day in the era with one more adjustment:

const unsigned yoe = (doe - doe/1460 + doe/36524 - doe/146096) / 365;

Given year-of-era, and era, one can now compute the year number:

const Int y = static_cast<Int>(yoe) + era * 400;

Note though that this year number is still in terms of a year that begins on Mar. 1, not Jan. 1.

Also the day-of-year, again with the year beginning on Mar. 1, can be computed from the day-of-era and year-of-era. One simply subtracts from the day-of-era the days that have occurred in all prior years of this era:

const unsigned doy = doe - (365 * yoe + yoe / 4 - yoe / 100);

Again note the absence of the correct term + yoe / 400 because the contribution of this term is always zero since 399 is the upper range of yoe.

Computing month from day-of-year

When developing days_from_civil we had to develop a linear equation to compute the day-of-year from the first day of month m' where m' is in the range [0, 11] representing [Mar, Feb].

int
doy_from_month(int mp)
{
    return (153 * mp + 2) / 5;
}

Now we need the inverse of this formula: Given day-of-year, we need to find the month number. If integral arithmetic was exact, the derivation would be straight forward algebra and we would get:

int
month_from_doy(int doy)
{
    return (5 * doy - 2) / 153;
}

Before accepting this as the correct answer, it is wise to build a unit test for this function. The one developed for doy_from_month can easily be augmented to test both of these functions at the same time:

int
main()
{
    int a[12][2] =
    {
        {0, 30},
        {31, 60},
        {61, 91},
        {92, 121},
        {122, 152},
        {153, 183},
        {184, 213},
        {214, 244},
        {245, 274},
        {275, 305},
        {306, 336},
        {337, 365}
    };

    for (int mp = 0; mp < 12; ++mp)
    {
        assert(doy_from_month(mp) == a[mp][0]);
        assert(month_from_doy(a[mp][0]) == mp);
        assert(month_from_doy(a[mp][1]) == mp);
    }
}

The pair of numbers in a are the first and last numbers of the day-of-year for each month in [0, 11]. We already have a function doy_from_month(mp) which computes the starting day-of-year for each month, and tested by the first assert in the program. And now two more asserts are added to test that given both the first and last day of each month, month_from_doy can transform that day-of-year into the correct month number mp.

Running this test on the month_from_doy given above, we see that our first attempt at derivation using simple algebra is incorrect. However it is close. The slope of the linear equation is correct. We just need to experiment with the y-intercept to discover the correct formula. There exist three which will pass the above unit test:

I've chosen the second for use in civil_from_days because it appears to have a slight performance advantage:

const unsigned mp = (5*doy + 2)/153;

From day-of-year and month-of-year we can now easily compute day-of-month by reusing the doy_from_month formula developed for days_from_civil. One just subtracts from the day-of-year all of the days that occurred in the previous months of this year. One is added to the result since the day count is 1-based instead of 0-based.

const unsigned d = doy - (153*mp+2)/5 + 1;

Next we need to transform the month number from the [0, 11] / [Mar, Feb] system to the civil system: [1, 12]. I've found that branching is faster than using %:

const unsigned m = mp + (mp < 10 ? 3 : -9);

Now the only thing left to do is to transform the year number from the internal format (begins in Mar.) to the civil format (begins in Jan.). This is done simply by adding 1 to the year if the month is Jan. or Feb. I've returned this result in a std::tuple for no good reason at all. You should return the triple year/month/day in whatever format is convenient for you.

return std::tuple<Int, unsigned, unsigned>(y + (m <= 2), m, d);

is_leap

Even though the conversions between year/month/day and the serial date do not need to compute whether or not a year is a leap year, it is still very handy to know whether or not a year is a leap year. This function answers that question. First the algorithm, and then the explanation:

// Returns: true if y is a leap year in the civil calendar, else false
template <class Int>
constexpr
bool
is_leap(Int y) noexcept
{
    return  y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}

The formula is designed to return an answer as quickly as possible for a random year. 75.75% of all years are not leap years. We can find 99% of the non-leap years with only one test: y % 4 != 0. If the year is not evenly divisible by 4, then it is definitely not a leap year, and short circuiting will cause a return at this point without evaluating the rest of the formula.

Of the 25% of the years that are evenly divisibly by 4, these might be a leap year. 96% of these 25% are and can be dispatched with a second test: y %100 != 0. If the year is evenly divisible by 4 and not evenly divisible by 100, then it is definitely a leap year, and short circuiting will return here for those years. The remaining 4% of the 25% (or 1% of the total number of years) require one more test. These are years that are known to be divisible by 100. If they are also evenly divisible by 400, then they are a leap year, else they are not.

In summary, given a uniformly distributed random year:

This percentage of the timethis will get executed
75%y % 4 == 0, typically optimized to !(y & 0x3)
24%(y % 4 == 0) && (y % 100 != 0)
1%(y % 4 == 0) && (y % 100 != 0) && (y % 400 == 0)

last_day_of_month_common_year

Given a month, and with the assumption that this is a month in a common (non-leap) year, return the number of days in the month, or equivalently the day of the last day of the month. First the algorithm, and then the explanation:

// Preconditions: m is in [1, 12]
// Returns: The number of days in the month m of common year
// The result is always in the range [28, 31].
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];
}

If you know you have a common year, this is the fastest mapping I know of to translate the month into the last day of the month. unsigned char is used as the table type as both a speed and size optimization.

last_day_of_month_leap_year

Given a month, and with the assumption that this is a month in a leap year, return the number of days in the month, or equivalently the day of the last day of the month. First the algorithm, and then the explanation:

// Preconditions: m is in [1, 12]
// Returns: The number of days in the month m of leap year
// The result is always in the range [29, 31].
constexpr
unsigned
last_day_of_month_leap_year(unsigned m) noexcept
{
    constexpr unsigned char a[] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    return a[m-1];
}

If you know you have a leap year, this is the fastest mapping I know of to translate the month into the last day of the month. unsigned char is used as the table type as both a speed and size optimization.

last_day_of_month

Given a year and month, often one needs to quickly find out how many days are in the month. Or equivalently, what is the last day of the month. First the algorithm, and then the explanation:

// Preconditions: m is in [1, 12]
// Returns: The number of days in the month m of year y
// The result is always in the range [28, 31].
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;
}

The algorithm looks so simple that it hardly needs any explanation. However I'm going to bore you with one anyway. An early reviewer noted that sometimes one already has the information that y is (or not) a leap year, and so taking advantage of that information for performance reasons would be nice, instead of recomputing it within last_day_of_month. I found this argument compelling, and set off to measure how much time I could save.

It turns out that if one simply replaces Int y with bool is_leap in the above algorithm, the savings is actually quite tiny. So tiny it is hard to measure. I was surprised by this result, however the basic concept that the reviewer had: "avoid is_leap(y) when possible," is sound. And this was the genesis of last_day_of_month_common_year and last_day_of_month_leap_year.

First an analysis of the current implementation of last_day_of_month:

Given a uniformly distributed y, and a uniformly distributed m in the range [1, 12], the following table gives the odds of exactly what gets executed in a call to last_day_of_month(y, m):

This percentage of the timethis will get executed
91⅔%m != 2
6¼%(m != 2) && (y % 4 == 0)
2%(m != 2) && (y % 4 == 0) && (y % 100 != 0)
1/12%(m != 2) && (y % 4 == 0) && (y % 100 != 0) && (y % 400 == 0)

In English, over 91% of the time, neither the function is_leap(y), nor the bool is_leap is even touched. Additionally in over 6% of the cases, the only additional code is a % 4 which is typically optimized to a & 0x3. Bitwise-ands are so fast they are practically free. So we're up to 9711/12% of the time actually computing is_leap(y) is just as fast or very nearly just as fast. In 2% of the cases, avoiding the is_leap(y) computation saves a % operation. And in 1/12 of 1% of the cases, avoiding the is_leap(y) computation saves two % operations. Although a % operation is a significant expense, they happen so rarely in this code that this just isn't good enough to justify another signature.

However if one can remove all branches from an entire year's worth of calls to last_day_of_month, then you've got a small but measurable performance optimization. For example if you're looping over all months in a year, then you should be able to compute is_leap(y) exactly once, then branch exactly once, and then get the number of days in each month with no further testing. And this is the reason last_day_of_month_common_year and last_day_of_month_leap_year are introduced.

weekday_from_days

The day-of-the-week is most conveniently computed from the serial date. These formulas use the C and C++ convention that [0, 6] represents [Sun, Sat]. First the algorithm, and then the explanation:

// Returns day of week in civil calendar [0, 6] -> [Sun, Sat]
// Preconditions:  z is number of days since 1970-01-01 and is in the range:
//                   [numeric_limits<Int>::min(), numeric_limits<Int>::max()-4].
template <class Int>
constexpr
unsigned
weekday_from_days(Int z) noexcept
{
    return static_cast<unsigned>(z >= -4 ? (z+4) % 7 : (z+5) % 7 + 6);
}

There are really two formulas, both based on doing % 7. When the lhs argument for the % operator is not negative, then (z+4) % 7 has pleasing results. Recall that z == 0 corresponds to 1970-01-01. It is easily verified that this day was a Thursday. Thus weekday_from_days(0) should yield 4, weekday_from_days(1) should yield 5, and so on. (z+4) % 7 achieves this and it is easy to see will always be correct for all dates after 1970-01-01.

Getting weekdays prior to 1970-01-01 requires a bit more work. But we can start with weekday_from_days(-1) should yield 3 (the day before Thursday is Wednesday). This actually works with (z+4) % 7, but stops working by the time we get to weekday_from_days(-5), which should be 6 (Sat). Instead the formula yields -1. For these and all previous dates, after we % 7, giving a number in the range [-6, 0], we need to add 6 to get the number back into the desired range [0, 6]. And furthermore we need a new offset to ensure that weekday_from_days(-5) == 6. The formula (z+5) % 7 + 6 does the trick.

This is all equivalent to a modulo operation based on floored or Euclidean division. So if your C++98/03 compiler implements floored or Euclidean division (it may or may not), then you can simply return (z+4) % 7. If you are unsure, the unit tests below will detect the error if the code is inconsistent with the compiler's definition of integral division.

weekday_difference

It turns out to be very handy to ask: Given two weekdays, how many days do you have to increment to get from one to the other. This question has been cast in the form of subtraction between two weekdays. First the algorithm, and then the explanation:

// Preconditions: x <= 6 && y <= 6
// Returns: The number of days from the weekday y to the weekday x.
// The result is always in the range [0, 6].
constexpr
unsigned
weekday_difference(unsigned x, unsigned y) noexcept
{
    x -= y;
    return x <= 6 ? x : x + 7;
}

This algorithm views the range [Sun, Sat] ([0, 6]) as a circular range. Once you reach Sat, it is not the end of the range. Instead Sun is the next element in the range. And the cycle repeats. Given that, how many days do you need to add to y to get x?

The algorithm takes advantage of the requirement that unsigned integers shall obey the laws of arithmetic modulo 2n where n is the number of bits in the value representation of that particular size of integer. That is, if x -= y "underflows", it is brought back into range with + 7. Because this is unsigned arithmetic, there is no undefined behavior.

A higher-level library may choose to provide pre-condition checking prior to calling this low-level algorithm.

Here is a complete unit-test for this function:

#include <cassert>

void
test_weekday_difference()
{
    constexpr unsigned a[7][7] =
    {// -    Sun Mon Tue Wed Thu Fri Sat
     /*Sun*/ {0,  6,  5,  4,  3,  2,  1},
     /*Mon*/ {1,  0,  6,  5,  4,  3,  2},
     /*Tue*/ {2,  1,  0,  6,  5,  4,  3},
     /*Wed*/ {3,  2,  1,  0,  6,  5,  4},
     /*Thu*/ {4,  3,  2,  1,  0,  6,  5},
     /*Fri*/ {5,  4,  3,  2,  1,  0,  6},
     /*Sat*/ {6,  5,  4,  3,  2,  1,  0}
    };
    for (unsigned x = 0; x < 7; ++x)
        for (unsigned y = 0; y < 7; ++y)
            assert(weekday_difference(x, y) == a[x][y]);
}

next_weekday

It is convenient to find the next weekday in the circular range [Sun, Sat]. First the algorithm, and then the explanation:

// Preconditions: wd <= 6
// Returns: The weekday following wd
// The result is always in the range [0, 6].
constexpr
unsigned
next_weekday(unsigned wd) noexcept
{
    return wd < 6 ? wd+1 : 0;
}

If wd is not Sat, wd+1 is returned, else Sun is returned.

prev_weekday

It is convenient to find the previous weekday in the circular range [Sun, Sat]. First the algorithm, and then the explanation:

// Preconditions: wd <= 6
// Returns: The weekday prior to wd
// The result is always in the range [0, 6].
inline
constexpr
unsigned
prev_weekday(unsigned wd) noexcept
{
    return wd > 0 ? wd-1 : 6;
}

If wd is not Sun, wd-1 is returned, else Sat is returned.

Yes, but how do you know this all really works?

These functions can and should be tested. Below is a very thorough unit test for 7 of the ten functions:

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

static_assert(days_from_civil(1970, 1, 1) == 0, "1970-01-01 is day 0");
static_assert(civil_from_days(0) == std::make_tuple(1970, 1, 1), "1970-01-01 is day 0");
static_assert(weekday_from_days(days_from_civil(1970, 1, 1)) == 4, "1970-01-01 is a Thursday");

int
main()
{
    int ystart = -1000000;
    int prev_z = days_from_civil(ystart, 1, 1) - 1;
    assert(prev_z < 0);
    int prev_wd = weekday_from_days(prev_z);
    assert(0 <= prev_wd && prev_wd <= 6);
    auto t0 = std::chrono::system_clock::now();
    for (int y = ystart; y <= -ystart; ++y)
    {
        for (unsigned m = 1; m <= 12; ++m)
        {
            unsigned e = last_day_of_month(y, m);
            for (unsigned d = 1; d <= e; ++d)
            {
                int z = days_from_civil(y, m, d);
                assert(prev_z < z);
                assert(z == prev_z+1);
                int yp;
                unsigned mp, dp;
                std::tie(yp, mp, dp) = civil_from_days(z);
                assert(y == yp);
                assert(m == mp);
                assert(d == dp);
                unsigned wd = weekday_from_days(z);
                assert(0 <= wd && wd <= 6);
                assert(wd == next_weekday(prev_wd));
                assert(prev_wd == prev_weekday(wd));
                prev_z = z;
                prev_wd = wd;
            }
        }
    }
    auto t1 = std::chrono::system_clock::now();
    typedef std::chrono::duration<float> sec;
    std::cout << sec(t1-t0).count() << '\n';
    std::cout << days_from_civil(1000000, 12, 31) - days_from_civil(-1000000, 1, 1) << '\n';
}

First some static_asserts are performed to nail down some basics. If your compiler does not support the C++1y constexpr rules, you will need to verify these at run time with assert instead. The static_asserts confirm that 1970-01-01 is day 0, and that this day is a Thursday.

In main() I've chosen to test every day between -1,000,000-01-01 and 1,000,000-12-31. This is a total of 730,485,366 days, spanning a range far greater than the civil calendar is actually valid. So the test is overkill. However one of the goals of these formulas is to not burden the client with the need to range check, or worry about the range of validity of the formulas. All the user really has to worry about is if he really should be using the civil calendar for the Jurassic period (certainly possible when these functions are instantiated with long long).

The test loops over each year, each month of each year, and each day of each month. It computes the serial date from each year/month/day triple and ensures that this is 1 greater than the previous iteration. It then converts the serial date back to a year/month/day triple and ensures that this is the same triple it started this iteration with. And finally the test ensures that the weekday for this date is one day later in the week than was the weekday for the previous iteration.

I've also timed the entire test. On my machine (2.8 GHz Intel Core i5 iMac) this executes at -O3 in about 17.1 seconds which means it is testing each date in about 23.4 ns. These functions are not slow.

What can I do with that chrono compatibility?

Here is a short program that prints out the current local date and time without going through the C interface:

#include <iomanip>
#include <iostream>
#include <chrono>

int
main()
{
    using namespace std;
    using namespace std::chrono;
    typedef duration<int, ratio_multiply<hours::period, ratio<24>>> days;
    auto utc_offset = hours(-4);  // my current UTC offset
    // Get duration in local units
    auto now = system_clock::now().time_since_epoch() + utc_offset;
    // Get duration in days
    auto today = duration_cast<days>(now);
    int year;
    unsigned month;
    unsigned day;
    // Convert days into year/month/day
    std::tie(year, month, day) = civil_from_days(today.count());
    // Subtract off days, leaving now containing time since local midnight
    now -= today;
    auto h = duration_cast<hours>(now);
    now -= h;
    auto m = duration_cast<minutes>(now);
    now -= m;
    auto s = duration_cast<seconds>(now);
    now -= s;
    auto us = duration_cast<microseconds>(now);
    cout.fill('0');
    cout << "Today is "
         << year << '-' << setw(2) << month << '-' << setw(2) << day
         << " at " << setw(2) << h.count() << ':'
         << setw(2) << m.count() << ':'
         << setw(2) << s.count() << '.' << setw(6) << us.count() << '\n';
}

For me this outputs:

Today is 2013-08-04 at 20:21:22.043095

I've used civil_from_days to turn a chrono::duration obtained from system_clock::now() into a year/month/day triple. For grins I've also subtracted off the days from the duration to get the hours, subtracted off the hours to get minutes, and subtracted off the minutes to get seconds, so I can print out the current time along with the current date. On my system I can even print the current time with microsecond accuracy if I want (something not even possible with the C interface).

One can also go the other way: Specify a date in terms of a year/month/day triple and then convert that into a system_clock::time_point:

int
main()
{
    using namespace std;
    using namespace std::chrono;
    typedef duration<int, ratio_multiply<hours::period, ratio<24>>> days;
    auto utc_offset = hours(-4);
    // Build a time point in local days::hours::minutes and then convert to UTC
    auto wakeup_at = system_clock::time_point(days(days_from_civil(2013, 8, 4))
                                              + hours(20) + minutes(59) - utc_offset);
    this_thread::sleep_until(wakeup_at);
    print_current_date_time();
}

Today is 2013-08-04 at 20:59:00.021702

Example: Finding nth weekday of month

weekday_difference is handy for computing dates like the 4th Saturday in May, or the last Sunday of Jun. For an example of the former consider:

std::tuple<int, unsigned, unsigned>
get_nth_dow_month_year(unsigned n, unsigned wd, unsigned month, int year)
{
    // Do validation here
    assert(n <= 4);  // We could possibly allow n == 5, but it would sometimes fail
    assert(wd <= 6);
    assert(1 <= month && month <= 12);
    const unsigned wd_1st = weekday_from_days(days_from_civil(year, month, 1));
    const unsigned day = weekday_difference(wd, wd_1st) + 1 + (n-1)*7;
    return std::tuple<int, unsigned, unsigned>(year, month, day);
}

First compute the weekday of the first day of the month. Then add to the first day of the month the difference between the weekday you want and the weekday you have. This will be some number between 0 and 6. And then add to that n-1 weeks. Now you have a year/month/day triple. If instead you wanted to return a system_clock::time_point, that is just as easy:

std::chrono::system_clock::time_point
get_nth_dow_month_year(unsigned n, unsigned wd, unsigned month, int year)
{
    // Do validation here
    // Don't actually need to check n
    assert(wd <= 6);
    assert(1 <= month && month <= 12);
    using namespace std;
    using namespace std::chrono;
    typedef duration<int, ratio_multiply<hours::period, ratio<24>>> days;
    int d = days_from_civil(year, month, 1);
    const unsigned wd_1st = weekday_from_days(d);
    d += weekday_difference(wd, wd_1st) + (n-1)*7;
    return system_clock::time_point(days(d));
}

If you are wanting to get the last weekday of a month, this is also very easy using weekday_difference:

std::tuple<int, unsigned, unsigned>
get_last_dow_month_year(unsigned wd, unsigned month, int year)
{
    // Do validation here
    assert(wd <= 6);
    assert(1 <= month && month <= 12);
    const unsigned last = last_day_of_month(year, month);
    const unsigned wd_last = weekday_from_days(days_from_civil(year, month, last));
    const unsigned day = last - weekday_difference(wd_last, wd);
    return std::tuple<int, unsigned, unsigned>(year, month, day);
}

You simply compute the weekday of the last day of the month, and then use weekday_difference to find the number of days that need to be subtracted from the last day of the month to get to the desired weekday.

In some circumstances you might want to find the next weekday, not counting the "current day". For example you may need the next Thu from today, and if today is a Thu, you need a week from today, not today. In this use case, combining weekday_difference with next_weekday is very handy:

int meeting_day = tomorrow + weekday_difference(desired_weekday, next_weekday(todays_weekday));

Where tomorrow is just today+1 and todays_weekday is today's weekday.

Example: Converting between the civil calendar and the ISO week calendar

These algorithms can be used to easily convert between the civil calendar and the ISO week-based calendar. The ISO rules for this calendar are:

  1. The week starts with Monday, and ends with Sunday.
  2. The first day of the year is the Monday that occurs on or before Jan. 4.
  3. A date is specified by the week number [1 - 53], day of the week [Mon - Sun] and year number.
  4. The year number is the same as the civil year number for the Thursday that follows the start of the week-based year.

ISO 8601 gives two examples:

  1. Sunday Jan. 1, 1995 is the Sunday of week 52 of the year 1994. (Week 1 of 1995 starts on Monday Jan. 2, 1995)
  2. Tuesday Dec. 31, 1996 is the Tuesday of week 1 of the year 1997. (The first day of the week-based year 1997 begins on Monday Dec. 30, 1996, which is the first Monday on or before Jan. 4, 1997, a Saturday)

Here are functions for converting from year/month/day to year/week/weekday and back. It is first convenient to create a function that finds the "time_point" (count of days since epoch) of the first day of the week-based year given the year number. This year number is actually the week-based year number, not the civil year number:

int
iso_week_start_from_year(int y)
{
    const unsigned Monday = 1;
    const unsigned Jan = 1;
    const int tp = days_from_civil(y, Jan, 4);
    const unsigned wd = weekday_from_days(tp);
    return tp - static_cast<int>(weekday_difference(wd, Monday));
}

To ease confusion and allow reuse of the code we've developed, we continue to encode our days [Sun, Sat] as [0, 6], despite the fact that Sun/0 is now the last day of the week instead of the first.

Given the tools in our toolbox, this function is remarkably easy to create from rule 2 above:

  1. Turn y-01-04 into a serial date.
  2. Get the weekday of y-01-04.
  3. Subtract off the number of days the current weekday is past Monday.

Using the iso_week_start_from_year helper function, it is now easy to convert from year/month/day to year/week_number/week_day:

// year, week[1, 53], weekday[0, 6]
std::tuple<int, unsigned, unsigned>
iso_week_from_civil(int y, unsigned m, unsigned d)
{
    const unsigned Monday = 1;
    const unsigned Thursday = 4;
    const int tp = days_from_civil(y, m, d);
    int iso_week_start = iso_week_start_from_year(y);
    if (tp < iso_week_start)
        iso_week_start = iso_week_start_from_year(y-1);
    else
    {
        const int iso_week_next_year_start = iso_week_start_from_year(y+1);
        if (tp >= iso_week_next_year_start)
            iso_week_start = iso_week_next_year_start;
    }
    const unsigned weekday = weekday_from_days(tp);
    const unsigned week = (tp - iso_week_start) / 7 + 1;
    int year;
    std::tie(year, std::ignore, std::ignore) =
        civil_from_days(iso_week_start + int(Thursday - Monday));
    return std::tuple<int, unsigned, unsigned>(year, week, weekday);
}

We're going to need to easily compare dates using less-than. To do that we need to work in terms of serial dates, so we convert both the y/m/d and the start of the ISO week-based year into serial dates (tp and iso_week_start).

Recall that the input to iso_week_start_from_year is the week-based year number, not the civil year number. So it is possible that our year number is one off, causing the current date to fall outside of the range of the ISO week-based year we just computed. The ISO 8601 examples given above are both cases where this happens. So we test if tp is prior to iso_week_start. If it is, then we need to change the start of the ISO week to that of the previous year. Otherwise we need to check if tp falls in the following ISO week-based year, and if so change iso_week_start to the following year.

Once past the if-statement, iso_week_start is the correct beginning of the week-based year that contains tp. We need the weekday of tp, easily computed with weekday_from_days. We need the week number, easily computed by finding out how many weeks tp is beyond iso_week_start, and recalling that the week number is 1-based, not 0-based. And finally we need to implement ISO rule 4 which says that the year number is that of the civil date for the Thursday that follows the start of the ISO week-based year.

The reverse conversion, from year/week_number/week_day to year/month/day is even easier:

// year, month[1, 12], day[1, 31]
std::tuple<int, unsigned, unsigned>
civil_from_iso_week(int y, unsigned w, unsigned wd)
{
    int tp = iso_week_start_from_year(y) + (w-1) * 7 + (wd == 0 ? 6 : wd - 1);
    return civil_from_days(tp);
}

One simply converts the week-based year into a serial date by using our helper function iso_week_start_from_year, the number of 1-based weeks, and the day of the week. For the latter, recall that Sunday is the last day of the week, or day 6 of the week, and Monday is the first day of the week, or day 0 of the week. Once we have a serial date, it is now trivial to convert that to a civil date using civil_from_days.

Note that in any of these formulas, the variable named tp is a serial date, compatible with chrono::system_clock::time_point, and so you could just as easily be converting to or from a chrono::system_clock::time_point using:

typedef duration<int, ratio_multiply<hours::period, ratio<24>>> days;
// tp -> time_point
system_clock::time_point time_point(days(tp));
// time_point -> tp
int tp2 = duration_cast<days>(time_point.time_since_epoch()).count();

And actually, if you anticipate converting negative system_clock::time_points you should create yourself a round_down function and use that in place of duration_cast:

template <class To, class Rep, class Period>
To
round_down(const std::chrono::duration<Rep, Period>& d)
{
    To t = std::chrono::duration_cast<To>(d);
    if (t > d)
        --t;
    return t;
}

For example if your system_clock::time_point contains a duration of seconds(-1), and you convert that to days, you want days to be -1 (midnight 1969-12-31), not 0 (midnight 1970-01-01).

// time_point -> tp
int tp2 = round_down<days>(time_point.time_since_epoch()).count();

Example: Converting between the civil calendar and the Julian calendar

It is relatively straight forward to derive days_from_julian from days_from_civil by simply adjusting the constants in days_from_civil:

// Returns number of days since civil 1970-01-01.  Negative values indicate
//    days prior to 1970-01-01.
// Preconditions:  y-m-d represents a date in the Julian calendar
//                 m is in [1, 12]
//                 d is in [1, last_day_of_month_julian(y, m)]
//                 y is "approximately" in
//                   [numeric_limits<Int>::min()/366, numeric_limits<Int>::max()/366]
template <class Int>
constexpr
Int
days_from_julian(Int y, unsigned m, unsigned d) noexcept
{
    static_assert(std::numeric_limits<Int>::digits >= 20,
             "This algorithm has not been ported to a 16 bit signed integer");
    y -= m <= 2;
    const Int era = (y >= 0 ? y : y-3) / 4;
    const unsigned yoe = static_cast<unsigned>(y - era * 4);        // [0, 3]
    const unsigned doy = (153*(m + (m > 2 ? -3 : 9)) + 2)/5 + d-1;  // [0, 365]
    const unsigned doe = yoe * 365 + doy;                           // [0, 1460]
    return era * 1461 + static_cast<Int>(doe) - 719470;
}

In the Julian calendar the era is only 4 years long instead of 400. This greatly simplifies everything. Otherwise we still use the the same basic design and algorithms as developed for days_from_civil. The one tricky part is that the constant to shift the epoch to the chrono-compatible civil 1970-01-01, the constant 719468 needs to be adjusted. To find the right shift, it is handy to note that there is a well-documented equivalence between the Julian and civil calendars:

static_assert(days_from_julian(1582, 10, 5) == days_from_civil(1582, 10, 15),
              "Rome switches from Julian to Gregorian");

If this equivalence does not hold true, then the epochs are not properly aligned.

Similarly, julian_from_days is derived from civil_from_days by simply adjusting the constants:

// Returns year/month/day triple in Julian calendar
// Preconditions:  z is number of days since 1970-01-01 (civil) and is not "too close"
//                   to numeric_limits<Int>::min() or numeric_limits<Int>::max().
template <class Int>
constexpr
std::tuple<Int, unsigned, unsigned>
julian_from_days(Int z) noexcept
{
    static_assert(std::numeric_limits<Int>::digits >= 20,
             "This algorithm has not been ported to a 16 bit signed integer");
    z += 719470;
    const Int era = (z >= 0 ? z : z - 1460) / 1461;
    const unsigned doe = static_cast<unsigned>(z - era * 1461);  // [0, 1460]
    const unsigned yoe = (doe - doe/1460) / 365;                 // [0, 3]
    const Int y = static_cast<Int>(yoe) + era * 4;
    const unsigned doy = doe - 365 * yoe;                        // [0, 365]
    const unsigned mp = (5*doy + 2)/153;                         // [0, 11]
    const unsigned d = doy - (153*mp+2)/5 + 1;                   // [1, 31]
    const unsigned m = mp + (mp < 10 ? 3 : -9);                  // [1, 12]
    return std::tuple<Int, unsigned, unsigned>(y + (m <= 2), m, d);
}

And now one can easily convert between the civil and Julian calendars by simply converting to the serial calendar in between, for example:

std::tuple<int, unsigned, unsigned>
julian_from_civil(int y, unsigned m, unsigned d)
{
    return julian_from_days(days_from_civil(y, m, d));
}

It is also interesting, and somewhat amusing, to note that the weekday_from_days function is just as valid for the Julian calendar as it is for the civil calendar. Some things even the pope won't mess with! But note that is_leap and last_day_of_month are not valid for the Julian calendar. Though it is certainly trivial to write Julian versions of these functions if desired.

How can I confirm that your assertions about chrono compatibility are correct?

Good question. I could be full of hot air.

Run the following program while noting through an independent source what the current time in the UTC timezone is:

#include <iostream>
#include <chrono>
#include <iomanip>

void
print_current_utc_date_time()
{
    using namespace std;
    using namespace std::chrono;
    typedef duration<int, ratio_multiply<hours::period, ratio<24>>> days;
    auto now = system_clock::now().time_since_epoch();
    auto today = duration_cast<days>(now);
    int year;
    unsigned month;
    unsigned day;
    std::tie(year, month, day) = civil_from_days(today.count());
    now -= today;
    auto h = duration_cast<hours>(now);
    now -= h;
    auto m = duration_cast<minutes>(now);
    now -= m;
    auto s = duration_cast<seconds>(now);
    cout.fill('0');
    cout << "Today is "
         << year << '-'
         << setw(2) << (unsigned)month << '-'
         << setw(2) << (unsigned)day
         << " at " << setw(2) << h.count() << ':'
         << setw(2) << m.count() << ':'
         << setw(2) << s.count() << " UTC\n";
}

int
main()
{
    print_current_utc_date_time();
}

The reported time through this program, and your independent source should be identical down to the nearest second. If they are, then the assumptions about your std::chrono::system_clock epoch are correct. If the two times disagree, you can still fix it.

If the times differ by more than 86400 seconds, then you can alter the constant 719468 in days_from_civil and civil_from_days to whatever it takes to bring the difference down below 86400 seconds.

If the times differ by less than 86400 seconds then you will need to add/subtract that many seconds whenever you convert a days duration from days_from_civil to/from a std::chrono::system_clock::time_point. One possibility is that the std::chrono::system_clock implementation is taking leap seconds into account.

My best guess is that you will never run into this problem. I have surveyed the LLVM libc++, the GNU libstdc++, and MVC++. My personal experience with this survey is only with libc++. I'm counting on reports from others for libstdc++ and MVC++. But in all cases I'm seeing the use of unix time. Implementations will not easily change their epoch, even though the epoch is unspecified, as the epoch is detectible. I.e. the epoch is part of an implementation's ABI.

Summary

We don't have a modern date class in the std::lib, and that is somewhat of a pain. However these formulas are nice to have in your toolbox, and can be quite useful, even without a type-safe date class. Maybe they don't have quite the right interface. Maybe the names aren't the best. But the formulas are good. Consider these donated to the public domain. Perhaps you can use them to create the next great date class!

Acknowledgments

I do not claim that any of these formulas are original. For example I've seen the shift to March as the first month of the year many times before. I haven't seen the use of eras before, nor the use of the equation that transforms a day-of-era into a year-of-era before. However I would be surprised if this was the first use of these formulations.

Thanks to Vicente J. Botet whose comments caused me to rethink several aspects of this paper.

Thanks to Jonathan Sauer who pointed out to me that C++98/03 compilers are allowed to implement truncated, floored or Euclidean integral division. However C++11 specifies truncated. I am unaware of any C++98/03 compiler that does not implement truncated division, which is probably why C++11 was able to change from implementation defined to truncated.