Counting the days, revisited – Tony Finch
Many years ago I wrote about how to convert Gregorian dates to Julian<br>Day numbers or similar counts such as rata die as used<br>in Calendrical Calculations. This algorithm is the core of<br>C’s mktime() function that converts a broken-down date-time<br>into linear time_t.
I recently learned from Ben Joffe that I was missing a few<br>tricks, and my old code wasn’t as good as it could have been. Here’s<br>a better version (using conventional not C numbering):
if m > 2 { m -= 2; } else { m += 10; y -= 1; }<br>y*365 + y/4 - y/100 + y/400 + m*979/32 + d - 336
the main idea
Julian years
Gregorian correction
the month pattern
the epoch
domains and ranges
leap year test
length of month
the main idea
There’s a helpful coincidence in the Gregorian calendar.
Although the month lengths aren’t obviously regular, there’s a<br>repeating 5 month pattern that becomes easier to see when you start<br>from March, as illustrated by the table below.
This pattern resets at the end of February, midway through its<br>third repeat, coincidentally at the same point that leap days occur.
Thus the first line of the code above adjusts the month and year<br>numbers so that January and February are counted at the end of the<br>previous year, and the coincidental alignment occurs at the boundary<br>between the adjusted year numbers.
I’ll explain the details of the adjustment as I discuss the relevant<br>parts of the second line
March<br>31 days
April<br>30 days
May<br>31 days
June<br>30 days
July<br>31 days
August<br>31 days
September<br>30 days
October<br>31 days
November<br>30 days
December<br>31 days
January<br>31 days
February<br>28 or 29
Julian years
The first part of the main formula counts the number of days before<br>the start of year y, in terms of normal years and leap days.
y * 365 + y / 4
The adjustment subtracts one from the year in January and February.<br>The effect is that the leap day in year 4 is counted as a day before<br>the start of the adjusted beginning of year 4, i.e. before March, i.e.<br>exactly the right place.
I previously combined this part of the expression into a single term,
y * 1461 / 4
Ben Joffe pointed out that when it is written this way the function is<br>only able to make use of 25% of the range of its output data type,<br>because the multiplication overflows for very large year numbers. And<br>on modern CPUs it isn’t actually faster to eliminate the addition.
Gregorian correction
The next part corrects the number of leap years before the current year.
- y/100 + y/400
It works in basically the same way as the Julian leap year<br>calculation, but whereas y/4 trivially compiles to a simple shift<br>operation, this needs a bit more cleverness.
As Hacker’s Delight explains, a modern compiler will turn<br>y/100 into a multiply-and-shift:
y * (1> (N+2)
That is, the compiler uses a fixed-point representation of the<br>reciprocal of the divisor. Then it uses common subexpression<br>elimination to suppress the second multiplication by 1/25.
So these two divisions are turned into a wide multiply and two shifts.<br>Neat.
the month pattern
The next part counts the number of days in this (adjusted) year before<br>the start of month m.
m * 979 / 32
I previously wrote it using the number of days in the repeating<br>pattern of 5 months,
m * 153 / 5
But this is relatively difficult for compilers to optimize well (clang<br>uses two multiplications instead of one), and they don’t know the<br>range of m is limited, so we can do better by turning it into a<br>multiply-and-shift by hand.
979/32 == 30.59375 which is close enough to the exact value 153/5 == 30.6
Either of these expressions produce the right 5 month long/short<br>pattern, but the pattern doesn’t necessarily line up with the normal<br>month numbering. (The two expressions above need different<br>adjustments.)
We move March to number 1, just before the start of the pattern. When<br>counting the days before April, we get 31 more than the count for<br>March; when counting the days before May, we get 30 more than the<br>count for April, etc.
January is adjusted to follow December to match the adjusted year<br>numbering.
m *979/32 diff<br>1 30 March<br>2 61 31 April<br>3 91 30 May<br>4 122 31<br>5 152 30<br>6 183 31<br>7 214 31<br>8 244 30<br>9 275 31<br>10 305 30 December<br>11 336 31 January<br>12 367 31<br>13 397 30
the epoch
Because calendars count from 1, the Gregorian date 0001-01-01 gets<br>numbered rata die 1.
The adjustments turn January into month 11, and so (as in the second<br>column in the table above) we count 336 days in the adjusted year 0<br>before January. We need to subtract those extra days to compensate for<br>the adjustment.
We can change the offset to choose a different epoch, e.g. the MJD<br>epoch 1858-11-17 is r.d. 678576, and the Unix epoch 1970-01-01 is<br>r.d. 719163.
domains and ranges
In my old C code I casually used int, which misleadingly implied<br>that it worked with proleptic Gregorian calendar dates before<br>year 1.
However signed division and modulus on common CPUs and<br>low-level programming languages truncates towards zero, but...