Wed, 07 Jun 2006

Doing Your Own Math

When I was going to Catonsville Community College (now the Catonsville Campus of The Community College of Baltimore County), I took a couple of computer science courses. The first of those was essentially an introduction-to-programming course, with the textbook using C. The professor, however, said that he would accept programs in any language that was cleared with him beforehand. Since I already knew C, I used the class as an opportunity to learn Common Lisp.

One of the problems from the course that I still remember fondly was the "do your own math" one. We were allowed to have a function that used the language's built-in addition operator to add one to a supplied value, and the same for the subtraction operator. Building on those two functions (i.e. not using any of the language's other math operators or functions), we had to write functions to implement addition, subtraction, multiplication, division, modulus, exponentiation, greatest common divisor, and least common multiple. To simplify things, we only had to make the functions work in the domain of positive integers (so the division would be integer divisions). Because I felt like setting myself a little more of a challenge, I added a couple of my own constraints. I decided that I would make my functions work for all integers, both positive and negative, and that I would match the interfaces for the Common Lisp functions I was replacing (at least as far as integers were concerned).

I found the problem to be quite interesting because it involves breaking down common mathematical operations into their basic forms. It's also rather neat to build up a hierarchy of common routines where you've constructed each layer yourself and you end up with a tower where you've built each layer, aside from some small contributions for the foundation.

I was bored recently and decided to redo the problem, now that I've got more Common Lisp experience under my belt. In particular, I realized that I could make a new package and shadow the functions that I was replacing, so all of my code would look normal, even though I was using my own functions. I also thought it would be interesting to compare my Common Lisp programming from nearly a decade ago with my Common Lisp programming now. Here's my original code and my new code.

Probably my biggest surprise was that my original version of least common multiple gave wrong answers when supplied with multiple arguments. I clearly hadn't tested it enough in school. What's interesting is that I originally tried the same approach with my recent code, but had to fix it when I saw that it wasn't right. My recent code is also more efficient; division is orders of magnitude faster, especially for small divisors, and my old code triggers a stack overflow when asked to multiply large numbers. Structurally speaking, the newer stuff tends to be more compact; helper functions are declared with labels rather than at the toplevel, and I make better use of some Common Lisp functions, most notably reduce.

So now I've gotten even more out of the interesting problem. In addition to the fun of solving it at all, I also get a comparison of changes in my programming style over time. Perhaps I'll address it again in another decade or so.

Phil! Gold