|
June 01, 1995
URL:http://www.drdobbs.com/letters/184409582
Dear DDJ,
Kim Larsen's article "Computing the Day of the Week" (DDJ, April 1995) is a good example of how a simple equation can sometimes replace tedious programming logic. This technique could be used in other applications to reduce code size and increase speed whenever a mathematical formula fits the problem better than a step-by-step algorithm. I especially appreciated Larsen's description of how this particular formula was developed.
Larsen made no mention of Zeller's Congruence. Zeller's Congruence is another formula for calculating the day of the week. It was published in 1887 by the German mathematician Zeller. Jeff Duntemann discussed Zeller's Congruence in issue #169 of DDJ, with some follow-up information in issues 170 and 171.
Like Larsen, Zeller reckoned January and February as the 13th and 14th months of the previous year. However, he then divided the year into two components: the century (C=Y/100) and the year within the century (Y mod 100). He probably did this to keep all the numbers small (they didn't have ten-digit calculators back then). After calculating C as Y/100 and adjusting Y to Y%100, Zeller's Congruence can be expressed as: A=(D+(M+1)*26/10+Y+Y/4--2*C+C/4)%7.
As with Larsen's formula, all divisions are integer divisions (rounding down). Note that the fraction 26/10 can be reduced to the equivalent 13/5. Zeller probably used 26/10 because it's very easy to divide by 10 when doing arithmetic by hand. One potential pitfall when implementing Zeller's Congruence is that the sum of the individual terms can sometimes be negative. For example, this occurs with the date 1 March 2000 (D=1, M=3, C=20, Y=0).
The formula should work even if the sum is negative, but some compilers give an unexpected result when a negative number is used with the modulo operator. This situation can be easily avoided by replacing the term --2*C with +5*C (to make all the terms positive). Since --2*C and +5*C differ by an exact multiple of 7, this change won't affect the final result modulo 7. These adjustments change the formula to: A=(D+(M+1)*13/5+Y+Y/4+5*C+C/4)%7.
Larsen's formula is virtually identical to Zeller's. Note that the value of Y in Larsen's formula is actually equal to 100*C+Y in Zeller's nomenclature. Making this substitution in Larsen's Y+Y/4--Y/100+Y/400 yields 100*C+Y+25*C+Y/4 --C+C/4. A little massaging will show that this differs from Zeller's Y+Y/4 --2*C+C/4 by 126*C. Since 126*C is a multiple of 7, this difference has no effect on the final result. Likewise, one can show that Larsen's 2*M+3*(M+1)/5 differs from Zeller's (M+1)*26/10 by a constant value of --2. This means that Zeller's Congruence will return 0 for Saturday and 6 for Friday, whereas Larsen's formula uses 0 for Monday and 6 for Sunday. Either formula can be adjusted to start on any day of the week by adding an appropriate constant offset before calculating the result modulo 7.
Larsen's detailed article gives valuable insight into the logic that Zeller must have used when devising his congruence. The description of the inner workings of Larsen's formula is much clearer than the explanations of Zeller's Congruence that I've seen elsewhere. Keep up the good work.
Rod Spade
Lancaster, Pennsylvania
Dear DDJ,
I enjoyed Kim S. Larsen's article because I have been playing with the subject too. I managed to stuff all computation into a single line of code (dayofweek1), which was then improved even further (dayofweek2) by a friend (Hendrik Jan Veenstra). The formulas presented in Example 1 use a table different from the one in the article for adjustment of the correct day.
Frank Bemelman
Dear DDJ,
After reading Kim Larsen's "Computing the Day of the Week," I thought you might be interested in the Day-of-the-Week C macro in Example 2. It returns from 0 (=Monday) to 6 (=Sunday). For reasonable input values, it works with 16-bit ints with no risk for overflow. And the y,m,d are real year, month, day values, not "adjusted" ones: January is m=1, February M=2, March M=3, and so on.
Paul Schlyter
Stockholm, Sweden
Dear DDJ,
The article "Computing the Day of the Week," by Kim S. Larsen, was a fine one. However, I'd like to add a few related observations.
Larsen's statement that "We switched to the current calendar system on Thursday, September 14, 1752" is true in a sense. But the switch was made in European Catholic countries much earlier (in 1582), and in Russia and Greece much later (around 1917)! The "October Revolution" was in November by Gregorian reckoning!
In UNIX, if you enter CAL 9 1752, you get a hybrid calendar; the first two days are Julian, and the rest of the month is Gregorian. The first week of that UNIX display looks like this: 1 2 14 15 16. A clever bit of programming, but be aware of what it means! One thing it means is that UNIX would be wrong in France, Russia, and many other places around the world!
When talking about any particular calendar (Julian, Gregorian, or other), it is helpful to think of it simply as an algorithm in its own right, independent of any concept of time--like a recipe for brownies. In this sense, a calendar does not change, nor does it have a beginning or an end. Only our application of it changes as time goes by.
In this way we should have no difficulty extrapolating any particular calendar algorithm to any year we please. Pope Gregory 13 insisted that his calendar (the one we use now) be phased relative to the Old Style Julian to match up in March 21 ad 325, so it makes sense to use it for reporting historical, as well as future dates from ad 1 until ad 3000 (when it loses accuracy) even if the people in the past didn't. (We can be pretty sure that Julius Caesar never had a calendar on his wall that said "50 bc:" Even so, we can quite reasonably say that he lived from 100--44 bc!)
Thus, even though the Gregorian calendar was not used in America prior to 1752, George Washington wisely reckoned his birthday in terms of it, as we continue to do today. He was born 20 years earlier in Westmoreland County, Virginia. Another thing: The 500th anniversary of Columbus's discovery of America was October 21, 1492 Gregorian--not the 12th. That, is if we can agree that "500 years" means 500 complete revolutions of the Earth about the Sun, without regard for what calendar Columbus might have been using at the time! At least the day of the week is the same; that original Columbus day being a Friday whether you talk Julian or Gregorian.
And when the astronomer says that his "Julian Day" (a different Julius!) relates back to January 1, 4713 bc, he doesn't tell us what calendar he's talking about! What's Latin for "Confusion reigns," anyway?
I also found it interesting to compare Larsen's algorithm with my own. In the October 1989 issue of PC Resource magazine, my short Basic program appeared containing this "Gregorian algorithm" for the day o'week: (Y+Y\4-- Y\100+Y\400+2.6*M+1.2+M)Mod 7. For January or February, use M=13 or 14 of the previous year. In my algorithm, I chose day 0 to be Sunday, not Monday, for a couple of reasons: First, that makes "2'sday" become "Tuesday;" an extremely useful mnemonic. Second, the astronomical symbol for the Sun is 0 (a circle).
With Microsoft GWBASIC 3.22 or other redirectable Basic on path, the next command, when invoked at the DOS prompt, will show the complete calendar for any month and ad year you type in the M=7:Y=1776:N=31 preamble. This command squawks if you try to use M=1 or M=2. Don't use any spaces not shown or it won't fit on the command line: ECHO M=7:Y=1776:N=31:Q=SQR(M--3):FOR J=1TO N:D=(Y+Y\4--Y\100+Y\400+2.6*M+1.2)MOD 7+J:LOCATE D\7+6,3*(D MOD 7)+3:?J:NEXT|GWBASIC.
Homer B. Tilton
Tucson, Arizona
Dear DDJ,
As leaders in the numerical computing industry, Cray Research appreciates the focus that your magazine brought to this important topic in the January 1995 DDJ "Tools that Count" issue. In the "Examining Room," Steven Baker reviewed several Fortran 90 compilers and test suites. As the producer of one of the test suites and compilers, we would like clarify a few points as they relate to our products.
Baker writes that "_the Cray, (and others)_compilers failed to recognize and report the obsolete features as required by the Fortran standard." There is a command-line option which will enable the generation of messages to note all nonstandard usage, including obsolete features. This option is off by default and would have to be specifically enabled to generate the report.
In Baker's "Other Considerations," it appears that the CraySoft compiler was dropped from consideration, leaving the implication that it does not come with a complete programming environment or supported extensions. In fact, the CraySoft Fortran 90 environment automatically optimizes for parallel processing and includes a parallel debugger, a source-code browser, a parallel performance analyzer, and other development tools; it supports Cray and VAX extensions.
In his Table 1, Baker publishes only the pass rates from selected portions of the various suites, which does not yield an accurate measure of the robustness and quality of the compilers being "evaluated." There was also apparently no analysis of specific failing tests. It is very likely that a single bug or a differing interpretation of the standard could cause multiple failures in a given test suite. Unfortunately, Mr. Baker's own caution about his analysis, that the "_results from these validation suites should be taken with a grain of salt," is not nearly as prominent.
Judy Smith
CraySoft Product Development
Eagan, Minnesota
Net Stuff
Dear DDJ
I think Jonathan Erickson's editorial "The Green, Green Cash of Gnomes" (DDJ, April 1995) was pretty cool, and I just wanted to let you guys know. I've subscribed to DDJ for a couple years now, I guess, and it's one of the few trade magazines I've kept. I've kept it because of honest editorials about the crap that goes on in the industry, as well as the useful technical information. Anyway, like most software engineers, I'm using online resources, particularly the Internet, more and more as part of my job. I cringe whenever I hear someone mention the words "regulation" and "Internet" in the same sentence. Erickson's editorial reminded me that if we sit back and let the government and the marketing bozos overrun the Net, we've only got ourselves to blame through our inaction. So anyway, keep telling it like it is, guys, and we'll keep reading.
Dale M. Davis
Sunnyvale, California
Dear DDJ,
Please allow me to poke two-cents' worth at Michael Swaine's "mechanical model" in his "Programming Paradigms" (DDJ, October 1994). Michael asserts: "There's precious little that we might consider the mind capable of doing that we can't convince ourselves that software can also do, in principle."
I'm afraid this is false. My counter-example is this: the invention of natural language. Programs that speak English do exist, but most could be improved. Programs that can learn to speak English are, so far as I know, still glued to the drawing board. Programs that can invent new languages as powerful as English do not exist.
Further, if such program did exist, what would be the guarantee that any human could learn the languages that it "spoke," or even recognize them as languages? If these things could be guaranteed, we would be inclined to ascribe the invention to the programmer(s), not the program.
I could push this argument a good deal further, but that will do for two cents. I hope I have said enough to convince a few people that the equation "mind=software" is a vague analogy which dissolves into large and unsolved problems if you look closely.
Thanks for the stimulus of a magazine that still manages to include technical, philosophical, and commercial information all at once.
I.K. Sayer
Smithton, Tasmania
Australia
#include <stdio.h>
#endif
/* This table starts on Sunday !!! */
char *name[] = { "Sunday",
"Monday",
"Tuesday",
"Wednesday",
"Thursday",
"Friday",
"Saturday",
};
void main(void)
{ int D,M,Y,A;
D=3; M=3; Y=1995;
printf("formula1, day=%s\n",name[dayofweek1(D, M, Y)]);
printf("formula2, day=%s\n",name[dayofweek1(D, M, Y)]);
}
int dayofweek1(int d, int m, int y)
{ return(((d+((26*((m<3)?m+13:m+1))/10)+((125*(long)((m<3)?y-1:y))/100)
-(((m<3)?y-1:y)/100)+(((m<3)?y-1:y)/400))-1)%7);
}
int dayofweek2(int d, int m, int y)
{ return((d+(int)((1040*(long)((m<3)?m+13:m+1))+
(597*(long)((m<3)?y-1:y))/400))%7);
}
/* Day-Of-Week macro for international Monday-Sunday calendars */
#define dow(y,m,d) \
( ( ( 3*(y) - (7*((y)+((m)+9)/12))/4 + (23*(m))/9 + (d) + 2 \
+ (((y)-((m)<3))/100+1) * 3 / 4 - 16 ) % 7 ) )
Copyright © 1995, Dr. Dobb's Journal
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.