Update (March 2014): A lot of the Z80 implementation has been superseded by the work of Al Petrofsky documented on another page.

Update (January 2011): At the end of last year I foolishly wrote: "I think the only significant improvements I can make to this code is by using a superoptimiser, which is non-trivial for such a large algorithm." Since then, I've gone back to first principles for the computation and come up with two "better" Z80 implementations. These replace the previously published code.

Computus is the calculation of Easter for any given year. For the purposes of this page, that means Easter Sunday in the Gregorian calendar according to the Book of Common Prayer of the Church of England.

Dr J R Stockton's excellent site covers most of the nuances of this computation, with one of his algorithms being (effectively):


      int easter_dm(int year) {
        // Based on EasterJRS at http://www.merlyn.demon.co.uk/estr-bcp.htm#A2008
        // Returns the "day of March"; > 31 for April
        int golden_number = year % 19;
        int x = year / 100;
        int q = 3 * (x + 1) / 4;
        int bcp_cypher = q - (13 + x * 8) / 25;
        x = (6 + ((5 * year) / 4) - q) % 7;
        int dm = 21 + (golden_number * 19 + bcp_cypher + 15) % 30;
        if (golden_number > 10) {
          if ((dm + 1) > 49)
            dm--;
        } else {
          if (dm > 49)
            dm--;
        }
        return dm + 1 + (66 - x - dm) % 7
      }
    

With a bit of refactoring, I rewrote this algorithm to use 16-bit unsigned arithmetic:


      void easter_u16(u16 year, u16* month, u16* day) {
        u16 a = year % 19;
        u16 b = year >> 2;
        u16 c = (b / 25) + 1;
        u16 d = (c * 3) >> 2;
        u16 e = ((a * 19) - ((c * 8 + 5) / 25) + d + 15) % 30;
        e += (29578 - a - e * 32) >> 10;
        e -= ((year % 7) + b - d + e + 2) % 7;
        d = e >> 5;
        *day = e - d * 31;
        *month = d + 3;
      }
    

