Computing the day of the week.

My first computer program

It must be the autumn of 1983. When I visited a friend of mine (a radio amateur), he showed me his new toy, the Sinclair ZX-81. one of the cheapest home computers at the time. This was not the first time a saw a computer and I had definitely entered some BASIC commands before. A year earlier I had visited an uncle of mine who was the proud owner of an Acorn Atom. It showed text on a TV-screen. As I recall, I entered a simple BASIC program to solve quadratic equations and I played with mathematical functions that could be evaluated in BASIC. And there was a version of Space Invaders that you could load from cassette tape. This was all very fascinating and I knew that I was going to have a computer sooner or later.

But back to the ZX-81. This too could show text and simple graphics on a TV screen and it too could load games from cassettes. It too had BASIC in ROM. This could be yours for less than 200 guilders including the 16 kB RAM extension that you were almost required to have. This machine could run a simple flight simulator program and I was truly amazed that this was possible on such a simple computer.

But programming was the thing I was most interested in, more than playing games. Calculating the week day for any given date was a problem that I should be able to tackle and so I did. I think I wrote the program down on paper after I ran it successfully on the ZX81, so I could enter it later when I did get a computer. The program may have looked a bit like the listing below. The original version certainly did not have REM statements, that would be a waste of memory (and would be too tedious to type on the ZX-81) and the original was in Dutch. But the algorithm was definitely very similar to what is shown, including the long clumsy lists of IF-statements. I did not know arrays at the time. I certainly did not use a fancy formula, such as Zeller's congruence. Download the program here to try in with your own BASIC interpreter.

 10 REM COMPUTE DAY OF THE WEEK
 20 PRINT "ENTER DAY (1-31)"
 30 INPUT D
 40 IF D>=1 AND D<=31 THEN GOTO 70
 50 PRINT "DAY OUT OF RANGE"
 60 GOTO 20
 70 PRINT "ENTER MONTH (1-12)"
 80 INPUT M
 90 IF M>=1 AND M<=12 THEN GOTO 120
100 PRINT "MONTH OUT OF RANGE"
110 GOTO 70
120 PRINT "ENTER YEAR (1901-2099)"
130 INPUT Y
140 IF Y>=1901 AND Y<=2099 THEN GOTO 170
150 PRINT "YEAR OUT OF RANGE"
160 GOTO 120
170 REM SET L=1 FOR LEAP YEAR, OTHERWISE LET L=0
180 LET L=0
190 IF 4*INT(Y/4)=Y THEN LET L=1
200 REM ADD NUMBER OF YEARS TO DAY, EACH YEAR STARTS A DAY LATER
210 LET D=D+Y
220 REM ADD NUMBER OF LEAP YEARS BEFORE THIS YEAR
230 LET D=D+INT((Y-1)/4)
240 REM ADD DAYS OF PRECEDING MONTHS
250 IF M>1 THEN LET D=D+31
260 IF M>2 THEN LET D=D+28+L
270 IF M>3 THEN LET D=D+31
280 IF M>4 THEN LET D=D+30
290 IF M>5 THEN LET D=D+31
300 IF M>6 THEN LET D=D+30
310 IF M>7 THEN LET D=D+31
320 IF M>8 THEN LET D=D+31
330 IF M>9 THEN LET D=D+30
340 IF M>10 THEN LET D=D+31
350 IF M>11 THEN LET D=D+30
360 REM THE FOLLOWING ADDITION WAS FOUND BY TRIAL AND ERROR
370 LET D=D+5
380 REM NOW DO MODULO 7
390 LET D=D-7*INT(D/7)
400 IF D=0 THEN LET D$="SUNDAY"
410 IF D=1 THEN LET D$="MONDAY"
420 IF D=2 THEN LET D$="TUESDAY"
430 IF D=3 THEN LET D$="WEDNESDAY"
440 IF D=4 THEN LET D$="THURSDAY"
450 IF D=5 THEN LET D$="FRIDAY"
460 IF D=6 THEN LET D$="SATURDAY"
470 PRINT D$
  

The algorithm is explained as follows:

