Software Engineering Stories

1999-06-12

Gauss's Algorithm

Tom Van Vleck

In 1972, I wrote calendar, a Multics PL/I program that created wall calendars. Input files for the program specified text to put in the boxes. Dates could be specified relative to others, so one could indicate "last sunday in October" and so on, for holidays whose date varied. I included a command that would put text in the box for Easter, using a simple 7-step algorithm for calculating the date of Easter, attributed to Gauss, which I found in an issue of the Wang Programmer magazine in the comp center library. I copied it down, used it in my program, and tested a few years to make sure it worked. The program worked fine for years, and then I got a trouble report in September 1980, that the "easter" command was off by a week for Easter 1981. Sure enough, it was wrong.

Jim Densmore was a user at AFDSC at that time, who encountered and reported this bug. I don't know if his was the report that led us to investigate the problem.

Dennis Capps kindly researched the fix, and included a page-long comment in the revised program, quoting an article from the New Scientist that said that Gauss's algorithm was fine but failed occasionally: the first date it failed on since I wrote calendar was 1981.

Others may get by for 180 years with trying a few test cases.
If you try it, you'll get caught.

Gauss

Even if a famous mathematician tells you something, you still have to test your program.

This bug shows that Zero Defects is always an asymptotic goal. No reasonable amount of additional effort would have prevented this bug. No reasonable amount of additional testing would have found the bug before release. When I got the report, at first I felt betrayed. I did research the problem. I did test the code. It wasn't enough. The lesson I learned is that no matter how hard you work to prevent bugs, you can't get them all. And therefore, there will always be a need for maintenance.

updated 11/11/94
updated 06/12/99

(Multicians who miss the function of calendar may wish to consult my JavaScript/HTML implementation .. it lacks the "easter" command though.)