Scheme For Enlightenment Part Nineteen - Ackermann Cached

So, (a 3 13) fails on some machines. (a 3 14) fails on others. I got to thinking. This function is supposed to eventually return. And it does this by calling itself with smaller numbers. And it seems to go over the same space with high frequency. So, if the function was written to remember answers that it previously computed, it could avoid lots of redundant calls. It might be faster. It's a classic trade of memory for time. How much memory, and how much time?

#include <stdio.h>
#include <stdlib.h>

#define A 5
#define B 10000000 /* m gets really big fast */
int acks[A][B]; /* (A * B * sizeof(int) bytes.), eg 200 MB. */

void init_acks()
{
    register int i;
    register int j;

    for (i = 0; i < A; i++) {
 for (j = 0; j < B; j++) {
     acks[i][j] = -1;
 }
    }
}

void setacks(int n, int m, int v)
{
    if (v < 0) {
 return;  /* Don't store bad data. */
    }
    if (n >= 0 && m >= 0 && n < A && m < B) {
 acks[n][m] = v;
    }
}

int chkacks(int n, int m)
{
    if (n >= 0 && m >= 0 && n < A && m < B) {
 return acks[n][m];
    } else {
 return -1;
    }
}

int ack(int n, int m)
{
    register int x;
    register int y;

    if (n == 0) {
 return m + 1;
    }
    x = chkacks(n, m);
    if (x >= 0) {
 return x;
    }
    if (m == 0) {
 x = ack(n - 1, 1);
 setacks(n - 1, 1, x);
 return x;
    } else {
 x = ack(n, m - 1);
 setacks(n, m - 1, x);
 y = ack(n - 1, x);
 setacks(n - 1, x, y);
 return y;
    }
}

int main(int argc, char *argv[])
{
    register int n;
    register int m;

    init_acks();
    if (argc == 3) {
        n = atoi(argv[1]);
        m = atoi(argv[2]);
    } else {
        printf("Usage: ack n m\nwhere n and m are small integers.\n");
        exit(0);
    }
    printf("Answer = %d\n", ack(n, m));
    return 0;
}

You have to call init_acks() before using it. The Ackermann function is called ack(). And this function is good for (a 3 16), assuming you have 200 MB of RAM for the array. It returns the answer very quickly. However, (a 3 17) doesn't work. It gets a stack crash. That's because the cache isn't large enough, and this code reverts to deep recursion. This one can also compute (a 4 1), but not (a 4 2). Worse, 1.5 GB of RAM (which happens to be handy) doesn't get you to (a 3 17). What on Earth is going on?

The Little Schemer chapter nine is available on line. It's postscript, but i was able to read it online. It's an interesting read. And they mention this function. They don't really explain it. I like things spelled out for me. According to the Wikipedia article, Mathemeticians spent a very long time on this. I'm a limited mortal. I don't have time like that. The joke is that the Ackermann function's compute time goes up as 2 ^ 2 ... ^2, where the number of raisings to powers is related to the input values. The result also goes up pretty fast. So (a 3 17) might not fit in a 32 bit integer. And no 32 bit machine will have stack space or cache space to cope anyway.

Why bring this up? Well, at first glance, it looks alot like the change counting function. It's worthwhile to see how they're different, to get an idea of the run time of functions. This brick wall function is not computable for even moderate input values in practice.