In October 1984, the SEMCO DATA BUS issued a programming challenge. It invited readers to write a computer program to solve a puzzle that was something like:
People were just starting to own personal computers at that time. The program was to be written in Basic, since virtually all PCs had that language as part of their operating system.
In those days, computers were slow (and computer time was expensive on mainframe computers). It was common practice to spend a great deal of time studying the problem so as to not waste the computer's time. Programs were to be efficient.
When I studied the puzzle, it was obvious that the problem could be stated as needing to simultaneously solve two equations in three unknowns. It was easy enough to use high school algebra to reduce the two equations to one equation with two unknowns—something of the form aX + bY = c. Unfortunately, such an equation has an infinite number of solutions. I assumed that other puzzle solvers would use a brute-force iterative solution to solve the problem.
I remembered though that I had had this particular equation in a number theory course in college—namely to solve one equation in two unknowns for integer solutions. A third century Greek mathematician, Diophantos, had developed a general method of solving this particular problem (called a Diophantine Equation).
Unfortunately, a Diophantine Equation can be solved if and only if the greatest common divisor (g.c.d.) of A and B divides C evenly. The method most often used to find the g.c.d. was developed by Euclid, and is called the Euclidean Algorithm.
So I set about programming the Euclidean Algorithm in Basic. It is an iterative solution, but it converges extremely fast—usually in fewer than five iterations. Now I could use the g.c.d. to divide A, B, and C.
Next I programmed the Diophantine Equation solution. It is complicated by the fact that it uses modular arithmetic (not often taught), and it is also an iterative solution. It also converges extremely fast—usually in fewer than five iterations.
Now I had one solution with almost no computer time required to obtain it. Once you have one solution, then there is an easy formula for obtaining other solutions. It only takes one iteration per solution. I was only interested in positive integer solutions, so I was able algebraically to set upper and lower bounds for my iteratons to constrain the program to positive solutions.
I ran the completed program on my relatively slow 2 MHz 8080 IMSAI PC, and it gave all non-negative solutions in about one second. I thought then, and I still think now, that the program was the finest computer program that I had/have ever written. Very elegant indeed.
I knew that anyone who tried to follow my program would be completely baffled. They would see that it worked, but they would have no clue as to why. So I included a letter to the editor that explained my whole technique in detail. I included numerical examples for how to execute the Euclidean Algorithm, and how to solve a Diophantine Equation.
I was sure that I would be announced the winner of the programming contest, but the editor chose no winner. Instead he published my letter, and my program, and the programs of the other eight entrants. Oh well!
Recently, as part of the 35th anniversary of SEMCO, I was thinking back over my years and experiences with SEMCO, and I started thinking about this computer program. I started wondering as to how I would solve the problem today if I didn't know about Diophantine Equations. It occurred to me that I could write a very simple little brute-force program where I did a FOR-loop for the pennies, allowing them to go from 0 to 128, and then nest inside that a second FOR-loop for nickels, allowing them to go from 0 to 128, and calculate the number of dimes by subtracting the number of pennies and nickels from 128. I could then calculate the value and see if it was $6.14 or not. I realized that the inner loop would be executed 129 * 129 = 16,641 times. As I thought about it, I realized that on a modern PC that would require essentially zero seconds to execute. I went to my PC and wrote the necessary 7-line program in about three minutes. It executed the first time, and generated all solutions virtually instantly. After a little more thinking, I was able to apply one small modification that cut the number of iterations in half—but that was of academic interest only.
If I had been asked to judge the programs in 1984, I would have said that the Diophantine Equation program was clearly the best. But if I was asked to judge the programs today, I would probably choose the 7-line program. I would ask myself such questions as:
I would no longer ask the question, “Which program is the most efficient in the use of CPU cycles?” I no longer care. I finally have enough speed, memory, and disk space on my personal PC to do anything that I want to do—virtually instantly.
Links: