Scheme For Enlightenment Part Eighteen - Ackermann

The Ackermann function is often used as a benchmark. It beats the crap out of your recursion system. But even with that caveat, it isn't a very good benchmark. Mainly, it's tough to scale it for reasonable run time for various systems. You can't just feed it new arguments and extrapolate times, though it could be put into a simple loop. The function is pretty simple. It only uses addition and subtraction. It has surprising runtime. There are tons of implementations out there. Here's one.

(define (a n m)
    (if (eqv? n 0) (+ m 1)
  (if (eqv? m 0)
      (a (- n 1) 1)
      (a (- n 1) (a n (- m 1))))))

The function a takes two arguments, n and m. If n is zero, it returns m + 1. This is the base condition, and eventually calls will be made to this ground state. If n isn't zero, then if m is zero, it calls itself with n - 1 and 1. Finally, if both n and m are not zero, it returns a funny nested call. It calls itself with n - 1, but the second argument is the return value of another call to itself. This last bit is interesting, as the return value of the Ackermann function can be really big. So it isn't clear that this function will ever return. It does. Eventually. If your machine is big enough. And if your Universe has been around long enough.

If you explore this function, you find that it seems to hit a brick wall. The enormous difference in speed between LispMe on the Palm and C on the desktop (146,000x) amounts to essentially nothing. You run into this wall right around (a 3 13).

int ack(int n, int m)
{
    if (n == 0) {
        return ++m;
    }
    if (m == 0) {
        return ack(n - 1, 1);
    } else {
        return ack(n - 1, ack(n, m - 1));
    }
}

So if you feed this C script arguments like (a 1 1), (a 1 13), (a 2 1), (a 2 13), (a 3 1), and even (a 3 11), you get answers quickly (less than 20 seconds). The argument (a 3 12) takes more like a minute, and (a 3 13) takes 3 1/2 minutes. And yet (a 3 14) stubbornly refuses to run. What i get is a stack crash, but only after quite some time goes by.

The Wikipedia article explains what's going on. While you read that, i'll write tomorrow's installment.