• Weekdays form a cycle of 7 days. We will have the same weekday 7 days from now, 14 days from now or any multiple of 7 days from now. If you count the days from a given start date (which is for example a Sunday) and the total is a multiple of 7, then that day must also be a Sunday. If it is one more than a multiple of 7, then that day must be a Monday. And so on. So the weekday is determined by the remainder when you divide the total number of days by 7. This is often called the modulo operation. The assignment statement at line 390 is computing the remainder (or modulo) of the number of days divided by 7. This remainder can be any number between 0 and 6 and each number corresponds to a weekday, the name of which which we assign in lines 400-460.
• So before taking the remainder, the variable D corresponds to the number of days passed since a given start date. Which start date? We don't care, as long as it is a Sunday.
• As addition is commutative, it is completely irrelevant in which order we add the various numbers to D.
• When we input D in line 30, it contains the number of days since the last day of the previous month.
• In lines 250-350 we add to D the number of days in any months before the current date. If the current date is in February, we add the days in January (only M>1 is true), if the current date is in December, we add all the days in the months January to December (everything including M>11 is true). Note that for February we count 28+L days, where L can be 0 or 1, depending on the leap year. With these lines and with the original input value of D, we have counted all days since the last day of the previous year.
• In line 210 we are adding the days of the years. You might expect something like D=D+365*Y, but this makes the number unnecessarily large (and in some versions of BASIC you may cause integer overflow). 365 is 52 weeks plus one day and for our purpose we may forget about the 52 whole weeks and we only have to count one day for each year. Each leap year has yet another day, which we count in 230. We count the leap days in previous years. The leap day in the current year is taken care of by the L variable.
• The addition in line 370 counts the days since the hypothetical start data to make the computation come out. It was found by trial and error.
• This program counts every fourth year as a leap year, which is not the correct rule for the Gregorian calendar. But between 1901 and 2099 every fourth year is a leap year, so the program checks we are in this range (see line 140).
• The program does not check that all entered numbers are integers and it does not check that the day number is valid for a given month.

Using arrays

Early in 1984 our family bought a used Texas Instruments TI-99/4A computer. This also had BASIC in ROM and it had 16kB of RAM, which I knew was enough. As opposed to the ZX-81 it had a real keyboard, colour graphics and sound. It came with three game cartridges: Munch Man, TI Invaders and Parsec and we spent many hours with these games. But for me programming was the main subject and I would soon be quite disappointed.

The TI computer had its own BASIC dialect. On the one hand it had many more features than ZX-81 BASIC, but on the other hand, it lacked some features that ZX-81 BASIC did have. And I thought: if the ZX-81 has it, every other computer must have it too. Like the ZX-81, the TI supported just one statement per line, but the IF statement could not have a statement after THEN, but just a line number (and you could specify another line number with ELSE). By the way, this is what ANSI Minimal BASIC specified and many early BASIC version on mainframes and minicomputers had it that way. As my original program contained many statements after IF..THEN, this was the first stumbling block. I could rewrite the program by using additional lines between the IF statements and then skip each of these lines in the IF statement, like this:

250 IF M<=1 THEN 260
255 D=D+31		 
260 IF M<=2 THEN 270
...			
  

But I did not feel like almost doubling the number of lines in the program. But after a little bit of learning, I came up with a solution that used arrays. The program may have looked like this one

  
100 REM COMPUTE DAY OF THE WEEK
110 DIM H(12)
120 H(1)=0
130 FOR I=2 TO 12
140 READ D
150 H(I)=H(I-1)+D
160 NEXT I
170 DIM D$(7)
180 FOR I=1 TO 7
190 READ D$(I)
200 NEXT I
210 INPUT "ENTER DAY (1-31)";D
220 IF (D>=1) * (D<=31) THEN 250
230 PRINT "DAY OUT OF RANGE"
240 GOTO 210
250 INPUT "ENTER MONTH (1-12)";M
260 IF (M>=1) * (M<=12) THEN 290
270 PRINT "MONTH OUT OF RANGE"
280 GOTO 250
290 INPUT "ENTER YEAR (1901-2099)";Y
300 IF (Y>=1901) * (Y<=2099) THEN 330
310 PRINT "YEAR OUT OF RANGE"
320 GOTO 290
330 REM IF CURRENT YEAR IS LEAP YEAR AND WE ARE IN MARCH OR LATER, ADD A DAY
340 IF (4*INT(Y/4)<>Y) + (M<3) THEN 360
350 D=D+1
360 REM ADD NUMBER OF YEARS TO DAY, EACH YEAR STARTS A DAY LATER
370 D=D+Y
380 REM ADD NUMBER OF LEAP YEARS BEFORE THIS YEAR
390 D=D+INT((Y-1)/4)
400 REM ADD NUMBER OF DAYS IN PRECEDING MONTHS.
410 D=D+H(M)
420 REM THE FOLLOWING ADDITION WAS FOUND BY TRIAL AND ERROR
430 D=D+5
440 REM NOW DO MODULO 7
450 D=D-7*INT(D/7)
460 PRINT D$(D+1)
470 END
480 REM DAYS IN MONTHS JAN-NOV
490 DATA 31,28,31,30,31,30,31,31,30,31,30
500 REM NAMES OF DAYS
510 DATA "SUNDAY","MONDAY","TUESDAY","WEDNESDAY","THURSDAY","FRIDAY","SATURDAY"
    

This program, may run unmodified on the TI-99/4A, except that it required a colon after the input prompt instead of a semicolon. It only uses the form of the IF-statement with a line number after THEN and I replaced AND and OR (that TI-Basic did not have) with * and +, as was commonly done on this machine.

The algorithm itself is the same as in the first program, but it uses two arrays. Both are read from DATA lines in two loops at the start of the program.

• The D$ array contains the names of the weekdays, so if we have the day modulo 7, we can use that as an index into the array, instead of using many IF statements.
• The H array contains the total of days in the months preceding any given month. The number of days in each month is read from data lines and it is added to the previous number before storing it into the array, so the array contains totals, not the number of days in a single month. Now we still have to take care of the leap day in the current year. The IF-statement in line 340 and the assignment in line 350 take care of that.

No, the disappointment about programming on the TI computer was not caused by the need to do a bit of extra learning to port my program to it. It was caused by the way the machine could not be programmed in machine code and many of the hardware features simply could not be used without buying additional expensive cartridges.

Zeller's congruence

Now most programs use a formula known as Zeller's congruence to compute the day of the week, like this program does.

10 REM COMPUIE DAY OF THE WEEK
20 DIM D$(7)
30 FOR I=1 TO 7:READ D$(I):NEXT I
40 INPUT "ENTER DAY (1-31)";D
50 IF D<1 OR D>31 THEN PRINT "DAY OUT OF RANGE":GOTO 40
60 INPUT "ENTER MONTH (1-12)";M
70 IF M<1 OR M>12 THEN PRINT "MONTH OUT OF RANGE":GOTO 60
80 INPUT "ENTER YEAR (1582-2999)";Y
90 IF Y<1582 OR Y>2999 THEN PRINT "YEAR OUT OF RANGE":GOTO 80
100 IF M<3 THEN M=M+12:Y=Y-1
110 D=D+5+INT(13*(M+1)/5)+Y+INT(Y/4)-INT(Y/100)+INT(Y/400)
120 D=D-7*INT(D/7)+1: REM D MOD 7 + 1
130 PRINT D$(D)
140 INPUT "ANOTHER DAY (Y/N)";Y$
150 IF Y$="Y" THEN GOTO 40
160 END
170 DATA "MONDAY","TUESDAY","WEDNESDAY","THURSDAY","FRIDAY","SATURDAY","SUNDAY"  
   

This program implements the full Gregorian date rule, as opposed to the previous two programs. The computation of the weekday is done in just three lines: 100-120, so let's explain it

