The Museum of HP Calculators

HP Forum Archive 11

[ Return to Index | Top of Index ]

Easter day challenge
Message #1 Posted by hugh on 3 Apr 2003, 7:45 p.m.

it will soon be easter. this year, easter sunday is on April 20. the idea is to write an easter sunday calculation program valid for years 1900-2099 on the 25C (ie in 50 steps or less!).

to make it more interesting, i've already had a go, but my answer is incomplete. completely different approaches are allowed as long as they work! i've managed to simplify a formula down to the following logic:

d =(204 - 11*(y%19))%30; if (d < 28) ++d; return d+27-(5*y/4+d)%7;

where `y' is the input year. the result `d' is the day number from march, where d > 31 implies april (d-31). after some struggle, i write:

sto0 1 9 / int 1 9 * rcl0 - 1 1 * 2 0 4 + sto1 3 0 / int 3 0 * sto-1 2 8 sto2 rcl1 x>=y? gto35 1 + rcl0 5 * 4 / int sto-2 + 7 / int 7 * rcl2 +

which works but always returns the answer + 1 :-) be sure to test 1954 (which is April 18).

happy easter!

      
Re: Easter day challenge
Message #2 Posted by hugh on 7 Apr 2003, 5:33 p.m.,
in response to message #1 by hugh

i finally done this in 46 steps. wow, 3 steps to party! but the program's about as vicious as a cornered rat.

            
Re: Easter day challenge
Message #3 Posted by glynn on 7 Apr 2003, 11:03 p.m.,
in response to message #2 by hugh

Did you scope out the algorithm at:

http://aa.usno.navy.mil/faq/docs/easter.html

Quoting here:

Computing the Date of Easter:

The rule is that Easter is the first Sunday after the first ecclesiastical full moon that occurs on or after March 21. The lunar cycles used by the ecclesiastical system are simple to program. The following algorithm will compute the date of Easter in the Gregorian Calendar system.

Please note the following: This is an integer calculation. All variables are integers and all remainders from division are dropped.

The algorithm uses the year, y, to give the month, m, and day, d, of Easter. The symbol * means multiply.

c = y / 100

