|
Is it Turbo Pascal's modulus operator that's been giving Jeff's day-of-the-week function fits? What would Zeller have to say about that!
November 01, 1990
URL:http://www.drdobbs.com/tools/structured-programming/184408450
Be careful what you ask for, children: You might get it.
Consider: It's hot out here in North Phoenix, so hot that by August the swimming pools have become too warm to be refreshing. The best you can do is jump in and jump immediately out again in the hope that the single-digit humidity will cool you off by rapid evaporation. If you have a solar pool-heating system, you can cool the water by running it at night, so that the hot water warms the panels and radiates heat into the clear desert midnight sky.
No such luck here until we move into our new house, and by then summer will be little more than a memory with smoke wafting off of it. So when I mailed invitations to one of our regular parties, I made it plain to our guests: The pool temperature had gone over 90 degrees, and if it got any hotter I'd have to throw some ice cubes into it.
It was 105 degrees the afternoon of the party, and no one was in the pool. Come seven PM, we had finished dinner and were talking hacker-talk out on the patio. The wind was rising sharply, and we saw the flashes of distant lightning in the north. Low clouds rolled over the sun, and behind them came roiling clouds of red dust from the desert just north of town.
The storm hit like a hammer, taking the temperature from 105 down to 75 almost instantly, with continuous lightning and winds gusting to 70 miles per hour amidst torrential rain. Then, as though that weren't enough, it started to hail.
Big chunks of ice riding a 70 mph wind are lethal missiles. We tumbled inside and watched in amazement as the storm poured wave after wave of hailstones, some rivaling golf balls, into the yard. Ten minutes later, there were hailstone drifts three inches deep beside the fence, and a thick layer of hailstones bobbed steaming in our pool.
Out in front, 10th Avenue was a river, carrying broken tree branches and fragments of redwood fence. Power was out for most of the night.
But I had managed to get some ice into the pool.
Similarly, I got what I asked for -- and then some -- when I swore up and down that I would figure out what was eating my day-of-the-week function, CalcDayOfWeek. Part of that adventure was detailed last month, in my recreation of a Pascal and Modula-2 implementation of Zeller's Congruence from the original source, a scholarly paper that Zeller published in 1887. (Zeller's Congruence, in case you're just tuning in, is an algorithm that calculates the day of the week, given the year, month, and day.)
I left you with an implementation that worked fine. There was a worm in it, though: In order to make the algorithm return correct dates in all cases, I had to ensure that Turbo Pascal's MOD operator never acted upon a negative quantity. In other words, rather than evaluate -17 MOD 7, I added 7 repeatedly to -17 until the sum surfaced on the plus side of zero. That quantity then became the first operand of the MOD operator. (See last month's code listings if you don't quite see what I mean.) This is a kluge by the classic definition, which is to say, something that works right for all the wrong reasons. (And the wrongest reason of all is not having any idea whatsoever why it works right!)
I'd heard whispers for years that Turbo Pascal's X MOD Y operator wasn't quite kosher, but nobody I knew could define just what was wrong with it. All my tests indicated that it did just what the modulus operation was supposed to do: Calculate an integer division of the first operand by the second, then return the remainder of that division. The dividend is thrown away unused. (That's what the X DIV Y operator is for.) No matter what combination of positive and negative integers I used, every calculation agreed with my pains-taking pencil-and-paper work. (How many pocket calculators will show you a remainder? Not mine....) I began to consign those rumors of MOD's incompetence to base canards, but then a disturbing possibility turned up out of a conversation in the mathematics conference on BIX: That the way Turbo Pascal and I understood the modulus operator was subtly but ruinously different from the way the mathematics community -- and hence Zeller himself -- understood it.
My head first started to spin when someone known to me only as "seba" posted the following definition for the modulus operator:
where [X/Y] is the greatest integer less than or equal to X/Y. This sure didn't look like taking the remainder and tossing the dividend, and it sure wasn't. I first implemented this equation the following way:
This, again, worked for positive values of X but not for negative values. After considerable head scratching, I realized that truncating a real number value such as that produced by X/Y always moves the value toward zero on the number line. This is fine for positive values, but for negative values, moving toward zero makes the value greater than X/Y rather than less. Implementing the equation for negative values has to be done this way:
Decrementing the value of the expression X/Y by one ensures that truncating the expression returns the largest integer less than X/Y.
Combining the two cases into one Modulus function is easy, and the result is the function given in Listing One (page 167).
If you have yet to grok the fullness of this new equation describing the modulus operator, have faith -- I trust it because it works, not because it's "obvious" to me. For it to become obvious, I have to look to a graphical interpretation of the modulus operator, something I learned in eighth grade during a brief brush with the New Math Monster and haven't thought about since 1966. To implement the modulus operator graphically, follow the example shown in Figure 1. To take N modulus Y, draw a circle of digits starting from O and running to Y-1. In Figure 1, I'm setting up the circle to take N modulus 7, as required by Zeller's Congruence.
With the circle in place, start at 0 and count around the circle by N positions. (Tap each digit with a pencil eraser if you have to -- I did, and I won't laugh if you do too.) Here's the kicker: If N is positive, move around the circle in a clockwise direction. If N is negative, move around the circle in a counterclockwise direction. Try it right now with the numbers 17 (clockwise) and -17 (counterclockwise.) Your answers should be:
Note that I didn't call the operator MOD. By now it was clear to me that MOD and modulus are two different operators. Turbo Pascal and Turbo C++ calculate 17 modulus 7 = 3 but -17 modulus 7 = -3. In all cases, -N MOD Y is simply - (N MOD Y), which is what you would expect if MOD returns the remainder of a simple division. Unfortunately, what we call MOD Zeller would have called the remainder function. And that in a nutshell was what was wrong with CalcDayOfWeek. (The final implementation of CalcDayOfWeek using Zeller's Congruence is given in Listing Two, page 167.) It wasn't really a bug in Turbo Pascal. What TP calls MOD is really the remainder function, and if what you need is the remainder function it will work without a hitch every time.
However, if you've ever implemented an algorithm from the literature of mathematics that calls for the modulus operator and used MOD, your algorithm will go wonky any time the first operand of modulus goes negative. Check it out. Now. I suspect the problem may be present in many more compilers than Borland's. If you're not using Turbo Pascal, bring up your compiler and evaluate -17 MOD 7. If you get anything but 4, you've got remainder or something else, not true modulus.
Thus ends the tale of what is certainly the most amazing single bug in my very full notebook of bug hunts.
Sometimes you wonder why it takes as long as it does for certain new products to appear. Ever since Borland first released the BGI with Turbo Pascal 4.0, there's been this gaping hole in BGI functionality: hardcopy. While numerous utilities exist to zip a displayed graphics screen out to the printer, this requires that the graphics image first appear on the screen. If you want to use the screen for something else, you're simply out of luck.
Enter Graf/Drive Plus from Fleming Software. The notion is elegant: A BGI driver that sends' BGI output to a hardcopy device rather than a video device. In other words, rather than load a driver for the EGA or Hercules graphics adapters, you load a driver for the Epson or LaserJet printers or one of the supported HP plotters. Then, when you execute a standard BGI statement such as Circle or OutTextXY, the graphics go to paper rather than to the screen.
All BGI functions that make sense for hardcopy are supported. (Those that don't are things such as GetImage, Put-Image, and palette control routines.) The package works with Turbo Pascal (5.x), Turbo C 2.0, and Turbo C++ 1.0. Printers currently supported are the HP LaserJet series, Epson MX/FX 80 and compatibles, the Epson LQ1500 and compatibles, and the HP 7470A and 7475A pen plotters. Several new printers will be supported by the time you read this, including PostScript, the HP PaintJet, the HP7585 plotter, and the Toshiba and IBM QuietWriter printers.
Graf/Drive Plus does exactly what it says it does. I've had no trouble making it work and can trace no crashes or other bugs to its use. The individual drivers are fairly small (less than 16K) and can be linked into your .EXE image just as any BGI driver can be. The hacking-around license is $149; if you purchase a developers' license ($299) you can distribute the drivers with your application without further royalty obligations.
Lord knows, something like this should have been done years ago. Highly recommended.
A lot of developers don't go to Comdex anymore. They say, rightfully, that it's a hardware show, but that's all the more reason to hock your firstborn and truck on out there. For the little guy, it's a niche-filler's game these days, and you have to remember that a software niche is an idea delimited by available hardware. And the one thing a lone wolf can do better than all the armies of IBM is have ideas.
It happens to me every year: I prowl the aisles (especially in the third-tier hotels where the weird stuff ends up) and wait for the hardware on display to suggest new applications to me. I'm in the magazine business rather than the software business these days, but the ideas come nonetheless. And sometimes the triggering products are not even "hardware" in the familiar sense: Last year I saw a firm dealing in customperfed sheets of paper for computer printed tear-out coupons, and I had this notion that I could create custom sheets punched and perfed to tear down into pages for the smallest standard pocket memo book, which is something only a little larger than your average business card. Feed 10 or 12 sheets through your laser printer with the proper software interface to your contacts database (including an eight-point font) and bang! A little little black book!
The problem of marketing your software still remains (looming larger than ever, in fact) but having ideas that nobody else has had is often no harder than getting out and exposing yourself to large quantities of the stuff of which our industry is made.
Graf/Drive Plus Fleming Software P.O. Box 528 Oakton, VA 22124 703-591-6451 Personal License: $149 Developers' license: $299
After all, lots of people find that pacing around the room helps shake ideas loose. At Comdex, you can pace around some of the largest rooms in the civilized universe, (in fact, to see it all you'd better pace at something close to a dead run) surrounded by the largest concentration of computer stuff that ever happens anywhere.
If you can't get ideas there, you might as well go back to selling shower curtains.
_STRUCTURED PROGRAMMING COLUMN_
by Jeff Duntemann
[LISTING ONE]
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.
Modulus Vobiscum
Which Way is the Floor?
X MOD Y = X-Y*[X/Y]
X-(Y*Trunc(X/Y))
X- (Y*Trunc((X/Y) -1))
Modulus Roulette
17 modulus 7 = 3 -17 modulus 7 = 4.
BGI Hardcopy
Comdex Approaches
Products Mentioned
FUNCTION Modulus(X,Y : Integer) : Integer;
VAR
R : Real;
BEGIN
R := X/Y;
IF R < 0 THEN
Modulus := X-(Y*Trunc(R-1))
ELSE
Modulus := X-(Y*Trunc(R));
END;
[LISTING TWO]
PROGRAM ZelTest2; { From DDJ 11/90 }
CONST
DayStrings : ARRAY[0..6] OF STRING =
('Sunday','Monday','Tuesday','Wednesday','Thursday','Friday','Saturday');
VAR
Month, Day, Year : Integer;
{ This function implements true modulus, rather than }
{ the remainder function as implemented in MOD. }
FUNCTION Modulus(X,Y : Integer) : Integer;
VAR
R : Real;
BEGIN
R := X/Y;
IF R < 0 THEN
Modulus := X-(Y*Trunc(R-1))
ELSE
Modulus := X-(Y*Trunc(R));
END;
FUNCTION CalcDayOfWeek(Year,Month,Day : Integer) : Integer;
VAR
Century,Holder : Integer;
BEGIN
{ First test for error conditions on input values: }
IF (Year < 0) OR
(Month < 1) OR (Month > 12) OR
(Day < 1) OR (Day > 31) THEN
CalcDayOfWeek := -1 { Return -1 to indicate an error }
ELSE
{ Do the Zeller's Congruence calculation as Zeller himself }
{ described it in "Acta Mathematica" #7, Stockhold, 1887. }
BEGIN
{ First we separate out the year and the century figures: }
Century := Year DIV 100;
Year := Year MOD 100;
{ Next we adjust the month such that March remains month #3, }
{ but that January and February are months #13 and #14, }
{ *but of the previous year*: }
IF Month < 3 THEN
BEGIN
Inc(Month,12);
IF Year > 0 THEN Dec(Year,1) { The year before 2000 is }
ELSE { 1999, not 20-1... }
BEGIN
Year := 99;
Dec(Century);
END
END;
{ Here's Zeller's seminal black magic: }
Holder := Day; { Start with the day of month }
Holder := Holder + (((Month+1) * 26) DIV 10); { Calc the increment }
Holder := Holder + Year; { Add in the year }
Holder := Holder + (Year DIV 4); { Correct for leap years }
Holder := Holder + (Century DIV 4); { Correct for century years }
Holder := Holder - Century - Century; { DON'T KNOW WHY HE DID THIS! }
Holder := Modulus(Holder,7); { Take Holder modulus 7 }
{ Here we "wrap" Saturday around to be the last day: }
IF Holder = 0 THEN Holder := 7;
{ Zeller kept the Sunday = 1 origin; computer weenies prefer to }
{ start everything with 0, so here's a 20th century kludge: }
Dec(Holder);
CalcDayOfWeek := Holder; { Return the end product! }
END;
END;
BEGIN
Write('Month (1-12): '); Readln(Month);
Write('Day (1-31): '); Readln(Day);
Write('Year : '); Readln(Year);
Writeln('The day of the week is ',
DayStrings[CalcDayOfWeek(Year,Month,Day)]);
Readln;
END.