C track: assignment 2


Goals

In this assignment you will write a more substantial program and learn some new language constructs.

Language concepts covered this week

Other concepts covered this week

Reading

Read this page to familiarize yourself with the make program and Makefiles.

Also take a look at our C style guide. Starting from this lab, I'll be more picky about style issues.

Operators and operator precedence in C

An "operator" is a character or character sequence that has a special syntactic meaning to the C compiler. Most operators are binary, which means that they are found sandwiched between two values. An example is the addition operator, +, which is found in expressions such as 1 + 2. Some operators are unary, such as the bitwise-NOT operator (~). One operator is actually trinary (the dreaded   ? :   operator), but we won't discuss it here. Compared to most languages, C has a very large number of operators and a correspondingly large number of operator precedence levels (15 of them to be precise; see table 2-1 in K&R if you're curious). Operator precedence levels determine how to interpret expressions with multiple operators. For instance,

    a = b + c * d + e;

is interpreted as being

    a = b + (c * d) + e;

because multiplication has higher precedence than addition. If we want it to be interpreted differently, we need to use parentheses, e.g.

    a = (b + c) * (d + e);

Note that the = sign is also an operator (the assignment operator). It has very low precedence, so we don't need to use parentheses around the arithmetic expression to the right of the = sign. Also note that (confusingly) equality testing uses the == operator, not the = operator.

We do not want you to memorize the operator precedence table! Instead, simply use these three rules:

  1. Multiplication and division have precedence over addition and subtraction;
  2. All assignment operators (except for ++ and --) have extremely low precedence;
  3. Put parentheses around everything else where there is any possibility of confusion.

Also note that C has a lot of shortcut assignment operators:

Used judiciously, they often result in more concise and understandable code. An annoying fact is that the ++ and -- operators have a very high precedence, whereas all the other assignment operators have the same precedence as = does.

Program to write

You will write a program called easter that will compute the day of the year on which Easter falls, given the year.

Description of the algorithm

