## Solving a little problem discretely

CS 101 problem: calculate the number of days between two dates, accounting for leap years, etc. You’ve probably done or seen the answer, and it involves a look-up table for numbers of days per month, and probably a loop. Not a deep problem, and probably every CS undergrad’s introduction to the very basics of “business application programming”.

But there’s nothing clever, let alone efficient about it (oh, alright, efficiency probably doesn’t count for much on this scale). So naturally, I started looking for another way. For month (m), are there numbers (A,B) such that floor(m*A/B) gives you the number of days in that month?

If the months of the year strictly alternated 31,30,31,30,… days, it would be obvious: a month takes 30.5 days, and you start at 0.5, truncating the result to an integer. This works perfectly if the year were to start March 1,as it did when Julius Caesar came up with this calendar. A trivial tweak of (y,m) makes the “year” start with March as month 0.

But there is another  little hiccup: Jul/Aug and Dec/Jan, six months apart,  need an extra .5 days added. How about a linear solution to that?

To add an extra half-day every six months, but not every five months, means adding some fraction between 1/12 and 1/10 per month. Here the bit-twiddler in me cries out: I hate doing division if it’s not by a power of two. Simple trial and error eliminates 4, 8, 16 as denominators; but 3/32 falls into the range we want. So our linear “month” will have 30.5 +3/32 = 979/32 days.

So here’s the code to compute ordinals starting at 0, for any date between Mar 1, 1900 and Feb 28, 2100. Beyond that requires adjusting for centuries and quadricentennials. I plan on getting to that, in early 2100.

```int ymd2date(y,m,d)
{
if (m > 2) m -= 3; else m += 9, --y;
return y*1461/4 + (m*979 + 17)/32 + d - 693976;
}```

The above compiles to about 10 machine instructions, with one conditional branch. The reverse is only a bit more complicated:

```dnum += 693976;
y = (dnum * 4 - 1) / 1461;
m = (dnum * 32 - 17) / 979;
d = (dnum - (m * 979 + 17) / 32;
if (m > 9) m -= 9, ++y; else m += 3;``` 