# A Light Dark

## Cursed calendar computations

Recently, I’ve been working on some very cursed calendar maths. Specifically, trying to write some efficient code to work with some of the common operations you’d want to do with dates. I know that loads of code exists already to do this, but I wanted to, in a sense, discover these algorithms for myself, so I really understand how these computations work. There are loads of links to papers and explanations of why these algorithms work scattered among the existing implementations, but I figured, why can’t I just start from the rules and figure it out?

Before I fully unload the details, though, there are a few things that you need to know about calendars.

Content warning: I’ll be making a few jokes about various calendar terms, since a lot of people like to pretend that the “international calendar” isn’t the Christian calendar, forced upon the world by imperialism. There will be a few terms I intentionally misidentify because I find it funny. The remainder of what I say, however, will be correct.

## Proleptic calendars

Right now, we use the Gregorian calendar, which is the latest iteration of the Christian calendar, unleashed upon the world by Pope Gregory 8th, who I’ve personally just been calling Greg. A lot of people like to pretend that this is now the “ISO” calendar, and that somehow, globalisation and imperialism excuse its Christian origins, but… yeah, nope. It’s the Christian calendar, but we’ve collectively decided to use it.

Anyway, the Gregorian calendar hasn’t been used since the dawn of time. In fact, Greg’s big day was in 1582 on October 15th, when Greg’s calendar finally dropped. The previous day was actually October 4th according to the previous iteration of the Christian calendar, the Julian calendar, named after a kind of salad who had a particular lust for warfare.

Of course, our calendars are already confusing enough, which is why for the longest time after Greg’s big day, people had a habit of noting the date on *both* calendars, Gregorian and the Julian, so that people would be even more confused about the state of things. Extending these calendars past their “expiration date” is called prolepsis, and we refer to these expired calendars as “proleptic” calendars.

Basically… we know that the Gregorian calendar didn’t exist before Greg’s Big Day, and we know that the Julian calendar didn’t exist past then, but we can still pretend. This is extra helpful because Greg didn’t spend a lot of time on his marketing campaign and a lot of places didn’t notice the news until several days, or years, later.

## Leaping too far

Now, Greg spent long and hard thinking about how to convert between the Julian and Gregorian calendars. Both of them agreed on the number of days since the Christian Era started (we use the terms BCE and CE to describe years after and before this time), but they disagreed on how many years exactly this was.

Both calendars agree that the year is around 365 days long, and that we should add an extra, 366th day about every 4 years. Since we know the absolute time the calendar started, we also know that this time should be the same on both calendars.

For those who don’t know the difference between the two calendars: it’s actually rather minor. The Julian calendar simply added an extra day to every year that was divisible by four, whereas Greg switched things up a bit: on Greg’s calendar, years that are multiples of 100 are not leap years, unless they’re divisible by 400. This means that the year 1900 wasn’t a leap year on Greg’s calendar, even though the year 2000 was.

However, Rome messed up a lot when it came to their own calendar, and lost track of leap years for the first few years. The actual days that leap days occurred wasn’t always February 29th, and some years had to get multiple days added or subtracted to realign stuff. When we talk about the proleptic Julian calendar, we just ignore these mistakes and use the tried-and-true multiple-of-four rule, and we put the leap day on February 29th, where we put it now.

So, among this giant mess, after considering leap years, the Gregorian and Julian calendars are exactly two days off. This means that on the year before 1 CE (which should be zero, but is actually 1 BCE), January 1st on the Gregorian calendar is actually January 3rd on the Julian calendar. I searched across several different sources and could not find anyone who actually explicitly pointed this out. But, if you do the leap year calculations, keeping in mind that in 1582, October 4th on the Julian calendar is October 14th on the Gregorian calendar, you’ll find that the two calendars are two days off the difference you’d expect from leap years.

## Leaping just, in general

