chrono-Compatible Low-Level Date Algorithmsdays_from_civilcivil_from_daysis_leaplast_day_of_month_common_yearlast_day_of_month_leap_yearlast_day_of_monthweekday_from_daysweekday_differencenext_weekdayprev_weekdaychrono compatibility?chrono compatibility are correct?
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:
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;
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;
Determine if a year is a leap year.
template <class Int> constexpr bool is_leap(Int y) noexcept;
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;
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;
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;
Convert from a serial day number to a day of the week.
template <class Int> constexpr unsigned weekday_from_days(Int z) noexcept;
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;
Get the weekday following a weekday (e.g. Mon follows Sun).
constexpr unsigned next_weekday(unsigned wd) noexcept;
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_civilFirst 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:
yoe)? This is always in the
range [0, 399].
doe)? This is always in the
range [0, 146096].
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.
era start date end date -2 -0800-03-01 -0400-02-29 -1 -0400-03-01 0000-02-29 0 0000-03-01 0400-02-29 1 0400-03-01 0800-02-29 2 0800-03-01 1200-02-29 3 1200-03-01 1600-02-29 4 1600-03-01 2000-02-29 5 2000-03-01 2400-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:
- Map civil month number [1, 12] (Jan. - Dec.) into the internal month numbering [0, 11] (Mar. - Feb.).
- Compute the number of days between Mar. 1 and the first day of the current month.
- Add the number of days between the current day of the month and the first day of the current month.
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 monthm'isxnumber of days after Mar. 1.This can be exactly expressed as a table:
month m'days after m'-01 Mar 0 0 Apr 1 31 May 2 61 Jun 3 92 Jul 4 122 Aug 5 153 Sep 6 184 Oct 7 214 Nov 8 245 Dec 9 275 Jan 10 306 Feb 11 337 However we would like to translate this table into a linear polynomial.
a1 m' + a0Note 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 fora1anda0: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 == 30ora1 == 31, there is no value fora0we 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 == 337anda0 == 11. However when doing so there is no value ofb0that will pass the unit test. However if we makeb1 == 306anda0 == 10(i.e.306/10 ≈ 30.63636363636364) then there are actually two formulations that pass all unit tests:
return (306 * mp + 4) / 10;return (306 * mp + 5) / 10;I first arbitrarily selected the second. However note that the first can be simplified down to:
return (153 * mp + 2) / 5;For reasons I do not fully understand, this latter formula tests slightly faster (about 2%) than the others.
Now
mprepresentsm'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 tom, and taking the modulus of the result by 12:mp = (m + 9) % 12;This formula results in the following relationship:
m1 2 3 4 5 6 7 8 9 10 11 12 mp10 11 0 1 2 3 4 5 6 7 8 9 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)/5Now to get the day-of-year from the double
month/dayone 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:
m3 2 2 d1 29 28 doy0 365 364
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_civilwe had to develop a linear equation to compute the day-of-year from the first day of monthm'wherem'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_monthcan 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
aare the first and last numbers of the day-of-year for each month in [0, 11]. We already have a functiondoy_from_month(mp)which computes the starting day-of-year for each month, and tested by the firstassertin the program. And now two moreasserts are added to test that given both the first and last day of each month,month_from_doycan transform that day-of-year into the correct month numbermp.Running this test on the
month_from_doygiven 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:
return (10*doy + 4) / 306;return ( 5*doy + 2) / 153;return (10*doy + 5) / 306;I've chosen the second for use in
civil_from_daysbecause 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 time this 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_yearGiven 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_yearGiven 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_monthGiven 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 distributedmin the range [1, 12], the following table gives the odds of exactly what gets executed in a call tolast_day_of_month(y, m):
This percentage of the time this will get executed 91⅔% m != 26¼% (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 thebool is_leapis even touched. Additionally in over 6% of the cases, the only additional code is a% 4which 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 computingis_leap(y)is just as fast or very nearly just as fast. In 2% of the cases, avoiding theis_leap(y)computation saves a%operation. And in 1/12 of 1% of the cases, avoiding theis_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_daysThe 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_differenceIt 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_weekdayIt 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_weekdayIt 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.
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.
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
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.
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:
ISO 8601 gives two examples:
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:
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();
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.
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.
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!
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.