• #### Easter calculation in the Gregorian Calendar

From jmsteele9027@sbcglobal.net@21:1/5 to Judson McClendon on Mon Apr 4 15:48:24 2016
On Friday, October 19, 2007 at 2:41:53 PM UTC-4, Judson McClendon wrote:
Years ago I wrote a BASIC program using the Easter calculation algorithm
from Knuth's "Art of Computer Programming," Second Edition, pages
155-156, and later posted it on my website, and probably here as well. Recently I received an email from Edward Moneo informing me of a glitch
in the Epact calculation that would cause errors for certain years beginning with 9006. Knuth pointed out this possibility, but his solution was a bit cryptic, and I hadn't studied it thoroughly enough at the time. Edward suggested a fix, and I thought of another. Our discussions prompted me
to research the matter further, and the result is the QuickBASIC/QBASIC program below (I'm posting a PowerBASIC version to alt.lang.powerbasic
and comp.lang.basic.powerbasic), which I thought some of you might like
to see.

The problem in the Epact calculation is that, as years get larger than about 9000, the Epact can become negative, requiring a correction. I didn't code Knuth's Epact correction into the program below, but here are all three versions.

Uncorrected Epact calculation:
Epact = (11 * GoldenNo + 20 + LunarCorr - LeapCent) MOD 30

Knuth's correction:
Epact = (11 * GoldenNo + 20 + LunarCorr - LeapCent) MOD 30
IF (Epact < 0) THEN Epact = Epact + 30

Jud's correction:
Epact = (11 * GoldenNo + 30020 + LunarCorr - LeapCent) MOD 30

Note: By adding a sufficiently large multiple of 30 to the constant 20,
Epact will not become negative in the target range of years. This
value was chosen as sufficient for Knuth's suggested test range of
years = 1583 to 999,999. I like this method because it requires no
extra memory or time.

Edward Mateo's correction:
Epact = (11 * GoldenNo + 20 + LunarCorr - LeapCent)
Epact = Epact - 30 * INT(Epact / 30)

Note: To be honest, I'm not sure why Edward's correction works,
but it does.

The program also contains three other Easter calculation methods, the 'original' Oudin algorithm, a simpler version of Oudin's algorithm by
Claus Tonderings, and Butcher's algorithm. All of the algorithms
return the same values for every year in the range 1 - 999,999,999,
except for certain years between 216 and 1497 that the two Oudin
algorithms disagree with the others. To get that huge range, I used the PowerBASIC version and changed the variables to QUAD (64bit).
I find it strange that several algorithms could give the same result for years 1 to 999,999,999 except for certain years between 216 & 1497!
Easters before 1583 predated the Gregorian Calendar, and it is not
likely the Gregorian Calendar will remain unchanged past 4999, at
the latest. :-) (QuickBASIC/QBASIC program below)
--
Judson McClendon
Sun Valley Systems http://sunvaley.com
"For God so loved the world that He gave His only begotten Son, that
whoever believes in Him should not perish but have everlasting life."

'
' **************************************************
' * *
' * EASTERT.BAS *
' * *
' * Tests Easter calculation routines *
' * *
' * Compile using QuickBASIC 4.5 *
' * *
' * Judson D. McClendon *
' * Sun Valley Systems *
' * 4522 Shadow Ridge Pkwy *
' * Pinson, AL 35126-2192 *
' * 205-680-0460 *
' * *
' **************************************************
'

'
' ** Sub & Function Declarations **
'
DECLARE FUNCTION EasterKnuth(Year AS LONG)
DECLARE FUNCTION EasterKnuth2(Year AS LONG)
DECLARE FUNCTION EasterOudin(Year AS LONG)
DECLARE FUNCTION EasterOudin2(Year AS LONG)
DECLARE FUNCTION EasterButcher(Year AS LONG)

'
' ** Main **
'
DIM Year AS LONG
DIM Knuth AS LONG
DIM Knuth2 AS LONG
DIM Oudin AS LONG
DIM Oudin2 AS LONG
DIM Butcher AS LONG