Why stop there? If you're on a 16-bit machine, perhaps you don't have native division. So, using the "integer division by constants" ideas from Hacker's Delight:


      void easter_u16_nodiv(u16 year, u16* month, u16* day) {
        u16 a = year >> 1;
        u16 b = a >> 1;
        u16 c = b + (b >> 2);
        u16 d = (a + c + (c >> 4) + (c >> 5) + (c >> 10)) >> 4;
        u16 e = d & 255;
        u16 f = (year - e * 19) & 255;
        if (f >= 19) f = f - 19;
        u16 g = (b >> 1) + (b >> 3);
        u16 h = (g + (g >> 6) + (g >> 7)) >> 4;
        u16 i = (h * 25) & 255;
        u16 j = (b - i) & 255;
        if (j >= 25) h = h + 1;
        u16 k = (h * 3) >> 2;
        u16 l = (h * 8) + 5;
        u16 m = (l >> 1) + (l >> 3);
        u16 n = (m + (m >> 6) + (m >> 7)) >> 4;
        u16 o = l - (n * 25);
        if (o >= 25) n = n + 1;
        u16 p = (f + 5) * 3;
        u16 q = (f * 16) + k - n + p;
        u16 r = ((q >> 4) + (q >> 8)) & 254;
        u16 s = q - (r * 15);
        if (s >= 30) s = s - 30;
        u16 t = s * 16 + f + 53;
        u16 u = ((t >= 512) ? 27 : 28;
        u16 v = (year >> 15) + (year & 32767);
        v = (v >> 9) + (v & 511);
        v = v + u + b - k + 2;
        v = (v >> 9) + (v & 511);
        v = (v >> 6) + (v & 63);
        v = (v >> 3) + (v & 7);
        v = (v >> 3) + (v & 7);
        if (v != 7) u = u - v;
        *day = u;
        *month = 3;
        if (u & 32) {
          *day = u - 31;
          *month = 4;
        }
      }
    

Some of the above might need a bit of explanation:

The final step was to convert this algorithm into Z80 assembly. The original translation (by hand) weighed in at over 3000 T-cycles and 600 bytes of code, but after quite a bit of optimisation (again, by hand) I got it down to two variations. The first is the shortest code I could come up with (149 code bytes, 8361-8406 T-cycles) whilst the second is the fastest without lookup tables (1799-1843 T-cycles, 355 code bytes):


      ; EasterZ80_Short
      ;     Compute Gregorian Easter according to
      ;     Book of Common Prayer in Z80 assembly
      ;     Ian Taylor, January 2011
      ; 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)
      ;     All other registers preserved
      ; Constraints:
      ;     No memory usage, except 8 stack words
      ;     No use of IX, IY or shadow registers
      ;     No self-modifying code
      ;     Computation time: 8361-8406 T-cycles
      ;     Code bytes used: 149
      EasterZ80_Short:
          PUSH DE                 ; Save DE
          PUSH HL                 ; Push Year
          CALL EasterZ80_Div      ; Let T0 = Year % 19 ...
          DB 19                   ; A = Year % 19
          LD D, B                 ; D = 0
          LD E, A                 ; DE = T0
          POP HL                  ; Let T1 = Year / 4 ...
          PUSH HL                 ; HL = Year
          CALL EasterZ80_Div      ; Divide HL by following byte
          DB 4                    ; HL = Year / 4
          PUSH HL                 ; Push T1
          PUSH DE                 ; Push T0
          CALL EasterZ80_Div      ; Let T2 = (T1 / 25) + 1 ...
          DB 25                   ; HL = T1 / 25
          INC HL                  ; HL = T2
          PUSH HL                 ; Push T2
          LD A, 3                 ; Let T3 = (T2 * 3) / 4 ...
          CALL EasterZ80_Mul      ; HL = T2 * 2
          CALL EasterZ80_Div      ; HL = HL / 4
          DB 4                    ; HL = T3
          EX (SP), HL             ; Pop T2, Push T3
          LD A, 8                 ; Let T4 = (T0 * 19) - ((T2 * 8 + 5) / 25) + T3 + 15
          CALL EasterZ80_Mul      ; HL = T2 * 8
          LD C, 5                 ; BC = 5
          ADD HL, BC              ; HL = T2 * 8 + 5
          CALL EasterZ80_Div      ; HL = HL / 25
          DB 25                   ; HL = (T2 * 8 + 5) / 25
          EX DE, HL               ; DE = (T2 * 8 + 5) / 25
          LD A, 19                ; A = 19
          CALL EasterZ80_Mul      ; HL = T0 * 19
          SBC HL, DE              ; Carry guaranteed to be 0
          LD C, 15                ; BC = 15
          ADD HL, BC              ; HL = (T0 * 19) - ((T2 * 8 + 5) / 25) + 15
          POP DE                  ; Pop T3
          ADD HL, DE              ; HL = T4
          CALL EasterZ80_Div      ; Let T5 = T4 % 30
          DB 30                   ; A = T5
          POP BC                  ; Pop T0
          LD L, A                 ; HL = T5
          PUSH HL                 ; Push T5
          LD L, 16                ; Let T6 = (15306 - T0 - T5 * 16) / 512
          CALL EasterZ80_Mul      ; HL = T5 * 16
          PUSH DE                 ; Push T3
          EX DE, HL               ; DE = T5 * 16
          LD HL, 15306            ; HL = 15306
          SBC HL, BC              ; Carry guaranteed to be 0
          SBC HL, DE              ; Carry guaranteed to be 0
          LD A, H                 ; A = HL >> 8
          RRA                     ; A = HL >> 9 (Carry was 0)
          POP DE                  ; Pop T3
          POP BC                  ; Pop T5
          ADD A, C                ; Let T7 = T5 + T6
          LD C, A                 ; BC = T7
          POP HL                  ; Pop T1
          ADD HL, BC              ; Let T8 = T7 + T1 - T3 + (Year % 7) + 1
          SBC HL, DE              ; Carry guaranteed to be 0
          EX DE, HL               ; DE = T1 + T7 - T3 (Carry was 0)
          POP HL                  ; Pop Year
          PUSH BC                 ; Push T7
          PUSH HL                 ; Push Year
          CALL EasterZ80_Div      ; Divide HL by following byte
          DB 7                    ; A = Year % 7
          LD H, B                 ; H = 0
          LD L, A                 ; HL = (Year % 7)
          ADD HL, DE              ; HL = T8
          INC HL                  ; HL = (Year % 7) + 1
          CALL EasterZ80_DivC     ; Let T9 = T8 % 7 (C was still 7)
          CPL                     ; Let T10 = T7 - T9 - 1
          POP HL                  ; Pop Year
          POP BC                  ; Pop T7
          ADD A, C                ; A = T10
          POP DE                  ; Restore DE
          LD B, A                 ; B = T10
          LD C, 3                 ; C = March
          CP 32                   ; Compare with 32
          RET C                   ; Return if T10 < 32
          RES 5, B                ; B = T10 - 32
          INC B                   ; B = T10 - 31
          INC C                   ; C = April
          RET                     ; Return
      EasterZ80_Mul:              ; Let HL = HL * A : Let A = 0 : Let B = 0
          PUSH DE                 ; Save DE
          EX DE, HL               ; DE = HL
          LD HL, 0                ; HL = 0
          LD B, 8                 ; Eight bits
      L1: ADD HL, HL              ; HL <<= 1
          ADD A, A                ; A <<= 1
          JR NC, L2               ; Skip if MSB was 0
          ADD HL, DE              ; HL = HL + DE
      L2: DJNZ L1                 ; Loop for each bit in A
          POP DE                  ; Restore DE
          RET                     ; Takes up to 415 T-Cycles
      EasterZ80_Div:              ; Divide by byte following 'CALL'
          EX (SP), HL             ; Swap HL with return PC
          LD C, (HL)              ; C = Following data byte
          INC HL                  ; Skip data byte
          EX (SP), HL             ; Swap HL with return PC
      EasterZ80_DivC:             ; Let A = HL % C : Let HL = HL / C : Let B = 0
          XOR A                   ; A = 0
          LD B, 16                ; Sixteen bits
      L3: ADD HL, HL              ; HL <<= 1
          ADC A, A                ; A <<= 1 with carry
          CP C                    ; Compare with divisor
          JR C, L4                ; Skip if A < divisor
          SUB C                   ; A = A - divisor
          INC L                   ; HL = HL + 1 (HL was even)
      L4: DJNZ L3                 ; Loop for each bit in HL
          RET                     ; Takes up to 768 T-Cycles
    
