forked from HowardHinnant/HowardHinnant.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
/
date_algorithms.html
2197 lines (1933 loc) · 73.6 KB
/
date_algorithms.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>chrono-Compatible Low-Level Date Algorithms</title>
<style type="text/css">
p {text-align:justify}
li {text-align:justify}
blockquote.note
{
background-color:#E0E0E0;
padding-left: 15px;
padding-right: 15px;
padding-top: 1px;
padding-bottom: 1px;
}
ins {background-color:#A0FFA0}
del {background-color:#FFA0A0}
</style>
</head>
<body>
<address align=right>
<br>
<a href="mailto:[email protected]">Howard Hinnant</a><br>
2021-09-01
</address>
<hr>
<h1 align=center><code>chrono</code>-Compatible Low-Level Date Algorithms</h1>
<h2>Contents</h2>
<ul>
<li><a href="#Introduction">Introduction</a></li>
<li><a href="#days_from_civil"><code>days_from_civil</code></a></li>
<li><a href="#civil_from_days"><code>civil_from_days</code></a></li>
<li><a href="#is_leap"><code>is_leap</code></a></li>
<li><a href="#last_day_of_month_common_year"><code>last_day_of_month_common_year</code></a></li>
<li><a href="#last_day_of_month_leap_year"><code>last_day_of_month_leap_year</code></a></li>
<li><a href="#last_day_of_month"><code>last_day_of_month</code></a></li>
<li><a href="#weekday_from_days"><code>weekday_from_days</code></a></li>
<li><a href="#weekday_difference"><code>weekday_difference</code></a></li>
<li><a href="#next_weekday"><code>next_weekday</code></a></li>
<li><a href="#prev_weekday"><code>prev_weekday</code></a></li>
<li><a href="#Yes, but how do you know this all really works?">Yes, but how do you know this all really works?</a></li>
<li><a href="#What can I do with that <code>chrono</code> compatibility?">What can I do with that <code>chrono</code> compatibility?</a></li>
<li><a href="#Example: Finding nth weekday of month">Example: Finding nth weekday of month</a></li>
<li><a href="#Example: Converting between the civil calendar and the ISO week calendar">Example: Converting between the civil calendar and the ISO week calendar</a></li>
<li><a href="#Example: Converting between the civil calendar and the Julian calendar">Example: Converting between the civil calendar and the Julian calendar</a></li>
<li><a href="#How can I confirm that your assertions about <code>chrono</code> compatibility are correct?">How can I confirm that your assertions about <code>chrono</code> compatibility are correct?</a></li>
<li><a href="#Summary">Summary</a></li>
<li><a href="#Acknowledgments">Acknowledgments</a></li>
</ul>
<h2><a name="Introduction"></a>Introduction</h2>
<p>
The purpose of this paper is <b>not</b> to propose a date class. For an example date
library based on these algorithms see <a href="https://howardhinnant.github.io/date/date.html"><code>date</code> v2</a>.
</p>
<p>
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 <code>noexcept</code>, and if C++1y
is available, they can trivially be made <code>constexpr</code>.
</p>
<p>
This paper does not document a library. It is a <i>how-to</i> 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.
</p>
<p>
The algorithms are interoperable with every known implementation of
<code>std::chrono::system_clock</code>, though that interoperability depends
on an unspecified property of the <code>system_clock</code>: its epoch. Example
code will be shown how these algorithms can take advantage of the common
(but unspecified) <code>system_clock</code> epoch.
</p>
<p>
The algorithms implement a
<a href="http://en.wikipedia.org/wiki/Proleptic_Gregorian_calendar">proleptic Gregorian calendar</a>.
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
<i>civil</i> 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.
</p>
<p>
The algorithms implement no validity checking. The intent is that any desired
validity checking on the triple <code>year/month/day</code> can be added on
top of these algorithms if and where desired.
</p>
<p>
Ten low-level algorithms are presented:
</p>
<ol>
<li>
<p>
Convert from a <code>year/month/day</code> triple to a serial day number.
</p>
<blockquote><pre>
template <class Int>
constexpr
Int
days_from_civil(Int y, unsigned m, unsigned d) noexcept;
</pre></blockquote>
</li>
<li>
<p>
Convert from a serial day number to a <code>year/month/day</code> triple.
</p>
<blockquote><pre>
template <class Int>
constexpr
std::tuple<Int, unsigned, unsigned>
civil_from_days(Int z) noexcept;
</pre></blockquote>
</li>
<li>
<p>
Determine if a year is a leap year.
</p>
<blockquote><pre>
template <class Int>
constexpr
bool
is_leap(Int y) noexcept;
</pre></blockquote>
</li>
<li>
<p>
Given the month, return the last day of the month of a common year.
</p>
<blockquote><pre>
constexpr
unsigned
last_day_of_month_common_year(unsigned m) noexcept;
</pre></blockquote>
</li>
<li>
<p>
Given the month, return the last day of the month of a leap year.
</p>
<blockquote><pre>
constexpr
unsigned
last_day_of_month_leap_year(unsigned m) noexcept;
</pre></blockquote>
</li>
<li>
<p>
Given the year and month, return the last day of the month.
</p>
<blockquote><pre>
template <class Int>
constexpr
unsigned
last_day_of_month(Int y, unsigned m) noexcept;
</pre></blockquote>
</li>
<li>
<p>
Convert from a serial day number to a day of the week.
</p>
<blockquote><pre>
template <class Int>
constexpr
unsigned
weekday_from_days(Int z) noexcept;
</pre></blockquote>
</li>
<li>
<p>
Subtract one weekday from another (e.g. Sun - Sat is 1, and Sat - Sun is 6).
</p>
<blockquote><pre>
constexpr
unsigned
weekday_difference(unsigned x, unsigned y) noexcept;
</pre></blockquote>
</li>
<li>
<p>
Get the weekday following a weekday (e.g. Mon follows Sun).
</p>
<blockquote><pre>
constexpr
unsigned
next_weekday(unsigned wd) noexcept;
</pre></blockquote>
</li>
<li>
<p>
Get the weekday prior to a weekday (e.g. Sat comes before Sun).
</p>
<blockquote><pre>
constexpr
unsigned
prev_weekday(unsigned wd) noexcept;
</pre></blockquote>
</li>
</ol>
<p>
The algorithms are templated on year number type and serial day number
type so that you can easily vary the range (use <code>int</code>,
<code>long long</code>, <code>big_num</code>, or whatever). For those
fields that are known to be unsigned and small (e.g. month)
<code>unsigned</code> is used. Feel free to substitute any type you
like. The use of <code>unsigned</code> is just to demonstrate that this
particular field is constrained in the algorithm to always remain within
a non-negative range.
</p>
<p>
Building upon these low-level algorithms, higher-level algorithms can
easily be written, and this paper shows several examples of such
higher-level algorithms.
</p>
<h2><a name="days_from_civil"></a><code>days_from_civil</code></h2>
<p>
First the algorithm, and then the explanation:
</p>
<blockquote>
<table border="1" cellpadding="10">
<tr><td>
<pre>
<font color="#C80000">// Returns number of days since civil 1970-01-01. Negative values indicate</font>
<font color="#C80000">// days prior to 1970-01-01.</font>
<font color="#C80000">// Preconditions: y-m-d represents a date in the civil (Gregorian) calendar</font>
<font color="#C80000">// m is in [1, 12]</font>
<font color="#C80000">// d is in [1, last_day_of_month(y, m)]</font>
<font color="#C80000">// y is "approximately" in</font>
<font color="#C80000">// [numeric_limits<Int>::min()/366, numeric_limits<Int>::max()/366]</font>
<font color="#C80000">// Exact range of validity is:</font>
<font color="#C80000">// [civil_from_days(numeric_limits<Int>::min()),</font>
<font color="#C80000">// civil_from_days(numeric_limits<Int>::max()-719468)]</font>
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); <font color="#C80000">// [0, 399]</font>
const unsigned doy = (153*(m > 2 ? m-3 : m+9) + 2)/5 + d-1; <font color="#C80000">// [0, 365]</font>
const unsigned doe = yoe * 365 + yoe/4 - yoe/100 + doy; <font color="#C80000">// [0, 146096]</font>
return era * 146097 + static_cast<Int>(doe) - 719468;
}
</pre>
</td></tr>
</table>
</blockquote>
<p>
As explained in the introduction, the type of <code>year</code> is templated
so that you can easily set your own range based on your own needs. And if
you dislike the use of <code>unsigned</code> for <code>month</code> and
<code>day</code>, 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 <code>constexpr</code> rules, you will need to remove (or comment out)
the <code>constexpr</code>. If you are compiling in C++98/03 you can substitute
<code>throw()</code> for <code>noexcept</code>, or remove the exception
specification entirely.
</p>
<p>
The first two algorithms also do some static checking on the range of
<code>Int</code> and <code>unsigned</code>. 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
<code>static_assert</code>. 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.
</p>
<p>
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.
</p>
<p>
Additionally the first two algorithms make use of the concept of an <i>era</i>.
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 <code>year/month/day</code> 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:
</p>
<ul>
<li>
What is the year of the era (<code>yoe</code>)? This is always in the
range <code>[0, 399]</code>.
</li>
<li>
What is the day of the era (<code>doe</code>)? This is always in the
range <code>[0, 146096]</code>.
</li>
</ul>
<p>
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.
</p>
<blockquote>
<table border="1" cellpadding="10">
<tr>
<th>era</th><th>start date</th><th>end date</th>
</tr>
<tr>
<td>-2</td><td>-0800-03-01</td><td>-0400-02-29</td>
</tr>
<tr>
<td>-1</td><td>-0400-03-01</td><td>0000-02-29</td>
</tr>
<tr>
<td>0</td><td>0000-03-01</td><td>0400-02-29</td>
</tr>
<tr>
<td>1</td><td>0400-03-01</td><td>0800-02-29</td>
</tr>
<tr>
<td>2</td><td>0800-03-01</td><td>1200-02-29</td>
</tr>
<tr>
<td>3</td><td>1200-03-01</td><td>1600-02-29</td>
</tr>
<tr>
<td>4</td><td>1600-03-01</td><td>2000-02-29</td>
</tr>
<tr>
<td>5</td><td>2000-03-01</td><td>2400-02-29</td>
</tr>
</table>
</blockquote>
<p>
So the first thing the <code>days_from_civil</code> algorithm does is
transform the <code>year</code> number to the internal one for Jan. and
Feb. And then the era is computed. For non-negative years, the era is
simply <code>y/400</code>. But for negative years one has to be careful
that years [-400, -1] map to era -1. By using
<a href="http://en.wikipedia.org/wiki/Modulo_operation">floored</a>
or
<a href="http://en.wikipedia.org/wiki/Euclidean_division">Euclidean</a>
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
<code>era</code> to simply <code>y / 400</code>. 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.
</p>
<p>
Once the <code>era</code> is known (this is generally a signed number of
unknown range), the year-of-era can easily be computed by subtracting
off the <code>year</code> from <code>era * 400</code>. This is the same
as the modulo operation, but assuming
<a href="http://en.wikipedia.org/wiki/Modulo_operation">floored</a>
or
<a href="http://en.wikipedia.org/wiki/Euclidean_division">Euclidean</a>
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 <code>era</code> is negative or non-negative.
</p>
<p>
At the same time as the <code>yoe</code> computation is happening, we can also
compute the day-of-year (<code>doy</code>) 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.
</p>
<p>
The <code>doy</code> computation is quite unintuitive and deserves an in-depth
explanation.
</p>
<blockquote>
<h3><a name="Computing day-of-year from month and day-of-month"></a>Computing day-of-year from month and day-of-month</h3>
<p>
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:
</p>
<ul>
<li>
Map civil month number [1, 12] (Jan. - Dec.) into the internal month
numbering [0, 11] (Mar. - Feb.).
</li>
<li>
Compute the number of days between Mar. 1 and the first day of the current
month.
</li>
<li>
Add the number of days between the current day of the month and the first day
of the current month.
</li>
</ul>
<p>
Let's start with the second bullet: Map a month number <code>m'</code>
in the range [0, 11] (Mar. - Feb.) into a range such that the first day
of the month <code>m'</code> is <code>x</code> number of days after Mar.
1.
</p>
<p>
This can be exactly expressed as a table:
</p>
<blockquote>
<table border="1" cellpadding="10">
<tr>
<th>month</th><th><code>m'</code></th><th>days after m'-01</th>
</tr>
<tr>
<td>Mar</td><td>0</td><td>0</td>
</tr>
<tr>
<td>Apr</td><td>1</td><td>31</td>
</tr>
<tr>
<td>May</td><td>2</td><td>61</td>
</tr>
<tr>
<td>Jun</td><td>3</td><td>92</td>
</tr>
<tr>
<td>Jul</td><td>4</td><td>122</td>
</tr>
<tr>
<td>Aug</td><td>5</td><td>153</td>
</tr>
<tr>
<td>Sep</td><td>6</td><td>184</td>
</tr>
<tr>
<td>Oct</td><td>7</td><td>214</td>
</tr>
<tr>
<td>Nov</td><td>8</td><td>245</td>
</tr>
<tr>
<td>Dec</td><td>9</td><td>275</td>
</tr>
<tr>
<td>Jan</td><td>10</td><td>306</td>
</tr>
<tr>
<td>Feb</td><td>11</td><td>337</td>
</tr>
</table>
</blockquote>
<p>
However we would like to translate this table into a linear polynomial.
</p>
<blockquote>
<i>a1 m' + a0</i>
</blockquote>
<p>
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.
</p>
<p>
The slope of this straight line can be easily computed by <code>337/11
== 30.63636363636364</code>. 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 <code>a1</code> and <code>a0</code>:
</p>
<blockquote><pre>
int
doy_from_month(int mp)
{
return a1 * mp + a0;
}
</pre></blockquote>
<p>
With this we can easily
write a comprehensive unit test for <code>doy_from_month</code>:
</p>
<blockquote><pre>
#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]);
}
</pre></blockquote>
<p>
If we make <code>a1 == 30</code> or <code>a1 == 31</code>, there is no
value for <code>a0</code> we can assign to make this unit test pass. However
we can manipulate the y-intercept (<code>a0</code>) in a very fine manner if
we express the equation as:
</p>
<blockquote><pre>
return (b1 * mp + b0) / a0;
</pre></blockquote>
<p>
The first best guess is to make <code>b1 == 337</code> and <code>a0 ==
11</code>. However when doing so there is no value of <code>b0</code> that
will pass the unit test. However if we make <code>b1 == 306</code> and
<code>a0 == 10</code> (i.e. <code>306/10 ≈ 30.63636363636364</code>) then
there are actually two formulations that pass all unit tests:
</p>
<ul>
<li>
<code>return (306 * mp + 4) / 10;</code>
</li>
<li>
<code>return (306 * mp + 5) / 10;</code>
</li>
</ul>
<p>
I first arbitrarily selected the second. However note that the first can be
simplified down to:
</p>
<ul>
<li>
<code>return (153 * mp + 2) / 5;</code>
</li>
</ul>
<p>
For reasons I do not fully understand, this latter formula tests slightly faster
(about 2%) than the others.
</p>
<p>
Now <code>mp</code> represents
<code>m'</code> or the month number that starts with Mar == 0. We also
need to map the civil month number (Mar == 3) (<code>m</code>) to
our internal month number (<code>mp</code>). This can be done by adding
9 to <code>m</code>, and taking the modulus of the result by 12:
</p>
<blockquote><pre>
mp = (m + 9) % 12;
</pre></blockquote>
<p>
This formula results in the following relationship:
</p>
<blockquote>
<table border="1" cellpadding="10">
<tr>
<th><code>m</code></th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td>
</tr>
<tr>
<th><code>mp</code></th><td>10</td><td>11</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td>
</tr>
</table>
</blockquote>
<p>
After some performance testing I discovered that replacing the <code>%</code>
with a branch was actually slightly faster, at least on the Core i5 I'm testing
on:
</p>
<blockquote><pre>
mp = m + (m > 2 ? -3 : 9);
</pre></blockquote>
<p>
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:
</p>
<blockquote><pre>
(153*(m + (m > 2 ? -3 : 9)) + 2)/5
</pre></blockquote>
<p>
Now to get the day-of-year from the double <code>month/day</code> one simply
adds the day-of-the-month, minus 1:
</p>
<blockquote><pre>
const unsigned doy = (153*(m + (m > 2 ? -3 : 9)) + 2)/5 + d - 1;
</pre></blockquote>
<p>
One can spot-check this formula in a few places:
</p>
<blockquote>
<table border="1" cellpadding="10">
<tr>
<th><code>m</code></th><td>3</td><td>2</td><td>2</td>
</tr>
<tr>
<th><code>d</code></th><td>1</td><td>29</td><td>28</td>
</tr>
<tr>
<th><code>doy</code></th><td>0</td><td>365</td><td>364</td>
</tr>
</table>
</blockquote>
</blockquote>
<p>
Now given year-of-era (<code>yoe</code>) and day-of-year (<code>doy</code>),
we can easily calculate the day-of-era (<code>doe</code>). 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:
</p>
<blockquote><pre>
const unsigned doe = yoe * 365 + yoe / 4 - yoe / 100 + doy;
</pre></blockquote>
<p>
Those familiar with this particular computation might question the lack of the
term:
</p>
<blockquote><pre>
+ yoe / 400
</pre></blockquote>
<p>
in the above formula. It would actually be correct to put it in. However note
that <code>yoe</code> is always in the range [0, 399], and so the contribution
of this term is always 0.
</p>
<p>
The final computation in <code>days_from_civil</code> is computing the serial date
from the <code>era</code> and from the day-of-era (<code>doe</code>). This
is simply:
</p>
<blockquote><pre>
return era * 146097 + static_cast<Int>(doe)
</pre></blockquote>
<p>
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
<code>days_from_civil</code> code. This is a shift which aligns this algorithm
with all known implementations of <code>std::chrono::system_clock</code>. It
makes the serial date 0 be equivalent to 1970-01-01 instead of 0000-03-01.
</p>
<p>
All known implementations of <code>std::chrono::system_clock</code> count
seconds from 1970-01-01, neglecting leap seconds. This is known as
<a href="http://en.wikipedia.org/wiki/Unix_time">unix time</a>. Implementations
are not required by the standard to use this measure. But it can be handy to
take advantage of it.
</p>
<h2><a name="civil_from_days"></a><code>civil_from_days</code></h2>
<p>
Now that we can use <code>days_from_civil</code> to convert a
<code>year/month/day</code> triple into a serial date, it is really
handy to be able to go the other way: convert a serial date into a
<code>year/month/day</code> triple. And this is exactly what
<code>civil_from_days</code> does. First the algorithm, and then the
explanation:
</p>
<blockquote>
<table border="1" cellpadding="10">
<tr><td>
<pre>
<font color="#C80000">// Returns year/month/day triple in civil calendar</font>
<font color="#C80000">// Preconditions: z is number of days since 1970-01-01 and is in the range:</font>
<font color="#C80000">// [numeric_limits<Int>::min(), numeric_limits<Int>::max()-719468].</font>
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); <font color="#C80000">// [0, 146096]</font>
const unsigned yoe = (doe - doe/1460 + doe/36524 - doe/146096) / 365; <font color="#C80000">// [0, 399]</font>
const Int y = static_cast<Int>(yoe) + era * 400;
const unsigned doy = doe - (365*yoe + yoe/4 - yoe/100); <font color="#C80000">// [0, 365]</font>
const unsigned mp = (5*doy + 2)/153; <font color="#C80000">// [0, 11]</font>
const unsigned d = doy - (153*mp+2)/5 + 1; <font color="#C80000">// [1, 31]</font>
const unsigned m = mp < 10 ? mp+3 : mp-9; <font color="#C80000">// [1, 12]</font>
return std::tuple<Int, unsigned, unsigned>(y + (m <= 2), m, d);
}
</pre>
</td></tr>
</table>
</blockquote>
<p>
Many of the same concepts used in developing <code>days_from_civil</code> 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.
</p>
<p>
The first step in the computation is to shift the epoch from 1970-01-01 to
0000-03-01:
</p>
<blockquote><pre>
z += 719468;
</pre></blockquote>
<p>
Now we can compute the <code>era</code> from the serial date by simply dividing
by the number of days in an <code>era</code> (146097). Again
<a href="http://en.wikipedia.org/wiki/Modulo_operation">floored</a>
or
<a href="http://en.wikipedia.org/wiki/Euclidean_division">Euclidean</a>
division must be used to correctly handle negative days.
</p>
<blockquote><pre>
const Int era = (z >= 0 ? z : z - 146096) / 146097;
</pre></blockquote>
<p>
The day-of-era (<code>doe</code>) 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
<a href="http://en.wikipedia.org/wiki/Modulo_operation">floored</a>
or
<a href="http://en.wikipedia.org/wiki/Euclidean_division">Euclidean</a>
division. This always results in a <code>doe</code> in the range [0,
146096].
</p>
<blockquote><pre>
const unsigned doe = static_cast<unsigned>(z - era * 146097);
</pre></blockquote>
<p>
From the day-of-era (<code>doe</code>), the year-of-era (<code>yoe</code>,
range [0, 399]) can be computed. This formula can be derived one piece at a
time. To start, the <code>yoe</code> can be approximated by simply dividing
<code>doe</code> by 365:
</p>
<blockquote><pre>
const unsigned yoe = doe / 365;
</pre></blockquote>
<p>
This is actually correct for <code>doe</code> in the range [0, 1459],
yielding a <code>yoe</code> 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:
</p>
<blockquote><pre>
const unsigned yoe = (doe - doe / 1460) / 365;
</pre></blockquote>
<p> Now the formula is accurate for <code>doe</code> in the range [0,
36523], yielding a <code>yoe</code> 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:
</p>
<blockquote><pre>
const unsigned yoe = (doe - doe/1460 + doe/36524) / 365;
</pre></blockquote>
<p>
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:
</p>
<blockquote><pre>
const unsigned yoe = (doe - doe/1460 + doe/36524 - doe/146096) / 365;
</pre></blockquote>
<p>
Given year-of-era, and era, one can now compute the year number:
</p>
<blockquote><pre>
const Int y = static_cast<Int>(yoe) + era * 400;
</pre></blockquote>
<p>
Note though that this year number is still in terms of a year that begins on
Mar. 1, not Jan. 1.
</p>
<p>
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:
</p>
<blockquote><pre>
const unsigned doy = doe - (365 * yoe + yoe / 4 - yoe / 100);
</pre></blockquote>
<p>
Again note the absence of the correct term <code>+ yoe / 400</code> because the
contribution of this term is always zero since 399 is the upper range of
<code>yoe</code>.
</p>
<blockquote>
<h3><a name="Computing month from day-of-year"></a>Computing month from day-of-year</h3>
<p>
When developing <code>days_from_civil</code> we had to develop a linear equation
to compute the day-of-year from the first day of month <code>m'</code> where
<code>m'</code> is in the range [0, 11] representing [Mar, Feb].
</p>
<blockquote><pre>
int
doy_from_month(int mp)
{
return (153 * mp + 2) / 5;
}
</pre></blockquote>
<p>
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:
</p>
<blockquote><pre>
int
month_from_doy(int doy)
{
return (5 * doy - 2) / 153;
}
</pre></blockquote>
<p>
Before accepting this as the correct answer, it is wise to build a unit test
for this function. The one developed for <code>doy_from_month</code> can easily
be augmented to test both of these functions at the same time:
</p>
<blockquote><pre>
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);
}
}
</pre></blockquote>
<p>
The pair of numbers in <code>a</code> are the first and last numbers of the
day-of-year for each month in [0, 11]. We already have a function
<code>doy_from_month(mp)</code> which computes the starting day-of-year for
each month, and tested by the first <code>assert</code> in the program. And
now two more <code>assert</code>s are added to test that given both the
first and last day of each month, <code>month_from_doy</code> can transform
that day-of-year into the correct month number <code>mp</code>.
</p>
<p>
Running this test on the <code>month_from_doy</code> 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:
</p>
<ul>
<li><code>return (10*doy + 4) / 306;</code></li>
<li><code>return ( 5*doy + 2) / 153;</code></li>
<li><code>return (10*doy + 5) / 306;</code></li>
</ul>
<p>
I've chosen the second for use in <code>civil_from_days</code> because it