FOR Year = 1583 TO 999999
Knuth = EasterKnuth(Year)
Knuth2 = EasterKnuth2(Year)
Oudin = EasterOudin(Year)
Oudin2 = EasterOudin2(Year)
Butcher = EasterButcher(Year)

IF (Knuth <> Knuth2) _
OR _
(Knuth <> Oudin) _
OR _
(Knuth <> Oudin2) _
OR _
(Knuth <> Butcher) THEN
PRINT USING "###### K:#### "; Year, Knuth;
IF (Knuth <> Knuth2) THEN
PRINT TAB(17); "K2:";
PRINT USING "####"; Knuth2;
END IF
IF (Knuth <> Oudin) THEN
PRINT TAB(26); "O:";
PRINT USING "####"; Oudin;
END IF
IF (Knuth <> Oudin2) THEN
PRINT TAB(34); "O2:";
PRINT USING "####"; Oudin2;
END IF
IF (Knuth <> Butcher) THEN
PRINT TAB(43); "B:";
PRINT USING "####"; Butcher;
END IF
PRINT
END IF

NEXT

'
' ** EasterKnuth Function **
'
' Knuth's algorithm with Jud McClendon's Epact correction
'
FUNCTION EasterKnuth(Year AS LONG)
DIM EasterMonth AS LONG
DIM EasterDay AS LONG
DIM EasterMMDD AS LONG

DIM GoldenNo AS LONG
DIM SundayCorr AS LONG
DIM Century AS LONG
DIM LeapCent AS LONG
DIM LunarCorr AS LONG
DIM Epact AS LONG
DIM FullMoon AS LONG

GoldenNo = (Year MOD 19) + 1
Century = (Year \ 100) + 1
LeapCent = ((3 * Century) \ 4) - 12
LunarCorr = ((8 * Century + 5) \ 25) - 5
SundayCorr = ((5 * Year) \ 4) - LeapCent - 10

' ** Jud McClendon correction to:
' ** Epact = (11 * GoldenNo + 20 + LunarCorr - LeapCent) MOD 30
Epact = (11 * GoldenNo + 30020 + LunarCorr - LeapCent) MOD 30

IF ((Epact = 25) AND (GoldenNo > 11)) OR (Epact = 24) THEN
Epact = Epact + 1
END IF
FullMoon = 44 - Epact
IF FullMoon < 21 THEN
FullMoon = FullMoon + 30
END IF
EasterDay = FullMoon + 7 - ((SundayCorr + FullMoon) MOD 7)
IF EasterDay > 31 THEN
EasterDay = EasterDay - 31
EasterMonth = 4
ELSE
EasterMonth = 3
END IF

EasterMMDD = EasterMonth * 100 + EasterDay
EasterKnuth = EasterMMDD
END FUNCTION

'
' ** EasterKnuth2 Function **
'
' Knuth's algorithm with Edward Moneo's Epact correction
'
FUNCTION EasterKnuth2(Year AS LONG)
DIM EasterMonth AS LONG
DIM EasterDay AS LONG
DIM EasterMMDD AS LONG

DIM GoldenNo AS LONG
DIM SundayCorr AS LONG
DIM Century AS LONG
DIM LeapCent AS LONG
DIM LunarCorr AS LONG
DIM Epact AS LONG
DIM FullMoon AS LONG

GoldenNo = (Year MOD 19) + 1
Century = (Year \ 100) + 1
LeapCent = ((3 * Century) \ 4) - 12
LunarCorr = ((8 * Century + 5) \ 25) - 5
SundayCorr = ((5 * Year) \ 4) - LeapCent - 10

' ** Edward Moneo correction to:
' ** Epact = (11 * GoldenNo + 20 + LunarCorr - LeapCent) MOD 30
Epact = (11 * GoldenNo + 20 + LunarCorr - LeapCent)
Epact = Epact - 30 * INT(Epact / 30)

IF ((Epact = 25) AND (GoldenNo > 11)) OR (Epact = 24) THEN
Epact = Epact + 1
END IF
FullMoon = 44 - Epact
IF FullMoon < 21 THEN
FullMoon = FullMoon + 30
END IF
EasterDay = FullMoon + 7 - ((SundayCorr + FullMoon) MOD 7)
IF EasterDay > 31 THEN
EasterDay = EasterDay - 31
EasterMonth = 4
ELSE
EasterMonth = 3
END IF