One of the most common operations on dates is to compute the date a given number of days after or before the given date. Simple dates are easy to compute; for example, 30 days after January 1st, regardless of year, is January 31st. However, once the number of days extends beyond a single year, things get tricky. We could just check if a year is a leap year, subtract 365 or 366 from our offset accordingly, then keep doing this until we have the right year, but that’s very slow.

It goes without saying, but when computing these date offsets, it’s easiest to work with a day-of-year, rather than a month and day-of-month. For example, February 28th is day 58 of the year, and March 1st is either day 59 or day 60 depending on whether it’s a leap year. Given a day-of-year and the year, it’s pretty easy to convert back to a month-day, and it helps make our leap year calculations simpler.

We’ll start with describing our date-offset algorithm at a high-level, then fill in the lower-level details.

### Offsetting dates

To offset dates, we want to be able to take a given date and compute the date N days later. If N is zero, we get the current date; if N is positive, we get the date N days later; if N is negative, we get the date -N days earlier.

Like we mentioned earlier, it’s much easier to do this calculation with a day-of-year instead of a month-day, but there’s actually an even simpler way to describe this algorithm. Since the day-of-year just describes the number of days from the beginning of the year, and N is our number of days from the given date, we actually just need to offset days from the beginning of a year; to offset an arbitrary date, we just need to add the right number of days to that amount.

For example, January 2nd is actually 1 day after the beginning of the year. Note that the days from the beginning of the year is actually one less than the day-of-year, since January 2nd is day 2 of the year, but 1 day from the beginning of the year. If we wanted to compute an offset N from January 2nd, we could just add N + 1 to the beginning of the year instead.

So, to formalise our offsetting algorithm, we start with a year and a number of days. We combine these two values to get a year and day-of-year which constitute that number of days from the beginning of the given year.

The next part is relatively straightforward. First, we leverage the fact that our calendar is cyclic, since everything repeats every 400 years (or 4 years, in the case of the Julian calendar). We reset our year back to the beginning of this loop, so that if we add multiples of 400 years, 100 years, or 4 years, we advance a known number of leap years.

Since this might be difficult to conceptualise, we’ll use 1900 as an example starting date. The algorithm goes like this:

1. The previous multiple of 400 is 1600, so, we might want to start there. But, that year is actually the exception for our weird leap-year-cycle, and it’ll make calculations weird. Instead, let’s reset back to 1601.

2. Since we’re resetting to one past the previous multiple of 400. We’ll need to add the right number of days that let us convert our year from 1900 to 1601. This is a loose end we’ll have to account for later; ignore it for now.

3. Now, because we’re aligned to a multiple of 400 (albeit, off by 1 year), we can compute the exact number of days in this 400-year cycle and remove those multiples from our offset. We know that this cycle will have 365 × 400 regular days and 97 leap days. In the case of 1600 as our starting year, we know that if we advanced 400 years, every fourth year would be a leap year except 1700, 1800, and 1900, but not 2000. That gives us 400 / 4 = 100 and 100 – 3 = 97.

4. So, just to recap: we divide our offset by the number of 400-year cycles and add that many multiples of 400 years. We keep the remainder afterwards and process that next.

5. Now, we’re still one past a multiple of 400 years, and we know that there are less than 400 years left in our offset. Conveniently, this is also one past a multiple of 100 years, and we can process the next part. We know that every single time we advance by a multiple of 100 years, that multiple of 100 won’t be divisible by 400, since our offset can’t get us that far. So, it must contain exactly 24 leap days; 100 / 4 = 25, and 25 – 1 exception = 24.

6. We do a similar thing for those multiples of 100, like we did with 400. The end result is one past a multiple of 100, and less than 100 years’ worth in our offset.

7. Now, we do the same thing with multiples of 4 years. Since we’re less than 100 years left, every single one of these cycles will contain exactly one leap year. We continue like we’ve been doing and remove these cycles from the offset.

8. By this point, you might be thinking: hang on. We’re not at the beginning of our cycle; we’re one year off. So, let’s say that we’re on the 100-year step. What if we add 99 years? Won’t we still need to account for that exception?

