Back when I was first learning Lisp by reading Paul Graham's Ansi Common Lisp, Graham mentioned that sometimes you can do useful work with a `DO`

loop having an empty body. I thought that was pretty neat but I've never come across a case where it was the natural solution. That is until now. As part of a small project I'm working on, I needed to evaluate a polynomial. The efficient way to do that is to use Horner's rule.

If you're a mathematician, you can think of Horner's rule as being a consequence of synthetic division or, if you're a programmer, as an application of strength reduction. Taking the programmer's point of view, we have

a_{0} + a_{1}x + … + a_{n-1}x^{n-1} + a_{n}x^{n} = a_{0} + x(a_{1} + x(a_{2} + … + x(a_{n-1} + a_{n}x)….)

Here's Horner's rule in Common Lisp:

(defun horner (a x) "Evaluate the polynomial with coefficients in the array a at x." (if (= (length a) 1) (aref a 0) (do* ((k (1- (length a)) (1- k)) (val (* (aref a k) x) (* (+ val (aref a k)) x))) ((<= k 1) (+ val (aref a 0))))))

Notice that the body of the `DO`

is empty. That's a pretty nice example; the implementation is natural and just what you'd write even if you'd never heard of the technique.

After I wrote that, I thought that you could do the same thing with a `for`

loop in C. It turns out, though, that the semantics are just different enough that it doesn't work—or at least I couldn't make it work. The best I could do is

double horner ( double x, double *a, int deg ) { double val; int k; val = a[ deg ] * x; for ( k = deg - 1; k > 0; k-- ) val = ( val + a[ k ] ) * x; return val + a[ 0 ]; }

You can see that they do the same thing in the same way but Lisp is wonderfully concise. Or, I suppose, horribly obscure depending on your point of view.

**Update**: Fixed formatting in polynomial strength reduction.