Assignment #2

A. Algorithm to calculate Easter day for the year 2013:
X = 2013 1. Divide X by 19 to obtain a quotient (which will be ignored) and a remainder A.
2013/19 = quotient 105 and remainder 18.
A = 18 2. Divide X by 100 to obtain a quotient B and a remainder C.
2013/100 = quotient 20 and remainder 13.
B =20; C = 13. 3. Divide B by 4 to obtain a quotient D and a remainder E
20/4 = quotient 5 and remainder 0.
D = 5; E = 0. 4. Divide (8*B + 13) by 25 to obtain a quotient G and remainder (which will be ignored).
(8*20 + 13)/25 = quotient 6 and remainder 23
G = 6. 5. Divide (19*A+B-D-G+15) by 30 to obtain a quotient which will be ignored and a remainder L.
(19*18+20-5–6+15)/30 = quotient 12 and remainder 6
H = 6. 6. Divide (A+11*H) by 310 to obtain a quotient M and a remainder (which will be ignored).
(18+11*6)/310 = quotient 0 and remainder 174.
M = 0 7. Divide C by 4 to obtain a quotient J and a remainder K.
13/4 => quotient 3; remainder 1
J = 3 and K = 1 8. Divide (2*E + 2*J - K – H + M + 32) by 7 to obtain a quotient (which will be ignored) and a remainder L.
(2*0 + 2*3 – 1 – 6 + 0 + 32)/7 = quotient 4 and remainder 3.
L = 3. 9. Divide (H - M + L + 90) by 25 to obtain a quotient N and a remainder (which will be ignored).
(6 – 0 + 3 + 90)/25 = quotient 3 and remainder 24.
N = 3. 10. Divide (H – M + L + N + 19)/32 to obtain a quotient (which will be ignored and a remainder P.
(6 – 0 +3+3+19)/32 = remainder 31 and quotient 0.
P = 31
Easter Sunday is on Pth day of the Nth month.
Easter Sunday is on March 31st 2013.

B. Using Euclid’s algorithm for determining GCD determine the following for inputs 60 and 16.
Step 1: Input larger value and smaller value (60 and 16).
Step 2: Divide larger by smaller and keep remainder. 60/16 = remainder 12.
Step 3a: If remainder is not 0, then reset larger to the value of smaller (16) and reset smaller to the remainder (12) and repeat step 2. 16/12 = remainder 4.
Step 3b: If remainder is not 0, then reset larger to value of smaller (12) and reset smaller to the remainder (4) and repeat step 2. 12/4 = remainder 0
If remainder is 0 then GCD is smaller (4)
Based on the above calculations the final findings are as below: 1. Step 2 was executed 3 times. 2. The final value of larger = 12. 3. The final value of smaller = 4. 4. GCD = 4