Easter Sunday: Do it Vleeptron's way / also, theme of my favorite Rose Bowl Parade float from last year

The Moon crater Lilius -- he was so non-famous that no portraits of him seem to have survived -- and Christopher Clavius. He has a crater, too, where the Monolith was uncovered in "2001."

Knuth's Algorithm is a modern housebreaking of the method devised for the new reformed Gregorian calendar by 16th century Neapolitan astronomer Aloysius Lilius and the German Jesuit mathematician Christopher Clavius. They transformed the earlier method agreed on at the Council of Nicea in 325.

Because The Last Supper was a Passover/Pesach, the whole mess references the moveable feast of Passover in the Hebrew lunar calendar.

You can either move to Pasedena and take this programming course from Mike Vanier and Donnie Pinkston at the California Institute of Technology (Cal Tech), or you can read all about the Easter Sunday Date algorithm here on Vleeptron.

If you want to see what Pasadena looks like, watch the television broadcast of The Rose Bowl Parade on New Year's Day. Every float must be made entirely of flowers or plant material. (My favorite float theme from last year's parade was "We Forgot What Our Theme Was" by the Oakland Bhang Growers Association.)

While he was discovering that Nebulae are really faraway Galaxies, how faraway they really are, and that the Universe is expanding, Edwin Hubble lived in Pasadena and hung out with Aldous Huxley and Walt Disney.

Parts of this filched document have been filetted for relavence. I mean, do you care that there's a Quiz on Tuesday?

These guys say Donald Knuth's Algorithm works for any year from 1582 to 39999 (in the Gregorian calendar).

As Vleeptron advised the last time this Thang came up: If you're not using Knuth's Algorithm, you could find yourself in all your Easter vestments on the steps of your cathedral at sunrise and wonder where all your sheep are. Accept No Substitutes.

Essay Question: What's the date of Easter Sunday 39999, and will they have settled that big dustup between Good Works and Faith by then? Who won?

==============

C track: assignment 2

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.

Easter computation

The allowable years are in the range 1582 to 39999 ...

[Reference]

Donald Knuth, The Art of Computer Programming, vol. 1: Fundamental Algorithms.

The Art of Computer Programming is a three-volume set (although more volumes are being written) which is a definitive treatment on computer algorithms written by Donald Knuth. The books are usually referred to simply as "Knuth vol. 1", etc. They are extremely dense and not really suitable for beginners, but they are good if you need to look up an algorithm and learn more about it. Knuth virtually invented the field of mathematical analysis of computer algorithms, and is still going strong.