This algorithm is taken from Donald Knuth's famous book The Art of Computer Programming (see the references below).

    GIVEN:   Y: the year for which the date of Easter is to be determined.
    FIND:    The date (month and day) of Easter

    STEP E1: Set G to (Y mod 19) + 1.
             [G is the "golden year" in the 19-year Metonic cycle.]
    STEP E2: Set C to (Y / 100) + 1. [C is the century]
    STEP E3: Set X to (3C / 4) - 12. [X is the skipped leap years.]
             Set Z to ((8C + 5) / 25) - 5.
             [Z is a correction factor for the moon's orbit.]
    STEP E4: Set D to (5Y / 4) - X - 10.
             [March ((-D) mod 7 + 7) is a Sunday.]
    STEP E5: Set E to (11G + 20 + Z - X) mod 30.
             If E is 25 and G is greater than 11 or if E is 24,
             increment E.
             [E is the "epact" which specifies when a full moon occurs.]
    STEP E6: Set N to 44 - E.  [March N is a "calendar full moon".]
             If N is less than 21 then add 30 to N.
    STEP E7: Set N to N + 7 - ((D + N) mod 7).
             [N is a Sunday after full moon.]
    STEP E8: If N > 31 the date is APRIL (N - 31),
             otherwise the date is MARCH N.

Note: all divisions in this algorithm are integer divisions, which means that any fractional remainders are thrown away. Also, the comment "March ((-D) mod 7 + 7) is a Sunday" is technically only true for years after 1752, because there was an 11-day correction applied to the calendar in September of 1752. You don't need to mention this in your comments, since it doesn't affect the Easter computation.

Note 2: We will be adding another step to make the algorithm work nicely with our C program; see the description of the program below for more details.

Note 3: Just because the great Don Knuth wrote this algorithm this way doesn't mean that it's written in a nice or easy-to-understand way. In particular, the use of single characters as variable names is usually a very bad idea (because single characters don't have any meaning to the person reading the code), and we don't want you to do that in this program. Knuth was trying to describe the algorithm in as short a space as possible; you don't have that restriction.

Explanation of the algorithm

Ever wonder what those monks did during the Dark Ages, all secluded away in their distant mountaintop monasteries and things? Well, it turns out that they were busy calculating the date of Easter. See, even back then, there wasn't much point in spending any effort on calculating the dates of holidays like Christmas, which as everyone knows, is on the same day each year. That also went for holidays which have become a tad more obscure, like Assumption (August 15th).

But the trouble with Easter is that it has to fall on Sunday. I mean, if you don't have that, all the other non-fixed holidays get all screwed up. Who ever heard of having Ash Wednesday on a Saturday, or Good Friday on Thursday? If the Christian church had gone and made a foolish mistake like that, they'd have been the laughingstock of all the other major religions everywhere.

So the Church leaders hemmed and hawwed and finally defined Easter to fall on the first Sunday after the first full moon after the vernal equinox.

I guess that edict must not have been too well-received, or something, because they then went on to define the vernal equinox as March 21st, which simplified matters quite a bit, since the astronomers of the time weren't really sure that they were up to the task of finding the date of the real vernal equinox for any given year other than the current one, and often not even that. So far so good.

The tricky part all comes from this business about the full moon. The astronomers of the time weren't too great at predicting that either, though usually they could get it right to within a reasonable amount, if you didn't want a prediction that was too far into the future. Since the Church really kinda needed to be able to predict the date of Easter more than a few days in advance, it went with the best full-moon-prediction algorithm available, and defined "first full moon after the vernal equinox" in terms of that. This is called the Paschal Full Moon, and it's where all the wacky epacts and Metonic cycles come from.

So what's a Metonic Cycle?

A Metonic cycle is 19 years.

The reason for the number 19 is the following, little-known fact: if you look up in the sky on January 1 and see a full moon, then look again on the same day precisely 19 years later, you'll see another full moon. In the meantime, there will have been 234 other full moons, but none of them will have occurred on January 1st.

What the ancient astronomers didn't realize, and what makes the formula slightly inaccurate, is that the moon only really goes around the earth about 234.997 times in 19 years, instead of exactly 235 times. Still, it's pretty close -- and without computers, or even slide rules, or even pencils, you were happy enough to use that nice, convenient 19-year figure, and not worry too much about some 0.003-cycle inaccuracy that you didn't really have the time or instruments to measure correctly anyway.

Okay, how about this Golden Number business then?

It's just a name people used for how many years into the Metonic cycle you were. Say you're walking down the street in Medieval Europe, and someone asks you what the Golden Number was. Just think back to when the last 19-year Metonic cycle started, and start counting from there. If this is the first year of the cycle, it means that the Golden Number is 1; if it's the 5th, the Golden number is 5; and so on.

Okay, so what's this Epact thing?

In the Gregorian calendar, the Epact is just the age of the moon at the beginning of the year. No, the age of the moon is not five billion years -- not here, anyway. Back in those days, when you talked about the age of the moon, you meant the number of days since the moon was "new". So if there was a new moon on January 1st of this year, the Epact is zero (because the moon is new, i.e. zero days "old"); if the moon was new three days before, the Epact is three; and so on.

When Easter was first introduced, the calculation for the Epact was very simple -- since the phases of the moon repeated themselves every 19 years, or close enough, the Epact was really easy to calculate from the Golden Number. Of course, this was the same calendar system that had one leap year every 4 years, which turned out to be too many, so the farmers ended up planting the fields at the wrong times, and life just started to suck.

Pope Gregory Makes Things More Complicated

You probably already know about the changes Pope Gregory XIII made in 1582 with respect to leap years. No more of this "one leap year every four years" business like that Julius guy said. Nowadays, you get one leap year every four years unless the current year is a multiple of 100, in which case you don't -- unless the current year is also a multiple of 400, in which case you do anyway. That's why 2000 was a leap year, even though 1900 wasn't (I'm sure many of you were bothered by this at the turn of the millenium).

Well, it turns out that the other thing Pope Gregory did, while he was at it, was to fix this Metonic Cycle-based Easter formula which, quite frankly, had a few bugs in it -- like the fact that Easter kept moving around, bumping into other holidays, occuring at the wrong time of year, and generally making a nuisance of itself.

Unfortunately, Pope Gregory had not taken CS 11. So instead of throwing out the old, poorly-designed code and building a new design from scratch, he sort of patched up the old version of the program (this is common even in modern times). While he was at it, he changed the definition of Epact slightly. Don't worry about it, though -- the definition above is the new, correct, Gregorian version.

This is why you'll see Knuth calculating the Epact in terms of the Golden Number, and then applying a "correction" of sorts afterwards: Gregory defined the Epact, and therefore Easter, in terms of the old definition with the Metonic cycles in it. Knuth is just the messenger here.

So what is this thing with "Z" and the moon's orbit?

It's just the "correction" factor which the Pope introduced (and Knuth later simplified) to account for the fact that the moon doesn't really orbit the earth exactly 235 times in 19 years. It's analogous to the "correction factor" he introduced in the leap years -- the new formula is based on the old one, is reasonably simple for people who don't like fractions, is also kind of arbitrary in some sense, and comes out much closer to reality, but still isn't perfect.

What about all the rest of that stuff?

Ah, well, you wouldn't want me to make this too easy, would you? My hope is that, after this brief introduction, that code up there will not seem quite so mysterious, and that you may, in fact, be able to figure out, if not exactly what's going on, at least most of the stuff that's happening in there.

Description of the program

Write a program that reads a series of years from a text file and prints out the date of Easter on all those years, as follows.

Testing the program

We are supplying you with a simple Makefile. Download it into your lab2 directory as a file called "Makefile" (it should be called that by default; just don't change the name). Running "make" will create the easter program. Running "make test" will run a simple test of the program and report whether it is correct or not with respect to the inputs. This is an example of a "test script". Test scripts are critically important in producing correctly-working code. Some programmers even advocate writing test scripts and test cases for functions before writing the actual code to be tested. Running "make check" will run the style checker on your code.

Other things to do

Write a clean target for the Makefile. This target will remove the easter program, all object files, and all files generated by the program when you type "make clean". It must not remove the input file used to test the program, your source code file, the test script, or the correct output file. Hint: use the Unix command "rm -f" (i.e. the rm program with the -f optional argument) to remove your files. Normally, rm complains if you try to remove a nonexistent file, but with the -f optional argument it won't. Note also that "rm -f" can take multiple filename arguments.

Try the program on an input file that intentionally contains years that are outside the correct range. Send the output to a file as usual. The error messages should be printed on the terminal, not put into the file. This shows you the difference between printing to stdout (which printf() does) and printing to stderr (which fprintf() does if you tell it to).

Supporting files

Make sure you download all of these files into your lab2 directory (except possibly for the style checker, which ideally you should already have put into your ~/bin directory).

To hand in

The program easter.c and the completed Makefile. We will run the program to see if it passes the test script.

For extra credit...

Have your program use Zeller's Congruence to verify that the date it is printing really does fall on a Sunday. Use assert to signal an error in case it doesn't. Get the definition of Zeller's Congruence by doing an internet search. Type "man assert" to learn more about the assert macro. Assert is a very valuable and under-appreciated debugging aid, which we will meet again in later labs.

References