Elegant Inelegance: Algorithm 199

I recently experimented with JSR-310’s LocalDate class (v0.6.3). I found it a little slow mainly because it computes the Julian date on the fly, which does not suit my application. So unfortunately I started to roll my own LocalDate, preserving as much as possible the JSR-310’s API. When it came to implement a conversion from yyyy-mm-dd to a serial number I hoped I could find something smaller and faster than typical implementations of Julian date. Working in computational finance I only needed a serial date for a few hundred years. During my search I stumbled across “Date Manipulations in WFL” by Paul Kimpel. Tucked away at the back of the document was an excellent explanation of the workings of Robert Tantzen’s “Algorithm 199: Conversions Between Calendar Date and Julian Day Number”, Communications of the ACM, Vol. 8, August 1963, p444. After reading it, I realised I never really knew how or why Julian date algorithms worked, and more worryingly I had never stopped to investigate!!

It was intriguing, given the awkwardness of dates, some months 30 days, others 31 days, February 28 days except sometimes 29 dates etc, how does one convert from yyyy-mm-dd to serial number and back? Surely it had to be some awkward algorithm involving table lookups, yet somehow in the code there is a formula involving 1461 and 153m+2…

The first important step is the leap period, it’s the first glimpse of a pattern amongst the uneven dates. There is a natural cycle of 1461=365+365+365+366 days, and for convenience we choose to leave the leap day 29-Feb to end of the cycle. Now focusing on the serial dates within a 365-day year starting from March, one can determine mathematically that the straight line,

provides a very close fit to the serial number and the month number. However, one is only interested in values of j at m=0,1,2,…,11 and the values of m at j=0,1,..,365, so consider integer arithmetic, not least because it would likely be faster to execute. First reduce the truncation error by scaling by 5, that is, 5j=153.0007m + 0.1282. In integer arithmetic, j=(153m+0)/5 would seem a reasonable guess, but it does not quite work. However,

works perfectly, the inelegant round off and integer truncation works in such a way as to exactly match the slightly uneven serial number to month number function. This is the elegant part of Algorithm 199 explained by Paul Kimpel.

The transformation, j=(153m+2)/5 is not unique, for example j=(306m+5)/10 would also work. Since it is integer arithmetic, it might be judicious to seek a divisor that is a power of 2. One such transformation is,

(actually, replacing 15 by 16, 17, 18 or 19 will also work). The inverse is computed by m=(5*j-3)/153 (or m=(32*j-16)/979).