9. In this case, we actually don’t have to worry about our exception! The final year after all the computations might be a weird exception year, but since we’re not going past the end of the year, we don’t care whether it’s a leap year or not. Good question, hypothetical person!

10. Anyway, after we’ve added our leap-cycles all the way up to multiples of 4, our last remaining offset may contain some full years. We know that these are not leap years by our previous rules, so, we just remove multiples of 365 from our offset.

11. And… we’re done? We’re left with an offset under 365 days and a year.

You might have noticed something strange on that last point: we can’t ever land on day 366. That would be December 31st on a leap year. There’s something off about our algorithm, and we need to fix it.

The solutions lies in the way we handle division and negative offsets. In general, most programming languages have settled on truncating division, which means that division always rounds toward zero, and the remainder shares the same sign. This allows us to solve a potential problem: when adding our offsets, we always assumed that we kept moving in the same direction; if we were to add multiples of 100 and then subtract multiples of 4, we could jump back over one of those weird exception years.

So, there are actually two changes we need to make things work. The first thing to note is actually how we round the starting year. If we’re adding days to our year, we want to start at one after a multiple of 400; if we’re subtracting, we want to leave this as-is. Since we might want to move around this multiple, it’s a good idea to just reset to a multiple of 400 and then shift around to make things work.

So, our beginning bit actually has a bit of extra logic. First, we reset to a multiple of 400 and add the right number of days to our offset. (don’t worry; we’ll elaborate on this soon)

1. If our offset is less than 366 days in magnitude, shifting the year will actually affect the sign of the offset and we won’t be able to pick the right side of our cycle. So, we can just handle this case manually since it’s not hard: if the offset is positive, we have a valid date, and if it’s negative, just bump the year down and add 365 days to our offset; the previous year is always a non-leap year.

2. If our offset is 366 days or greater, we subtract 366 from our offset and bump the year up by 1. All of our previous calculations should work out until the end.

3. If our offset is -365 days or less, we leave it as-is. Remember that when we’re moving backwards from a leap year, the actual calculations only care if the previous year is a leap year. All of our calculations should work out until the end, but we’ll have an extra step to do if the remainder at the end is negative.

At the very end, if we have a negative offset, we need to convert it into a positive one. Since the previous year may or may not be a leap year, we have to check, add 365 or 366 days accordingly, and bump the year down. We now have a positive offset.

And remember: the offset at the end is the number of days from the beginning of the year, not the day-of-year. We have to add one to this number to get the actual day-of-year, and then we can convert this into a month-day if desired.

### Counting leaps

There was one loose end in our previous algorithm, which actually solves an extra problem in its own right: how many days lie between two given dates? Again, if we ignore the day-of-year and just think of the years alone, we want to find the number of days to move from one year to another.

This algorithm is something called anti-symmetric, since swapping our years will negate the result: if it takes N days to jump from year X to year Y, then it takes -N days to jump from year Y to year X.

This algorithm was actually painful for me to figure out, but I finally did it. We’re going to talk about the simple, Julian calendar case first, and then figure out how we can extrapolate this to the Gregorian calendar.

So, given a year end and start, we’re conceptually subtracting end – start, except we’re getting a number of days, not years. To make things easier, we’ll assume that start < end; if they’re not, we just swap them before doing the calculation and negate the result, since we know that our algorithm is anti-symmetric.

To recap: our algorithm takes a start and end year, and returns the number of leap days required to offset the beginning of start to the beginning of end. We can compute the number of non-leap days separately. Here’s the algorithm:

1. Keep track of the sign of the result; we use the signum function for this to preserve a particularly useful property: if start and end are the same, the result should still be zero. The sign value will be the signum of end minus start, which is -1 if end < start, 0 if end = start, and 1 if end > start.

2. Now that we know the sign, we want to ensure that startend. So, if end < start, swap start and end. This will be important for the next step.

3. Keep track of the “full” cycles between start and end; this is end minus start, divided by the cycle length, which is 4 in this case.

4. Add those full cycles to start; that is, take the above, multiplied by the cycle length, and add it to start. After this, the distance between start and end will be less than the cycle length.

