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.
-
Golden Number. Set
G
← (
Y
mod 19) +
1. (
G
is the “golden number” of
the year in the 19-year Metonic cycle.)
-
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.)
-
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.)
-
Find Sunday. Set
D
← ⌊5
Y
÷ 4⌋ −
X
− 10. (March ((−
D
) mod
7) actually will be a Sunday.)
-
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.)
-
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.
-
Advance to Sunday. Set
N
←
N
+ 7 −
((
D
+
N
) mod 7).
-
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.
-
Golden Number. Set
G
← (
Y
mod 19) +
1. (
G
is the “golden number” of
the year in the 19-year Metonic cycle.)
-
Find Sunday. Set
D
← ⌊5
Y
÷ 4⌋.
(March ((−
D
) mod 7) actually will be a
Sunday.)
-
Epact. Set
E
← (11
G
− 4)
mod 30 + 1. (
E
is the “epact,”
which specifies when the full moon occurs.)
-
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.
-
Advance to Sunday. Set
N
←
N
+ 7 −
((
D
+
N
) mod 7).
-
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.
-
A
← (
Y
mod
19).
-
B
← ⌊
Y
/
100⌋.
-
C
← (
Y
mod
100).
-
D
← ⌊
B
/ 4
⌋.
-
E
←
B
mod
4.
-
F
← ⌊ (
B
+ 8 ) / 25
⌋.
-
G
← ⌊ (
B
−
F
+ 1 ) / 3 ⌋.
-
H
← ( ( 19
A
) +
B
−
D
−
G
+ 15 ) mod 30.
-
I
← ⌊
C
/ 4
⌋.
-
K
←
C
mod
4.
-
X
← ( 32 + ( 2
E
) +
(2
I
) −
H
−
K
) mod 7.
-
M
← ⌊ (
A
+ (
11
H
) + (22
X
) ) / 451
⌋.
-
Q
←
H
+
X
− 7
M
+ 114.
-
N
← ⌊
Q
/ 31
⌋.
-
P
←
Q
mod
31.
-
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.
-
A
← (
Y
mod
4).
-
B
← (
Y
mod
7).
-
C
← (
Y
mod
19).
-
D
← (19
C
+ 15) mod
30.
-
E
← (2
A
+
4
B
−
D
+ 34) mod
7.
-
H
←
D
+
E
+ 114.
-
F
← ⌊
H
/ 31
⌋.
-
G
←
H
mod
31.
-
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.
-
A
← (
Y
mod
19).
-
B
← ⌊
Y
/
100⌋.
-
C
← (
Y
mod
100).
-
D
← ⌊
B
/ 4
⌋.
-
E
←
B
mod
4.
-
G
← ⌊ (8
B
+ 13 ) /
25 ⌋.
-
H
← ( ( 19
A
) +
B
−
D
−
G
+ 15 ) mod 30.
-
M
← ⌊ (
A
+
11
H
) / 319 ⌋.
-
I
← ⌊
C
/ 4
⌋.
-
K
←
C
mod
4.
-
F
← ( 2
E
+
2
I
−
K
−
H
+
M
+ 32 ) mod
7.
-
N
← ⌊ (
H
−
M
+
F
+ 90 ) / 25
⌋.
-
P
← (
H
−
M
+
F
+
N
+ 19 ) mod 32.
-
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.
-
B
← ⌊
Y
/
100⌋.
-
C
← (
Y
mod
100).
-
A
← ( 5
B
+
C
) mod 19.
-
T
← 3
B
+
75.
-
D
← ⌊
T
/ 4
⌋.
-
E
←
T
mod
4.
-
G
← ⌊ (8
B
+ 88 ) /
25 ⌋.
-
H
← ( ( 19
A
) +
D
−
G
) mod 30.
-
M
← ⌊ (
A
+
11
H
) / 319 ⌋.
-
T
← 300 − 60
E
+
C
.
-
J
← ⌊
T
/ 4
⌋.
-
K
←
T
mod
4.
-
F
← ( 2
J
−
K
−
H
+
M
) mod 7.
-
T
←
H
−
M
+
F
+ 110.
-
N
← ⌊ T / 30 ⌋.
-
Q
←
T
mod
30.
-
P
← (
Q
+ 5 −
N
) mod 32.
-
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.
-
C
← ⌊
Y
/
100⌋.
-
N
← (
Y
mod
19).
-
K
← ⌊ (
C
− 17) /
25 ⌋.
-
I
← (
C
−
⌊
C
/ 4 ⌋ − ⌊ (
C
−
K
) / 3 ⌋ + 19
N
+ 15 ) mod
30.
-
I
←
I
−
⌊
I
/28⌋(1 −
⌊
I
/28⌋×⌊29/(
I
+1)⌋×⌊(21−
N
)/11⌋
).
-
J
← (
Y
+
⌊
Y
/ 4 ⌋ +
I
+ 2 −
C
+ ⌊
C
/ 4 ⌋) mod
7.
-
X
←
I
−
J
.
-
M
← 3 + ⌊ (
X
+ 40
) / 44 ⌋.
-
D
← X + 28 − 31 ⌊
M
/ 4 ⌋.
-
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.
-
H
← ⌊
Y
/
100⌋.
-
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 |
-
C
← ( 19(
Y
mod 19)
+
A
) mod 30.
-
D
← ( 2(
Y
mod 4) +
4(
Y
mod 7) + 6
C
+
B
) mod 7.
-
day
← 22 +
C
+
D
,
month
¬ 3.
-
If
day
> 31, set
day
←
C
+
D
− 9, increment
month
.
-
If
month
= 4 and
day
= 26, set
day
←
19
.
-
If
C
= 38 and (
Y
mod 19) > 10 and
month
= 4 and
day
= 25, set
day
←
18
.
-
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.
-
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.)
-
Shifted Epact. Set
E
← ( 14 + 11(
Y
mod 19 ) − ⌊3
C
/ 4⌋ +
⌊(5+8
C)
/ 25⌋ ) mod 30.
-
Adjust Epact. If
E
= 0 or (
E
= 1
and 10 < (
Y
mod 19) ), then add 1 to
E
.
-
Paschal Moon. Set
R
← the RD for April 19 of year
Y
. Set
P
←
R
−
E
.
-
Easter. Locate the Sunday after the Paschal Moon. Set
Q
←
P
+ 7 −
(
P
mod 7).
-
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.
-
Year Test. Set
R
←
Y
mod
4.
-
400-Year Test. Set
C
←
Y
mod
400.
-
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.
-
Days for all Years. Set
R1
←
365(
Y
−1) + ⌊(
Y
−1)/4⌋ −
⌊(
Y
−1)/100⌋ +
⌊(
Y
−1)/400⌋.
-
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.
-
Days for this year. Set
R2
← ⌊
(367*
M
−362) / 12 ⌋ +
f
.
-
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.
-
Offset by Gregorian Start Date. Set
d0
←
RD
−1.
-
400 year cycles. Set
n400
← ⌊
d0
/ 146097 ⌋ , set
d1
←
d0
mod 146097.
-
100 year cycles. Set
n100
← ⌊
d1
/ 36524 ⌋ , set
d2
←
d1
mod 35624.
-
4 year cycles. Set
n4
← ⌊
d2
/ 1461 ⌋ , set
d3
←
d2
mod 1461.
-
1 year cycles. Set
n1
← ⌊
d3
/ 365 ⌋ , set
d4
←
d3
mod 365 + 1.
-
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.
-
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
.
-
Get prior days in this year. Set
P
←
RD
−
jan1
.
-
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.
-
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.
-
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
.
-
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.