n = y - 19 * ( y / 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 = y + y / 4 + i + 2 - c + c / 4

j = j - 7 * ( j / 7 )

l = i - j

m = 3 + ( l + 40 ) / 44

d = l + 28 - 31 * ( m / 4 )

For example, using the year 2010,

y=2010,

c=2010/100=20,

n=2010 - 19 x (2010/19) = 15,

etc. resulting in Easter on April 4, 2010.

The algorithm is due to J.-M. Oudin (1940) and is reprinted in the Explanatory Supplement to the Astronomical Almanac, ed. P. K. Seidelmann (1992). See Chapter 12, "Calendars", by L. E. Doggett.

                  
Re: Easter day challenge
Message #4 Posted by hugh on 8 Apr 2003, 1:13 p.m.,
in response to message #3 by glynn

hi glynn,

i had seen the oudin version. but it is way to large for 50 steps. instead i found a formular by Carter valid only for 1900-2099 then simplified it a bit more and tied that.

            
Re: Easter day challenge
Message #5 Posted by eamonn on 8 Apr 2003, 3:02 a.m.,
in response to message #2 by hugh

Hugh,

I had a look at your original algorithm and ran a quick check of the values for d that are generated before the 'if' statement. Oddly enough, for years in the range 1900 to 2099, d never equals 27. So, your algorithm can be rewritten:


d =(204 - 11*(y%19))%30;
if (d < 27) ++d;
return d+27-(5*y/4+d)%7;

This leads to a simple change to your original HP-25C code - replace the '8' in step 28 with a '7' and now the result is no longer off by one.

I also experimented with storing some of the constants in the algorithm in memory registers. Doing this allowed me to free up about 10 lines of program space, which in turn allows an epilogue to your code to return the month in the X register and the day in the Y register.

Unfortunately, I don't have an actual HP-25C myself, but I was able to test the code on the HP-25C simulator at http://www.rskey.org/hp25.htm and it seems to work fine for all they years I threw at it. I've pasted the code below. Note that the registers need to be initialized with the values shown before the program is run for the first time. Since the program doesn't modify R3 to R7, they do not need to be initialized again for subsequent runs of the program.

Good challenge.

Eamonn.

Store the following values in registers R3 to R7: 

R3 = 19
R4 = 204
R5 = 30
R6 = 27
R7 = 1.25

And here's the code, with some comments. 


01  sto0  ; Store year in R0 for later
02  rcl3  ; R3 = 19
03  / 
04  int 
05  rcl3 
06  * 
07  rcl0 
08  -     ; X = -(year mod 19)
09  1
10  1
11  * 
12  rcl4  ; R4 = 204
13  + 
14  sto1  ; 204 - 11 * (year mod 19) stored in R1
15  rcl5  ; R5 = 30 
16  / 
17  int 
18  rcl5
19  *
20  sto-1 ; d stored in R1
21  rcl6  ; R6 = 27
22  sto2  ; store 27 in R2 for later
23  rcl1  ; recalls d
24  x>=y? ; if d>=27 then ...
25  gto28 ;    ... goto 27.
26  1     ; Add 1 to d
27  + 
28  rcl0  ; Recall the year
29  rcl7  ; R7 = 5/4 = 1.25
30  *     ; X = y * 5/4
31  int   ; X = floor (y * 5/4)
32  sto-2 ; Store 27 - floor(y * 5/4) in R2
33  +     ; X = d + floor(y * 5/4)
34  7     
35  / 
36  int 
37  7 
38  *     ; X = 7 * floor( (d + (y * 5/4) ) / 7 )
39  rcl2  ; X = 28 - (y * 5/4)
40  +     ; X = 28 - (y * 5/4) + 7 * floor( (d + (y * 5/4) ) / 7 ), the result from the original code.
41  3
42  1
43  x<y   ; result > 31?
44  gto48 ; if so, then skip to line 48
45  Rv    ; Place result back in X
46  3     ; Month is march
47  gto00 ; Done
48  -     ; Subtract 31 from result
49  4     ; Month is April
                  
Re: Easter day challenge
Message #6 Posted by hugh on 8 Apr 2003, 1:11 p.m.,
in response to message #5 by eamonn

hey, i like it!

i didnt think of the 27 trick. you had seen how i had tried to reuse the same constant but out by 1. also, the idea of storing some of the constants in registers and then using the space to discriminate march/april is a cool idea. what i did in the end is recode the problem again using FRAC instead of INT. last time i tried this (which saves space) it got the wrong answer for certain cases. you see frac(x/7)*7 is often wrong. but x - int(x/7)*7 is always right. this is due to small rounding errors. here's my version:

sto1 1 9 / frac 2 0 9 * 2 0 4 - chs 3 0 / frac 3 1 * 2 8 x<>y x>=y? gto 29 1 + rcl1 5 * 4 / int sto2 + 7 / int 7 * rcl2 - + 1 -

the beauty is /30 then *31 which makes the number ever-so-slightly larger. later on the INT throws away the oversize part and there is no loss of bits.

but wait! i can use your 27 idea, because i do the -1 on the end here. this now gives me 5 spare steps. the question is, can i put in the month discriminator as well!

i'll try that later.

                        
Re: Easter day challenge
Message #7 Posted by eamonn on 9 Apr 2003, 2:40 a.m.,
in response to message #6 by hugh

Looks good Hugh, though I think you'll have difficulties getting the month and day displayed correctly with only five steps remaining. I both like and dislike the multiply by 31 trick - kinda ugly, but it gets the job done and it looks like it should work for all cases. Admittedly, when you have limitations such as having only 50 steps available, you sometimes have to resort to tricks like this. By the way, I really like the way you calculate the d+27-(5*y/4+d)%7 part of the algorithm. Not obvious, and it took a few minutes to write out the equations to understand what you were doing, but 100% correct.

With your changes bringing the program down to 44 steps, I'm guessing, you could store the constants 204 and 209 in registers, freeing up four steps and allowing the display of the month and date at the end. This is more efficient the five registers I used. Also, I see you only use two storage registers in your new code, compared to three in the original code.

It's going to be hard to beat that.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall