CS 11 C track: Assignment 2

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.

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.

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.

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.

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.

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.

You may 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 just 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.

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.

Ah, well, you wouldn’t want me to make this too easy, would you? Our 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.

When the program is written, use Unix input/output redirection to handle input from and output to files (if you don’t know about this, here is a decent tutorial). In other words, invoke the program like this:

where $ is the terminal prompt (so you don’t type that in). Note: this is Unix shell (terminal) syntax, not C syntax! The < infile part means to take the input from the file called infile instead of from the keyboard, and the > outfile part means to send the output to the file called outfile instead of printing it to the terminal. See below for more details on this.

infile is a file containing a list of years (one per line) e.g.

and outfile will become a list of year/date pairs, e.g.

Handling input from files and output to files directly from your C program is possible, but it’s a little bit more complicated, so we won’t bother with it now (it involves functions like fopen(), fclose() and fscanf(); look them up if you’re curious). Instead, you just have to read from standard input (i.e. the terminal; use scanf() like in the previous assignment) and write to standard output (using printf()). Unix-derived operating systems (including Linux and MacOS) will convert this to reading from a file and writing to a file if you use the < and > symbols in the command line as we showed above:

Technically, what this does is bind standard input to the file infile and bind standard output to the file outfile just for this one invocation of the easter program, so that when in your program you read from standard input (using scanf()) you’re really reading from infile, and when you write to standard output (using printf()) you’re really writing to outfile. ^[1]

The program should include a function called calculate_Easter_date (yes, that exact name) which takes an integer argument (the year) and returns an integer representing the date. The month should be indicated by the sign of the integer return value: negative means March and positive means April. The absolute value of the integer represents the day of the month. So April 10 would be represented as the integer 10, while March 23 would be represented as the integer -23. This is not part of the Knuth algorithm! You have to convert from the value that Knuth’s algorithm gives you to the value in this representation (which is quite easy).

The allowable years are in the range 1582 to 39999; if the input is outside of this range, the calculate_Easter_date function should return 0. When the main program sees this return value, it should print an error message to stderr (NOT to stdout; use fprintf instead of printf for this), and then continue with the loop.

In the main() function, use a call to scanf to read in each the input line from stdin. Note that to read an integer value using scanf, you need to use the "%d" format string (where "d" means "decimal"). Store the return value of scanf in a variable (yes, scanf does return a value, but it isn’t used very often). This return value will be equal to the integer constant EOF ("end of file") when there is no more input. EOF is defined in the header file <stdio.h>, just like printf and scanf. You will find the break statement (K&R pp. 64-65) to be useful in your loop. Use a while loop that loops forever e.g. while (1) { ... } until an EOF is encountered, and then break out of the loop. The main() function should call the calculate_Easter_date() function for each line of input. If calculate_Easter_date() returns 0 (because of a range error), print an error message to stderr and keep going.

Make sure you have declared function prototypes at the top of your file before you define the functions. Although this isn’t strictly necessary here, it’s a good habit to get into. Prototypes allow you to reference functions before they are defined, which allows you to program without having to worry about what order your functions are defined in. (However, you do not have to write a prototype for the main function.)

Comment your code liberally, especially the Easter algorithm itself. Very few programmers write too many comments; most write way too few. Remember, your task is to write a program which (a) does what it’s supposed to, and (b) is clearly understandable. You are free to copy Knuth’s algorithm verbatim if you like, but make sure you add comments explaining what each step of the algorithm does. Also, your version of the algorithm should contain better variable names than the ones Knuth uses. If you use one-letter variable names like Knuth does, you’ll lose a lot of marks. Instead, use variable names that are words or phrases that are descriptive of the meaning of the variable.

For functions, put a comment before the function that states what the function does, what the arguments mean, and what the return value means. These are the most important kinds of comments you’ll ever write, because they are what will allow other people to use your code.

Also, put a comment at the top of the file explaining what the program does as a whole.

We will be grading your program not only on how well it performs its task, but on how easy it is to read and understand. Make sure you keep this in mind as you do this assignment. And don’t think this is only an exercise for this assignment — future assignments have to have the same standard of commenting.