I'm particularly happy with the fast version below as it uses the undocumented Z80 instruction SLIA (shift left inverted arithmetic):

      ; EasterZ80_Fast
      ;     Compute Gregorian Easter according to
      ;     Book of Common Prayer in Z80 assembly
      ;     Ian Taylor, January 2011
      ; 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)
      ;     All other registers preserved
      ; Constraints:
      ;     No memory usage, except 4 stack words
      ;     No use of IX, IY or shadow registers
      ;     No self-modifying code
      ;     No subroutine calls
      ;     Computation time: 1799-1843 T-cycles
      ;     Code bytes used: 355
      EasterZ80_Fast:
          PUSH DE         ; Save DE
          LD D, H         ; Let T0 = Year >> 1 ...
          LD A, L
          SRL D
          RRA
          LD B, D
          LD C, A         ; BC = T0
          SRL D           ; Let T1 = T0 >> 1 ...
          RRA
          LD E, A         ; DE = T1
          PUSH DE         ; Push T1
          PUSH HL         ; Push Year
          LD H, D
          LD L, E         ; HL = T1
          SRL D           ; Let T2 = T1 + (T1 >> 2) ...
          RRA
          SRL D
          RRA
          LD E, A         ; DE = T1 >> 2
          ADD HL, DE      ; HL = T2
          LD D, H         ; Let T3 = (T0 + T2 + (T2 >> 4) + (T2 >> 5) + (T2 >> 10)) >> 4 ...
          LD A, L
          ADD HL, BC
          SRL D
          RRA
          SRL D
          RRA
          LD B, D
          SRL D
          RRA
          SRL D
          RRA
          LD E, A         ; DE = T2 >> 4
          ADD HL, DE
          SRL D
          RRA
          LD E, A         ; DE = T2 >> 5
          ADD HL, DE
          LD D, 0
          LD E, B         ; DE = T2 >> 10
          ADD HL, DE
          LD A, L
          SRL H
          RRA
          SRL H
          RRA
          SRL H
          RRA
          SRL H
          RRA             ; A = T3
          LD B, A         ; Let T4 = T3 & 255 ...
          ADD A, A        ; Let T5 = (Year - T4 * 19) & 255 ...
          LD C, A
          ADD A, A
          ADD A, A
          ADD A, A
          ADD A, B
          ADD A, C        ; A = (T4 * 19) & 255
          NEG             ; A = -(T4 * 19) & 255
          POP HL          ; Pop Year
          ADD A, L        ; A = T5
          CP 19           ; If T5 >= 19 Then Let T5 = T5 - 19
          JR C, L1
          SUB 19
      L1: LD C, A         ; C = T5
          EX (SP), HL     ; Let T6 = (T1 >> 1) + (T1 >> 3) ...
          PUSH HL         ; Pop T1, Push Year, Push T1
          LD B, L         ; B = T1 & 255
          LD A, L
          SRL H
          RRA
          LD D, H
          LD E, A
          SRL H
          RRA
          SRL H
          RRA
          LD L, A
          ADD HL, DE      ; HL = T6
          LD D, 0         ; Let T7 = (T6 + (T6 >> 6) + (T6 >> 7)) >> 4 ...
          LD E, H
          LD A, L
          ADD A, A
          EX DE, HL
          ADC HL, HL
          EX DE, HL       ; DE = T6 >> 7
          ADD HL, DE
          ADD A, A
          EX DE, HL
          ADC HL, HL      ; HL = T6 >> 6
          ADD HL, DE
          XOR A
          ADD HL, HL
          ADD HL, HL
          ADD HL, HL
          ADC A, A
          ADD HL, HL
          ADC A, A
          LD L, H
          LD H, A         ; HL = T7
          LD A, L         ; Let T8 = (T7 * 25) & 255 ...
          ADD A, A
          ADD A, A
          ADD A, A
          LD D, A
          ADD A, A
          ADD A, D
          ADD A, L        ; A = T8
          SUB B           ; Let T9 = (T1 - T8) & 255 ...
          NEG             ; A = T9
          CP 25           ; If T9 >= 25 Then Let T7 = T7 + 1
          JR C, L2
          INC HL
      L2: INC HL          ; Let T7 = T7 + 1 ...
          LD D, H         ; Let T10 = (T7 * 3) >> 2 ...
          LD E, L
          ADD HL, HL
          EX DE, HL       ; DE = T7 * 2
          ADD HL, DE      ; HL = T7 * 3
          LD A, L
          SRL H
          RRA
          SRL H
          RRA
          LD L, A         ; HL = T10
          PUSH HL         ; Push T10
          EX DE, HL       ; DE = T10
          INC HL          ; Let T11 = (T7 * 8) + 5 ...
          ADD HL, HL      ; HL = T11 >> 1
          LD B, L
          SLIA B          ; Equivalent to SLA B : INC B
          LD D, H         ; Let T12 = (T11 >> 1) + (T11 >> 3) ...
          LD A, L
          SRL D
          RRA
          SRL D
          RRA
          LD E, A
          ADD HL, DE      ; HL = T12
          LD D, H         ; Let T13 = (T12 + (T12 >> 6) + (T12 >> 7)) >> 4 ...
          LD E, L
          ADD HL, HL
          LD A, H
          ADD HL, HL
          ADD A, H
          LD L, A
          LD H, 0
          ADD HL, DE      ; HL >> 4 = T13
          LD D, L
          ADD HL, HL
          ADD HL, HL
          ADD HL, HL
          ADD HL, HL      ; H = T13
          LD E, H         ; Let T14 = T11 - (T13 * 25) ...
          LD A, H
          ADD A, A
          ADD A, A
          ADD A, A
          ADD A, H
          LD H, A         ; H = (T13 * 9) & 255
          LD A, D
          AND 240         ; A = (T13 * 16) & 255
          ADD A, H
          SUB B           ; (-A & 255) = T14
          CP 232          ; If T14 >= 25 Then Let T13 = T13 + 1
          JR NC, L3
          INC E
      L3: LD A, C         ; Let T15 = (T5 + 5) * 3 ...
          ADD A, A        ; Let T16 = (T5 * 16) + T10 - T13 + T15 ...
          ADD A, A
          ADD A, A
          LD H, 0
          LD L, A
          LD D, H         ; DE = T13
          ADD HL, HL      ; HL = T5 << 4
          LD A, 5
          ADD A, C
          LD B, A
          ADD A, A
          ADD A, B        ; A = T15
          SBC HL, DE
          LD E, A         ; DE = T15
          ADD HL, DE
          POP DE          ; Pop T10
          ADD HL, DE      ; HL = T16
          LD A, H         ; Let T17 = ((T16 >> 4) + (T16 >> 8)) & 254 ...
          LD B, L
          ADD HL, HL
          ADD HL, HL
          ADD HL, HL
          ADD HL, HL
          ADD A, H
          AND 254         ; A = T17
          POP HL          ; Pop T1
          SBC HL, DE      ; HL = T1 - T10
          PUSH HL         ; Push T1-T10
          LD H, 0         ; Let T18 = T16 - (T17 * 15) ...
          LD L, A         ; HL = T17
          LD D, H
          LD E, L         ; DE = T17
          ADD HL, HL
          ADD HL, HL
          ADD HL, HL
          ADD HL, HL
          SBC HL, DE      ; HL = T17 * 15
          LD A, B
          SUB L           ; A = T18
          CP 30           ; If T18 >= 30 Then Let T18 = T18 - 30
          JR C, L4
          SUB 30
      L4: LD B, A         ; Let T19 = T18 * 16 + T5 + 53 ...
          ADD A, A
          ADD A, A
          ADD A, A
          LD H, D         ; H = 0
          ADD A, A
          RL H
          LD L, A         ; HL = T18 * 16
          LD A, 53
          ADD A, C        ; A = T5 + 53
          LD E, A         ; DE = T5 + 53
          ADD HL, DE      ; HL = T19
          LD A, H         ; If T19 >= 512 Then T20 = Let T18 + 27 Else Let T20 = T18 + 28
          RRA
          CPL
          ADD A, 29
          ADD A, B        ; A = T20
          LD B, D         ; B = 0
          POP DE          ; Let T21 = (Year >> 15) + (Year & 32767) ...
          POP HL          ; Pop Year
          PUSH HL         ; Push Year
          BIT 7, H
          JR Z, L5
          RES 7, H
          INC HL
      L5: LD C, H         ; Let T21 = (T21 >> 9) + (T21 & 511) ...
          RR C
          LD H, B         ; H = 0
          RL H
          ADD HL, BC      ; HL = T21
          SCF             ; Let T21 = T21 + T20 + T1 - T10 + 2 ...
          ADC HL, DE
          LD C, A         ; BC = T20
          SCF
          ADC HL, BC      ; HL = T21
          LD C, H         ; Let T21 = (T21 >> 9) + (T21 & 511) ...
          RR C
          LD H, B
          RL H
          ADD HL, BC      ; HL = T21
          LD C, A         ; BC = T20
          LD A, L         ; Let T21 = (T21 >> 6) + (T21 & 63) ...
          AND 63
          ADD HL, HL
          ADD HL, HL
          ADD A, H        ; A = T21
          LD D, 7         ; Let T21 = (T21 >> 3) + (T21 & 7) ...
          LD L, A
          SRL L
          SRL L
          SRL L
          AND D
          ADD A, L        ; A = T21
          LD L, A         ; Let T21 = (T21 >> 3) + (T21 & 7) ...
          SRL L
          SRL L
          SRL L
          AND D
          ADD A, L
          LD L, A         ; A = T21
          CP D            ; If T21 != 7 Then Let T20 = T20 - T21
          LD A, C
          JR Z, L6
          SUB L
      L6: POP HL          ; Pop Year
          POP DE          ; Restore DE
          LD B, A         ; B = T20
          LD C, 3         ; C = March
          CP 32
          RET C
          RES 5, B
          INC B           ; B = T20 - 31
          INC C           ; C = April
          RET
    
With thanks to Dr J R Stockton.