EasterMMDD = EasterMonth * 100 + EasterDay
EasterKnuth2 = EasterMMDD
END FUNCTION

'
' ** EasterOudin Function **
'
' Original Oudin algorithm from "Standard C Date/Time Library" page 169
'
FUNCTION EasterOudin(Year AS LONG)
DIM EasterMonth AS LONG
DIM EasterDay AS LONG
DIM EasterMMDD AS LONG

DIM C AS LONG
DIM N AS LONG
DIM K AS LONG
DIM I AS LONG
DIM J AS LONG
DIM X AS LONG

C = Year \ 100
N = Year - 19 * (Year \ 19)
K = (C - 17) \ 25
I = C - C \ 4 - (C - K) \ 3 + 19 * N + 15
I = I - 30 * (I \ 30)
I = I - (I \ 28) * (1 - (I \ 28) * (29 \ (I + 1)) * ((21 - N) \ 11))
J = Year + Year \ 4 + I + 2 - C + C \ 4
J = J - 7 * (J \ 7)
X = I - J
EasterMonth = 3 + (X + 40) \ 44
EasterDay = X + 28 - 31 * (EasterMonth \ 4)

EasterMMDD = EasterMonth * 100 + EasterDay
EasterOudin = EasterMMDD
END FUNCTION

'
' ** EasterOudin2 Function **
'
' Short Oudin algorithm by Claus Tonderings
'
FUNCTION EasterOudin2(Year AS LONG)
DIM EasterMonth AS LONG
DIM EasterDay AS LONG
DIM EasterMMDD AS LONG

DIM Century AS LONG
DIM G AS LONG
DIM I AS LONG
DIM J AS LONG
DIM K AS LONG
DIM L AS LONG

Century = Year \ 100
G = Year MOD 19
K = (Century - 17) \ 25
I = (Century - Century \ 4 - (Century - K) \ 3 + 19 * G + 15) MOD 30
I = I - (I \ 28) * (1 - (I \ 28) * (29 \ (I + 1)) * ((21 - G) \ 11))
J = (Year + Year \ 4 + I + 2 - Century + Century \ 4) MOD 7
L = I - J
EasterMonth = 3 + (L + 40) \ 44
EasterDay = L + 28 - 31 * (EasterMonth \ 4)

EasterMMDD = EasterMonth * 100 + EasterDay
EasterOudin2 = EasterMMDD
END FUNCTION

'
' ** EasterButcher Function **
'
' Butcher's Algorithm
'
FUNCTION EasterButcher(Year AS LONG)
DIM EasterMonth AS LONG
DIM EasterDay AS LONG
DIM EasterMMDD AS LONG

DIM A AS LONG
DIM B AS LONG
DIM C AS LONG
DIM D AS LONG
DIM E AS LONG
DIM F AS LONG
DIM G AS LONG
DIM H AS LONG
DIM I AS LONG
DIM K AS LONG
DIM L AS LONG
DIM M AS LONG

A = Year MOD 19
B = Year \ 100
C = Year 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
L = (32 + 2 * E + 2 * I - H - K) MOD 7
M = (A + 11 * H + 22 * L) \ 451
Eastermonth = (H + L - 7 * M + 114) \ 31
Easterday = (H + L - 7 * M + 114) MOD 31 + 1

EasterMMDD = EasterMonth * 100 + EasterDay
EasterButcher = EasterMMDD
END FUNCTION

Years too late, but the Oudin routine contains an error that only matters for C<15. Two ways to fix:
1) In the line defining K = (C-17)\25, replace by K = (C+8)/25 -1, OR
2) eliminate K entirely and replace (C-K)\3 in the line below by (8*C+13)\25

Tondering made this change in version 2.9 of Calendar facts. If the argument is negative, there is always some uncertainty in integer divide, the INT function (between calculators and computers) and the MOD or % function. Note that Knuth defines
century as 1 more than Y\100 and uses (8*century+5)\25 as the lunar correction.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)