A lot of my original work on calculating the date of Easter Sunday has been superseded by the work of Al Petrofsky. In response to my earlier attempts, Al posted his solution which is far superior.
I have recently returned to this problem with fresh eyes and now believe I understand Al's algorithm, which I present (re-commented) below.
; Compute proleptic Gregorian/Anglican Easter, per the British ; Calendar Act, 24 Geo. II c. 23 (1751) and "Romani Calendarii a ; Gregorio XIII. P. M. Restituti Explicatio" (Clavius, 1603). ; See http://en.wikipedia.org/wiki/Computus ; Authored 2011 by Al Petrofsky (al@petrofsky.org). ; Features: ; No self-modifying code (suitable for ROMming) ; No subroutines or data tables (completely relocatable code) ; No branching (just put one foot in front of the other) ; Measurements: ; Clock ticks: 1043 ; Code bytes: 237 ; Opcode fetches: 202 ; Stack words: 2 (plus return address) ; (those all exclude the call but include the return) ; On entry: ; HL is Gregorian year (0..65535) ; On exit: ; A is "Day of March" for Easter (22..56) ; B is day of month of Easter (1..31) ; C is month of year of Easter (3..4) ; F is trashed ; DE and HL are saved and restored. ; IX, IY, and the alternate registers are never touched ; (and therefore will be available during interrupts) ; PHASE A: Compute Golden Number ; This phase computes a variant of the Golden Number ; A7 = 138 - (Year % 19) ; See http://en.wikipedia.org/wiki/Golden_number_(time) ; Let A1 = 7 * ((Year >> 6) & 7) ; Let A2 = A1 + 133 - (Year >> 9) + (Year & 63) ; Where (A2 % 19) = (Year % 19) ; Let A3 = (((((A2 >> 1) + A2) >> 2) + A2) >> 1) + A2 ; Let A4 = A3 >> 5 ; Where A4 is nearly (A2 * 27) / 512, and exactly A2 / 19 ; Let A5 = A4 << 4 ; Let A6 = ((A5 >> 1) + A5 >> 3) + A5 - A2 = A4 * 19 - A2 ; Let A7 = A6 + 138 PUSH DE ; Save DE XOR A ; A = 0 LD B, A ; B = 0 LD C, H RR C ; BC = Year >> 9 RLA ; A = (Year >> 8) & 1 LD E, L RL E RLA ; A = (Year >> 7) & 3 RL E RLA ; A = (Year >> 6) & 7 LD D, A ; D = (Year >> 6) & 7 ADD A, A ; A = D * 2 ADD A, D ; A = D * 3 ADD A, A ; A = D * 6 ADD A, D ; A = D * 7 = A1 ADD A, 133 ; A = A1 + 133 SUB C LD C, A ; C = A1 + 133 - (Year >> 9) LD A, L AND 63 ; A = Year & 63 ADD A, C ; A = A1 + 133 - (Year >> 9) + (Year & 63) = A2 LD E, A ; E = A2 [6..245] RRA ; A = A2 >> 1 ADD A, E ; A = (A2 >> 1) + A2 RRA ; A = ((A2 >> 1) + A2) >> 1 OR A ; Carry = 0 RRA ; A = ((A2 >> 1) + A2) >> 2 ADD A, E ; A = (((A2 >> 1) + A2) >> 2) + A2 RRA ; A = ((((A2 >> 1) + A2) >> 2) + A2) >> 1 ADD A, E ; A = (((((A2 >> 1) + A2) >> 2) + A2) >> 1) + A2 = A3 RRA ; A = A3 >> 1 AND 240 ; A = (A3 >> 5) << 4 = A5 LD C, A ; C = A5 RRA ; A = A5 >> 1 ADD A, C ; A = (A5 >> 1) + A5 RRA ; A = ((A5 >> 1) + A5) >> 1 RRA ; A = ((A5 >> 1) + A5) >> 2 RRA ; A = ((A5 >> 1) + A5) >> 3 ADD A, C ; A = (((A5 >> 1) + A5) >> 3) + A5 = A4 * 19 SUB E ; A = A4 * 19 - A2 = -(Year % 19) ADD A, 138 ; A = 138 - (Year % 19) = A7 LD D, A ; D = A7 ; PHASE C: Compute Centuries ; This phase computes ; C7 = (Year / 100) + 1 ; Let C1 = Year / 4 ; Let C2 = Year >> 8 ; Let C3 = ((((C2 >> 3) + C2) >> 2) + C2) << 1 ; Where C3 (10 bits) is nearly C1 * 41 / 1024 and nearly (C1 / 25) + 1 ; Let C4 = C1 - (C3 - 1) * 25 ; Where C4 is the leftover that will need to be accurately divided by 25 ; Let C5 = (((C4 >> 3) + C4) >> 2) + C4 ; Let C6 = C5 >> 5 ; Where C6 (3 bits) is C4 / 25 ; Let C7 = C3 + C6 = Year / 100 + 1 PUSH HL ; Save Year LD A, H RRA RR L RRA RR L AND 63 ; AL = Year / 4 = C1 RRA ; A = C2 >> 3 ADD A, H ; A = (C2 >> 3) + C2 RRA ; A = ((C2 >> 3) + C2) >> 1 OR A ; Carry = 0 RRA ; A = ((C2 >> 3) + C2) >> 2 ADD A, H RL B ; BA = (((C2 >> 3) + C2) >> 2) + C2 RLA RL B LD C, A ; BC = ((((C2 >> 3) + C2) >> 2) + C2) << 1 = C3 ADD A, A ADD A, C ADD A, A ADD A, A ADD A, A ADD A, C ; A = (C3 * 25) % 256 SUB L ; A = (C3 * 25 - C1) % 256 = C3 * 25 - C1 CPL ; A = C1 - C3 * 25 - 1 ADD A, 26 ; A = C1 - C3 * 25 + 25 = C1 - (C3 - 1) * 25 = C4 LD E, A ; E = C4 [11..136] RRA RRA AND 63 RRA ; A = C4 >> 3 ADD A, E ; A = (C4 >> 3) + C4 RRA OR A RRA ; A = ((C4 >> 3) + C4) >> 2 ADD A, E ; A = (((C4 >> 3) + C4) >> 2) + C4 = C5 RLCA RLCA RLCA AND 7 ; A = C5 >> 5 = C6 = C4 / 25 ADD A, C LD C, A ADC A, B SUB C LD B, A ; BC = C3 + C6 = C7 = Year / 100 + 1 ; PHASE E: Compute Lunar Correction ; Computes a lunar correction ; E2 = ((((Year / 100) * 8) + 13) / 25) + 11 ; Let E1 = (C7 * 82) + 51 - (C7 * 20) >> 8 ; Where N * 5243 / (1 << 17) is nearly N / 25 ; Let E2 = (E1 >> 8) + 13 ; Where E2 = ((((Year / 100) * 8) + 13) / 25) + 11 LD H, B LD L, C ; HL = Year / 100 + 1 [1..656] ADD HL, HL ADD HL, HL ADD HL, BC ADD HL, HL ADD HL, HL ; HL = C7 * 20, H = (C7 * 20) >> 8 LD A, 51 SUB H ; A = 51 - (C7 * 5) / 64 ADD HL, HL ADD HL, BC ADD HL, HL ; HL = C7 * 82, HL + A = E1 ADD A, L LD A, H ADC A, 11 ; A = E2 ; PHASE F: Accumulate Solar Corrections ; Accumulates all the corrections for the solar calendar including leap days ; F4 = 227 - (Year % 19) * 11 + ((Year / 100) * 8 + 13) / 25 - (Year / 100) + (Year / 400) ; Let F1 = ((C7 >> 1) + C7) >> 1 ; Where F1 = Year / 100 - Year / 400 (Solar correction) ; Let F2 = E2 - F1 ; Let F3 = (A7 * 11) % 256 ; Where F3 = 238 - (Year % 19) * 11 ; Let F4 = F3 - F2 ; Where F4 = 227 - (Year % 19) * 11 + ((Year / 100) * 8 + 13) / 25 - (Year / 100) + (Year / 400) LD H, B LD L, C ; HL = C7 = Year / 100 + 1 SRL H RR L ; HL = C7 >> 1 ADD HL, BC ; HL = (C7 >> 1) + C7 SRL H RR L ; HL = F1 SUB L LD C, A SBC A, H SUB C LD B, A ; BC = E2 - F1 = F2 LD A, D ; A = A7 = 138 - Year % 19 ADD A, A ; A = A7 * 2 ADD A, A ; A = A7 * 4 ADD A, D ; A = A7 * 5 ADD A, A ; A = A7 * 10 ADD A, D ; A = A7 * 11 = F3 SUB C ; A = F3 - (F2 % 256) LD C, A SBC A, B SUB C ; AC = F3 - F2 = F4 ; PHASE G: Unadjusted Epact ; Computes a variant of the unadjusted epact ; G3 = ((F4 - 2) % 30) + 2 ; See http://en.wikipedia.org/wiki/Epact ; Let G1 = F4 >> 1 [14..254] ; Let G2 = (((G1 >> 4) + G1) >> 4) << 1 ; Where G2 = ((F4 - 2) / 30) << 1 ; Let G3 = (G2 + F4) & 31 ; Where G3 = F4 - ((F4 - 2) / 30) * 30 = ((F4 - 2) % 30) + 2 RRA ; Carry = (F4 >> 8) LD A, C RRA ; A = F4 >> 1 LD E, A ; E = G1 [14..254] LD B, 31 RRA RRA RRA AND B ; A = G1 >> 3 RRA ; A = G1 >> 4 ADD A, E ; A = (G1 >> 4) + G1 RRA RRA RRA AND 30 ; A = ((F4 - 2) / 30) << 1 = G2 ADD A, C ; A = G2 + F4 AND B ; A = (G2 + F4) & 31 = G3 ; PHASE H: Compute Day-of-March of Day after Paschal Full Moon ; Computes a variant the number of days after the first of March of the Paschal Full Moon ; Let H1 = 19 + G3 - (G3 + Year % 19 / 11) / 31 ; Let H2 = (Year / 4) * 2 + F1 + 8192 - H1 LD C, A ; C = G3 SLA D ; Carry = 1 - (Year % 19) / 11 SBC A, 30 ; Carry = 1 - (G3 + (Year % 19) / 11) / 31 LD A, 237 SBC A, C ; A = 237 - G3 - (1 - (G3 + (Year % 19) / 11) / 31) LD C, A ; C = -H1, BC = (32 * 256) - H1 ADD HL, BC ; HL = F1 + 8192 - H1 POP DE ; DE = Year LD B, D LD A, E ; BA = Year RR B RRA AND 254 ; BA = (Year / 4) * 2 ADD A, L LD L, A LD A, H ADC A, B ; AL = H2 ; PHASE I: Compute Day-of-Week of Paschal Full Moon ; Computes the day of the week of the Paschal Full Moon so we can find Easter Sunday ; Let I1 = 3 - (Year % 4) ; Let I2 = H2 + I1 ; Let I3 = (I1 << 3) + ((H2 >> 6) & 7) + (H2 >> 9) + (H2 & 63) ; Where I3 % 7 = I2 % 7 ; Let I4 = ((I3 >> 3) + I3 + 4) >> 3 ; Where ((x + 4) >> 3) means (x / 8) rounding to nearest integer ; Let I5 = I3 + I4 ; Let I6 = (I3 + I5) & 7 ; Let I7 = I6 + H1 RRA ; Carry bit = (H2 >> 8) & 1 LD B, A ; B = H2 >> 9 LD A, E ; A = Year % 256 CPL ; A & 3 = 3 - (Year % 4) = I1 RLA ; A & 7 = (I1 << 1) + Carry AND 7 ; A = (I1 << 1) + ((H2 >> 8) & 1) LD H, A ; HL = (I1 << 9) + (H2 & 511) LD A, L ; A = H2 & 255 ADD HL, HL ADD HL, HL ; HL = (I1 << 11) + (H2 & 511) << 2 EX DE, HL ; HL = Year, D = (I1 << 3) + (H2 >> 6) & 7 LD E, 63 AND E ; A = H2 & 63 ADD A, B ; A = (H2 >> 9) + (H2 & 63) ADD A, D ; A = (I1 << 3) + ((H2 >> 6) & 7) + (H2 >> 9) + (H2 & 63) = I3 LD B, A ; B = I3 [0..221] RRA RRA RRA AND E ; A = I3 >> 3 ADD A, B ; A = (I3 >> 3) + I3 RRA RRA AND E RRA ; A = ((I3 >> 3) + I3) >> 3 ADC A, B ; A = (((I3 >> 3) + I3 + 4) >> 3) + I3 = I3 + I4 = I5 RRA RRA RRA ; A & 31 = I5 >> 3 ADD A, B AND 7 ; A = I6 = I3 % 7 = I2 % 7 SUB C ; A = I6 + H1 = I7 ; PHASE J: Compute Day-of-March of Easter ; Computes the date of Easter Sunday including the number of days after the last day of February ; Let J1 = I7 + (I7 / 32) LD D, A ; D = I7 CP 32 ; Carry = (I7 < 32) SBC A, -1 ; A = I7 + 1 - (I7 < 32) = J1 LD B, A ; B = J1 SUB D ; A = (I7 >= 32) ADD A, 3 ; A = (I7 >= 32) + 3 LD C, A ; C = Month LD A, D ; A = Day-of-March POP DE ; Restore DE RES 5, B ; B = Day-of-Month RET
As Al commented, an alternative ending would be to use my shorter/faster tail code which bends the "rules" slightly with a premature return instruction.
; PHASE J: Compute Day-of-March of Easter ; Cheeky alternative by Ian Taylor (ian@chilliant.com) POP DE ; Restore DE LD B, A ; B = I7 = Day-of-March LD C, 3 ; C = March CP 32 RET C RES 5, B INC B ; B = Day-of-April INC C ; C = April RET