• Line 120 is the modulo 7 operation, just as we did in the other programs. We add 1 to it, to get an array index 1 to 7 out of it.
• Line 100 is a clever trick to remove the need to handle leap days in the current year in a special way. In the previous program we counted leap years prior to the current year and treated the leap day in the current year specially (only if the current year is a leap year and the month is after February). What we do in line 100: if the month number is lower than 3 (before March), we subtract one from the year and add 12 to the month. This way we treat January and February as months 13 and 14 of the previous year. From then on, we can always count any leap day in the current year.
• Line 110 contains Zeller's congruence itself. It contains seven terms, so we look at them one by one:
  • D is the day number in the current month. We have seen that before.
  • Y is the year number. Each year contributes 1 more day to the total, because we can ignore the 52 full weeks. We had that in our previous program too.
  • INT(Y/4) is the number of leap years. We include the current year. In our previous programs we had INT((Y-1)/4) instead.
  • But wait, in the Gregorian calendar, the years divisible by 100 are not leap years, so we subtract INT(Y/100).
  • But the years divisible by 400 are leap years after all, so add INT(Y/400).
  • 5 is not part of Zeller's original formula. It is used to make D MOD 7 = 0 come out on a Monday (first weekday in ISO numbering), instead of a Saturday as in the original formula.
  • And then we are left with the term INT(13*(M+1)/5. That counts the days in the the preceding months. We are not interested in the exact number of days, we may lose multiples of 7 days, but it has to come out modulo 7. So this term replaces the chain of 11 IF-statements in the first program or the lookup table H in the second program.

    Each month has either 30 days of 31 days. A 30-day month contributes 2 to the day count (4 weeks + 2 days), a 31-day month contributes 3 to the day count. I know, February has 28 (or 29 days), but as it is the last month of the year we compute with, it will never need to be counted in the preceding months. In our example we effectively multiply the month number by 2.6 and when rounded down to integers, this will increment in steps of 2 or 3, exactly in the pattern we need for our purpose. That was Zeller's stroke of genius. Let's honour him for it! In order to see it, you have to make a table. The first month number we use is 3 (for March) and the last number we use is 14 (for February), For March, we compute INT(13*(3+1)/5) = INT(52/5) = INT(10.4) = 10. This is our starting point for the year. For April we compute INT(13(4+1))/5) = INT(65/5) = 13. The difference between 13 and 10 is 3, so the preceding month March has added 3 days to our starting point if we have a date in April (and March is indeed a 31-day month). The "Incr" column shows how many days the value has incremented with respect to the previous month and the "Days PM" column shows the number of days in the previous month.

    Month	M	13*(M+1)	13*(M+1)/5	INT(13*(M+1)/5	Incr	days PM
    March	3	52	10.4	10	-	-
    April	4	65	13,0	13	3	31
    May	5	78	15.6	15	2	30
    June	6	91	18.2	18	3	31
    July	7	104	20.8	20	2	30
    August	8	117	23.4	23	3	31
    September	9	130	26.0	26	3	31
    October	10	143	28.6	28	2	30
    November	11	156	31.2	31	3	31
    December	12	169	33.8	33	2	30
    January	13	182	36.4	36	3	31
    February	14	195	39.0	39	3	31

Christian Zeller invented this method already in the nineteenth century, long before the age of computers. In his original formula he split he year Y into a century number J and a year within the century K. These numbers are smaller and easier to work with by humans. The Wikipedia article also lists a formula in which the year Y is used directly (and that's what I use). This has the additional advantage that the number cannot come out negative, as Zeller's original formula can and then it may be tricky to get the correct modulus. Also note that the multiplication and division is often mentioned as 26/10 instead of 13/5. For humans who use decimal arithmetic, a division by 10 is easier, for a binary computer it makes no difference. Many published computer implementations use the original formula and 26/10.

Portability

All three programs listed in this article run unmodified under Michael Haardt's bas and under Matrix Brandy. Any arrays are indexed starting at 1. Most BASIC interpreters will index arrays starting at 0, but they will run the programs anyway, the element at index 0 is just not used. The third program has multiple statements per line, so it will not run unmodified under BASIC versions with one statement per line, but it is easy to port. The programs are even portable to integer BASIC versions, you just have to omit the INT function, as in Integer BASIC the division operation rounds down anyway. Values are well within the range supported by 16-bit integers.

Other Calendar Applications

Zeller's congruence is a quick way to get the day of the week for any given date, but it is limited to just that. For many applications it is more useful to convert a given date to an integer that increases with each calendar day. For this purpose, there are formulas to convert a date to a Julian day and there is also an algorithm to convert a Julian day back to a calendar date.

In your calendar program you may need to do additional computations, for example checking that the entered date is valid (day number does not exceed the number of days in the month) and for that you need to check that the current year is a leap year. For that you probably will need a lookup table (but you could apply a Julian date formula to check that the first of the next month is higher than the given day). For printing a calendar you will also need to know the number of days in any month.

Julian day is the number of days passed since Jan 1, 4713BC 12:00 UTC. For the current date, this number is around 2.45 million. The number is a fractional number that can represent each time instant. For calendar applications you can treat it as an integer, but this will not fit into the 16-bit integer variables that many BASIC versions have. There is a formula to convert a given date (day, month, year) into a Julian date and there is an algorithm to convert this number back to a date. Take the Julian date modulo 7 and you will get the week day, Using these formulas you can compute the number of days between 2 dates or you can compute what date will be a given number of days from now.

I think the absolute minimum range for integers to perform calendar calculations using the Julian day is 24 bits (16 million) Numbers close to 10 million will occur in the given formulas with the current year. Single-precision floats (IEEE754) may just be sufficient, provided that arithmetic for integers below 16 million is implemented exactly. Some older BASIC versions that only support single precision numbers may not cut it.

The Julian day may come in handy when you want to convert dates between different calendars, for example the Gregorian calendar, the Jewish calendar and the Islamic calendar.