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;
Advertisements

About mischasan

I've had the privilege to work in a field where abstract thinking has concrete value. That applies at the macro level --- optimizing actions on terabyte database --- or the micro level --- fast parallel string searches in memory. You can find my documents on production-system radix sort (NOT just for academics!) and some neat little tricks for developers, on my blog https://mischasan.wordpress.com My e-mail sig (since 1976): Engineers think equations approximate reality. Physicists think reality approximates the equations. Mathematicians never make the connection.
This entry was posted in algorithm, Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s