Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions

  




 

 

Chapter 38. The Date of Easter

Don Knuth, in the Art of Computer Programming, Volume I, Fundamental Algorithms, suggests, “There are many indications that the sole important application of arithmetic in Europe during the Middle Ages was the calculation of Easter date, and so such algorithms are historically significant.

We present several variants on the basic problem of finding the date of Easter. We will not delve into the history and politics of this Christian holiday, but merely observe the huge intellectual effort put forth into locating the correct date.

In 1582, Pope Gregory decreed the change from the old Julian calendar to the Gregorian calendar. The most significant changes were dropping 10 days, fixing the leap year rules and fixing the rule for finding Easter. This was not adopted in England (and its colonies like the U.S. colonies) until 1782.

x ⌋ means round down, which is the usual rule for integer division. x mod y is the remainder when dividing x by y .

Algorithm E dates from the sixteenth century, and will find Easter for years after 1582. The author is D. Knuth, and it is published in Art of Computer Programming, Volume I, Fundamental Algorithms [Knuth73].

Procedure 38.1. Algorithm E.

(Date of Easter after 1582.) Let Y be the year for which the date of Easter is desired.

  1. Golden Number. Set G ← ( Y mod 19) + 1. ( G is the “golden number” of the year in the 19-year Metonic cycle.)

  2. Century. Set C ← ⌊ Y ÷ 100⌋ + 1. (When Y is not a multiple of 100, C is the century number; i.e., 1984 is in the twentieth century.)

  3. Corrections. Set X ← ⌊3 C ÷ 4⌋ − 12, Z ← ⌊(8 C +5) ÷ 25⌋ − 5. ( X is the number of years, such as 1900, in which leap year was dropped in order to keep in step with the sun. Z is a special correction designed to synchronize Easter with the moon's orbit.)

  4. Find Sunday. Set D ← ⌊5 Y ÷ 4⌋ − X − 10. (March ((− D ) mod 7) actually will be a Sunday.)

  5. Epact. Set E ← (11 G + 20 + Z X ) mod 30. If E = 25 and the golden number G is greater than 11, or if E = 24, then increase E by 1. ( E is the “epact,” which specifies when the full moon occurs.)

  6. Find full moon. Set N ← 44 − E . If N < 21 then set N N + 30. (Easter is supposedly the “first Sunday following the first full moon which occurs on or after March 21.” Actually perturbations in the moon's orbit do not make this strictly true, but we are concerned here with the “calendar moon” rather than the actual moon. The N th of March is a calendar full moon.

  7. Advance to Sunday. Set N N + 7 − (( D + N ) mod 7).

  8. Get month. If N > 31, the date is ( N − 31) April; otherwise the date is N March.

Knuth also observes the following:

A fairly common error in the coding of this algorithm is to fail to realize that the quantity (11G + 20 + Z − X) in step E5 may be negative, and so the positive remainder mod 30 is sometimes not computed. For example, in the year 14250, we would find G=1, X=95, Z=40; so if we had E=−24 instead of E=+6 we would get the ridiculous answer “42 April”. An interesting variation on this algorithm is to find the earliest year for which this remainder problem would cause the wrong date to be calculated for Easter.

For dates between 464 and 1582, the Julian calendar was in use, with different leap year rules, algorithm J computes Easter according to that calendar. The author is D. Knuth, and it is published in The Art of Computer Programming, Volume I, Fundamental Algorithms [Knuth73].

Procedure 38.2. Algorithm J.

(Date of Easter between 464 and 1582.) Let Y be the year for which the date of Easter is desired.

  1. Golden Number. Set G ← ( Y mod 19) + 1. ( G is the “golden number” of the year in the 19-year Metonic cycle.)

  2. Find Sunday. Set D ← ⌊5 Y ÷ 4⌋. (March ((− D ) mod 7) actually will be a Sunday.)

  3. Epact. Set E ← (11 G − 4) mod 30 + 1. ( E is the “epact,” which specifies when the full moon occurs.)

  4. Find full moon. Set N ← 44 − E . If N < 21 then set N N + 30. (Easter is supposedly the “first Sunday following the first full moon which occurs on or after March 21.” Actually perturbations in the moon's orbit do not make this strictly true, but we are concerned here with the “calendar moon” rather than the actual moon. The N th of March is a calendar full moon.

  5. Advance to Sunday. Set N N + 7 − (( D + N ) mod 7).

  6. Get month. If N > 31, the date is ( N − 31) April; otherwise the date is N March.

Algorithm A was first published in 1876. The author is Jean Meeus and it is published in Astronomical Algorithms [Meeus91].

Procedure 38.3. Algorithm A.

(Date of Easter after 1582.) Let Y be the year for which the date of Easter is desired.

  1. A ← ( Y mod 19).

  2. B ← ⌊ Y / 100⌋.

  3. C ← ( Y mod 100).

  4. D ← ⌊ B / 4 ⌋.

  5. E B mod 4.

  6. F ← ⌊ ( B + 8 ) / 25 ⌋.

  7. G ← ⌊ ( B F + 1 ) / 3 ⌋.

  8. H ← ( ( 19 A ) + B D G + 15 ) mod 30.

  9. I ← ⌊ C / 4 ⌋.

  10. K C mod 4.

  11. X ← ( 32 + ( 2 E ) + (2 I ) − H K ) mod 7.

  12. M ← ⌊ ( A + ( 11 H ) + (22 X ) ) / 451 ⌋.

  13. Q H + X − 7 M + 114.

  14. N ← ⌊ Q / 31 ⌋.

  15. P Q mod 31.

  16. Easter is day P +1 of month N .

Algorithm N is a variant on Algorithm A, but gives Easter prior to 1583. The rules for Easter are somewhat unclear prior to 325, but the author states that Easter is April 12 for 179, 711 and 1243. The author is Jean Meeus and it is published in Astronomical Algorithms [Meeus91].

Procedure 38.4. Algorithm B.

(Date of Easter prior to 1583.) Let Y be the year for which the date of Easter is desired.

  1. A ← ( Y mod 4).

  2. B ← ( Y mod 7).

  3. C ← ( Y mod 19).

  4. D ← (19 C + 15) mod 30.

  5. E ← (2 A + 4 B D + 34) mod 7.

  6. H D + E + 114.

  7. F ← ⌊ H / 31 ⌋.

  8. G H mod 31.

  9. Easter is day G +1 of month F .

The following algorithm is from T. M. O'Beirne, it is published in Puzzles and Paradoxes [OBeirne65].

Procedure 38.5. Algorithm O.

(Date of Easter after 1582.) Let Y be the year for which the date of Easter is desired.

  1. A ← ( Y mod 19).

  2. B ← ⌊ Y / 100⌋.

  3. C ← ( Y mod 100).

  4. D ← ⌊ B / 4 ⌋.

  5. E B mod 4.

  6. G ← ⌊ (8 B + 13 ) / 25 ⌋.

  7. H ← ( ( 19 A ) + B D G + 15 ) mod 30.

  8. M ← ⌊ ( A + 11 H ) / 319 ⌋.

  9. I ← ⌊ C / 4 ⌋.

  10. K C mod 4.

  11. F ← ( 2 E + 2 I K H + M + 32 ) mod 7.

  12. N ← ⌊ ( H M + F + 90 ) / 25 ⌋.

  13. P ← ( H M + F + N + 19 ) mod 32.

  14. Easter is day P of month N .

The following algorithm is from T. M. O'Beirne, it is published in Puzzles and Paradoxes [OBeirne65].

Procedure 38.6. Algorithm P.

(Date of Easter after 1582.) Let Y be the year for which the date of Easter is desired.

  1. B ← ⌊ Y / 100⌋.

  2. C ← ( Y mod 100).

  3. A ← ( 5 B + C ) mod 19.

  4. T ← 3 B + 75.

  5. D ← ⌊ T / 4 ⌋.

  6. E T mod 4.

  7. G ← ⌊ (8 B + 88 ) / 25 ⌋.

  8. H ← ( ( 19 A ) + D G ) mod 30.

  9. M ← ⌊ ( A + 11 H ) / 319 ⌋.

  10. T ← 300 − 60 E + C .

  11. J ← ⌊ T / 4 ⌋.

  12. K T mod 4.

  13. F ← ( 2 J K H + M ) mod 7.

  14. T H M + F + 110.

  15. N ← ⌊ T / 30 ⌋.

  16. Q T mod 30.

  17. P ← ( Q + 5 − N ) mod 32.

  18. Easter is day P of month N .

The following algorithm is from J.-M. Oudin. It is published in Standard C Date/Time Library [Latham98].

Procedure 38.7. Algorithm F.

(Date of Easter after 1582.) Let Y be the year for which the date of Easter is desired.

  1. C ← ⌊ Y / 100⌋.

  2. N ← ( Y mod 19).

  3. K ← ⌊ ( C − 17) / 25 ⌋.

  4. I ← ( C − ⌊ C / 4 ⌋ − ⌊ ( C K ) / 3 ⌋ + 19 N + 15 ) mod 30.

  5. I I − ⌊ I /28⌋(1 − ⌊ I /28⌋×⌊29/( I +1)⌋×⌊(21− N )/11⌋ ).

  6. J ← ( Y + ⌊ Y / 4 ⌋ + I + 2 − C + ⌊ C / 4 ⌋) mod 7.

  7. X I J .

  8. M ← 3 + ⌊ ( X + 40 ) / 44 ⌋.

  9. D ← X + 28 − 31 ⌊ M / 4 ⌋.

  10. Easter is day D of month M .

The following algorithm is from Gauss. It is published in Standard C Date/Time Library [Latham98].

Procedure 38.8. Algorithm G.

(Date of Easter between 1583 and 2199.) Let Y be the year for which the date of Easter is desired.

  1. H ← ⌊ Y / 100⌋.

  2. When H is then A is and B is

    H A B
    15 22 2
    16 22 2
    17 23 3
    18 23 4
    19 24 5
    20 24 5
    21 24 6
  3. C ← ( 19( Y mod 19) + A ) mod 30.

  4. D ← ( 2( Y mod 4) + 4( Y mod 7) + 6 C + B ) mod 7.

  5. day ← 22 + C + D , month ¬ 3.

  6. If day > 31, set day C + D − 9, increment month .

  7. If month = 4 and day = 26, set day ← 19 .

  8. If C = 38 and ( Y mod 19) > 10 and month = 4 and day = 25, set day ← 18 .

  9. Easter is day day of month month .

The following variation on algorithm G is from Dershowitz and Reingold, Calendrical Calculations [Dershowitz97]. This depends on a very clever idea of doing the calculation strictly as a number of days offset from a Gregorian Epoch date. This day number is called a Rata Die, RD. Once computed, the RD for Easter is simply converted to a Gregorian date. This algorithm requires the Gregorian to RD algorithm and the RD to Gregorian algorithm.

Procedure 38.9. Algorithm R.

(Date of Easter after 1582.) Let Y be the year for which the date of Easter is desired.

  1. Century. Set C ← ⌊ Y / 100⌋ + 1. (When Y is not a multiple of 100, C is the century number; i.e., 1984 is in the twentieth century.)

  2. Shifted Epact. Set E ← ( 14 + 11( Y mod 19 ) − ⌊3 C / 4⌋ + ⌊(5+8 C) / 25⌋ ) mod 30.

  3. Adjust Epact. If E = 0 or ( E = 1 and 10 < ( Y mod 19) ), then add 1 to E .

  4. Paschal Moon. Set R ← the RD for April 19 of year Y . Set P R E .

  5. Easter. Locate the Sunday after the Paschal Moon. Set Q P + 7 − ( P mod 7).

  6. Get Date. Compute the gregorian date for RD number Q .

In order to recover the actual date from the RD, the following algorithms must be used to get the year, the month and the day. These, in turn depend on another algorithm, given below, to compute the RD for a given date.

Procedure 38.10. Algorithm L.

(Leap Year Test.) Let Y be the year for which a leap day test should be done.

  1. Year Test. Set R Y mod 4.

  2. 400-Year Test. Set C Y mod 400.

  3. Final Rule. If R = 0 and not ( C =100 or C =200 or C =300), then Y is a leap year; otherwise Y is a standard year.

We can build up a RD from a Gregorian date with a relatively simple algorithm. This depends on a number of subtle observations, detailed by Dershowitz and Reingold in their book. This algorithm relies on Algorithm L to determine if a leap day is required.

Procedure 38.11. Algorithm RD.

(RD from a Gregorian Date.) Let Y, M and D be the year, month and day of a Gregorian date for which an RD is required.

  1. Days for all Years. Set R1 365( Y −1) + ⌊( Y −1)/4⌋ − ⌊( Y −1)/100⌋ + ⌊( Y −1)/400⌋.

  2. February Adjustment. If M ≤ 2, then set f ←0. If M > 2 and this year is a leap year, then set f ← −1. If M > 2 and this year is not a leap year, then set f ← −2.

  3. Days for this year. Set R2 ← ⌊ (367* M −362) / 12 ⌋ + f .

  4. Final RD. Set RD← R1+ R2+D .

Now that we can convert a Gregorian date to an RD, we can use algorithm RD to convert an RD back to a Gregorian date.

Procedure 38.12. Algorithm Y.

(Extract Gregorian year from RD number.) Let RD be the Rata Die date for which we want the Gregorian Year.

  1. Offset by Gregorian Start Date. Set d0 RD −1.

  2. 400 year cycles. Set n400 ← ⌊ d0 / 146097 ⌋ , set d1 d0 mod 146097.

  3. 100 year cycles. Set n100 ← ⌊ d1 / 36524 ⌋ , set d2 d1 mod 35624.

  4. 4 year cycles. Set n4 ← ⌊ d2 / 1461 ⌋ , set d3 d2 mod 1461.

  5. 1 year cycles. Set n1 ← ⌊ d3 / 365 ⌋ , set d4 d3 mod 365 + 1.

  6. Year. Set Y←400 n400 + 100 n100 + 4 n4 + n1 . If n100 =4 or n1 =4, Y is the Gregorian year. Otherwise, Y +1 is the Gregorian year.

Given a Gregorian year for an RD number, we can compute the RD number of the first day of the year, and subtract to find the day number. A bit more math will yield the month within the year. This relies on Algorithm Y and Algorithm L as well as Algorithm RD.

Procedure 38.13. Algorithm M.

(Extract month from the RD number.) Let RD by the Rata Die date for which we want the Gregorian month.

  1. Get key dates. Use algorithm Y to set Y to the year for RD . Use algorithm RD to set jan1 to the RD number for Jan. 1 of year Y . Use algorithm RD to set mar1 to the RD number for Mar. 1 of year Y .

  2. Get prior days in this year. Set P RD jan1 .

  3. Leap year correction. If RD < mar1 , then set c ←0. If RD > mar1 and year Y is a leap year, then set c ←1. If RD > mar1 and year Y is not a leap year, set c ←2.

  4. Compute month. Set M ← ⌊(12*( P + c )+373) / 367⌋. M is the month.

Finally, we can combine algorithm Y and M (along with L and RD) to compute the day of the month for an RD number. This is done by getting the year and month, and then finding the RD number for the first of the month. We then subtract the RD number from the RD number for the first of the month. The remainder is the number of days after the first.

Procedure 38.14. Algorithm D.

(Extract day from the RD number.) Let RD by the Rata Die date for which we want the day of the Gregorian month.

  1. Get key date. Use algorithm Y to set Y to the year for RD . Use algorithm M to set M to the month for RD . Use algorithm RD to set mon1 to the first day of month M , year Y .

  2. Get day of this month. Set D RD mon1 + 1. D is the day of the month.

Check Your Results. Find a calendar or web site with dates for Easter.


 
 
  Published under the terms of the Open Publication License Design by Interspire