5. If start and end are the same now, we can just quit out and return the above times our sign.

6. Now, even though there isn’t a full cycle between start and end, there could still be a multiple of the cycle length here. For example, year 4 exists between years 3 and 5, even though 5 – 3 < 4.

7. We can use the modulo operator here to help check whether we’re straddling this boundary. Take the start modulo the cycle length, and then end modulo the cycle length. Here, we have to actually use the Euclidean modulo, which ensures that the result is always positive. Mark these down as the end bit and the start bit.

8. Now, the logic for the above is a bit complicated. If the end bit is less than the start bit and the end bit isn’t zero, that means that there’s an “extra” multiple between the two that isn’t end. However, if the start bit is zero, that also means there’s an “extra”. So, the full logic is: either the start bit is zero, or the end bit isn’t zero and the end bit is less than the start bit.

9. Now that we’ve computed both the “full” cycle count and the “extra” cycle count, add these two together and multiply by the sign. This is the number of “leap days” between the two.

Now, for the Julian calendar, this is pretty simple: just plug in 4 for the cycle length, and we’re done. But for the Gregorian calendar, we need to perform this calculation separately for 400, 100, and 4; we add the amounts for 4 and 400, but subtract the amount for 100. After we’re done with our leap day counts, we can just add the regular days, which is end minus start times 365.

Again, if we want to compute the offset between any two dates, and not just January 1st, we can subtract the days-of-year and add that to our offset. However, without worrying about full date subtraction, this algorithm is useful for the first step of our regular date-offsetting algorithm, since we need to offset our year to that nice multiple of 400.

With the above two algorithms, and the knowledge that the Julian and Gregorian calendars are two additional days apart, you can actually create a completely functional calendar conversion algorithm.

However, as you can assume by the length of this article… there are going to be mistakes. And one resource I’ve found invaluable for checking these is actually a table from a particular source: “Explanatory Supplement to the Astronomical Ephemeris and the American Ephemeris and Nautical Almanac,” Her Majesty’s Stationery Office, 1961. Specifically, this table is on page 417, and you can find it on archive.org here. It provides a plethora of equivalences between the Gregorian and Julian calendars, including Greg’s Big Day (and a few days after), alongside various dates around the end of February going from -500 to 2100. It’s an invaluable resource, and matching the table has been my benchmark for the algorithms working correctly.

## Conclusions

Honestly, working with dates is terrible, and I don’t recommend it.

But, if you were here for a nice explanation on how this all actually works, and if you were actually as frustrated with the existing material as I was… wish granted.

I don’t actually have a good conclusion for this, but the post is over. Bye.

## Corrections

So, I posted this article initially late at night, and made a few mistakes. At the time of writing, my code also was broken, and I finally got around to figuring out what was wrong. So, I’ve listed the corrections I’ve made here for posterity. They’ve already been updated in the actual article text.

1. I accidentally negated the offset between the Gregorian and Julian calendars. This means that January 1 BCE on the Gregorian calendar is equivalent to January 3 BCE on the Julian calendar, not the other way around. Although dates on the Gregorian calendar are larger than ones on the Julian calendar today, the gap isn’t as extreme as you’d expect because the Julian calendar is actually ahead of the Gregorian calendar in the first few years.

2. In the initial year offsetting, while you do want to push positive offsets to one past a multiple of 400, for negative offsets, you actually just want to leave them alone, instead of going one before a multiple of 400. This is because, as I’ve even mentioned in this article, going backwards only factors in leap years before the current year. For example, when going from year 2000, January 1st to year 1999, December 31st, you only care that 1999 isn’t a leap year, not that 2000 is.

3. For the year differencing, I actually messed up a lot after the first version of this article. The final logic that factors in the start year modulo the cycle length and the end year modulo the cycle length isn’t simple, but should be relatively straightforward since you only have to do the divisions once.

4. I added in a note about the resource I’ve been using for testing that my date conversions are correct, which has proven invaluable.