Ackermann function (C)

From LiteratePrograms

Other implementations: Alice ML | C | Erlang | Forth | Haskell | Java | OCaml | Prolog | Python

This article explains a few different methods of computing the Ackermann function in C. Of course, since most values of the Ackermann function exceed the size of a machine word (even a 64-bit word), these implementations are more useful for illustration than practical computation of Ackermann function values.

Contents 1 Directly from definition 2 Partially iterative 3 Precomputed for small m 4 Test main

Directly from definition

The most basic implementation is based directly on the definition above, resembling it nearly identically, except that the greater-than-zero conditions are implicit due to previous conditions being false. We use unsigned types to avoid the possibility of illegal negative inputs.

<<ackermann implementations>>=
unsigned int naive_ackermann(unsigned int m, unsigned int n) {
    calls++;
    if (m == 0)
        return n + 1;
    else if (n == 0)
        return naive_ackermann(m - 1, 1);
    else
        return naive_ackermann(m - 1, naive_ackermann(m, n - 1));
}

Partially iterative

For compilers that do not eliminate tail recursion, we can turn two of the recursive calls above into iterative constructs. This greatly reduces the number of recursive calls, although the number is still prohibitive even for small inputs.

<<ackermann implementations>>=
unsigned int iterative_ackermann(unsigned int m, unsigned int n) {
    calls++;
    while (m != 0) {
        if (n == 0) {
            n = 1;
        } else {
            n = iterative_ackermann(m, n - 1);
        }
        m--;
    }
    return n + 1;
}

Precomputed for small m

It is possible to prove the following useful formulas for small values of the input m:

A(0,n) = n + 1
A(1,n) = n + 2
A(2,n) = 2n + 3
A(3,n) = 2^{n + 3} − 3

Using these, we can drastically reduce runtime not only for these inputs, but for larger inputs which make recursive calls with these inputs. We perform the exponentiation using shifting:

<<ackermann implementations>>=
unsigned int formula_ackermann(unsigned int m, unsigned int n) {
    calls++;
    while(1) {
        switch(m) {
        case 0:  return n + 1;
        case 1:  return n + 2;
        case 2:  return (n << 1) + 3;
        case 3:  return (1 << (n+3)) - 3;
        default:
            if (n == 0) {
                n = 1;
            } else {
                n = formula_ackermann(m, n - 1);
            }
            m--;
            break;
        }
    }
}

This doesn't quite work correctly for n + 3 equal to the word size, for which 1 << (n+3) is undefined due to overflow, but we ignore this here.

Test main

We write a test driver that prints a requested value of the Ackermann function using all three implementations, as well as the number of calls made by each:

<<ackermann.c>>=
#include <stdio.h>
#include <stdlib.h> /* atoi() */
static unsigned int calls;
ackermann implementations
int main(int argc, char* argv[]) {
    unsigned int m, n, result;
    m = (unsigned)atoi(argv[1]);
    n = (unsigned)atoi(argv[2]);
    calls = 0;
    result = naive_ackermann(m, n);
    printf("Naive:     %u (%u calls)\n", result, calls);
    calls = 0;
    result = iterative_ackermann(m, n);
    printf("Iterative: %u (%u calls)\n", result, calls);
    calls = 0;
    result = formula_ackermann(m, n);
    printf("Formula:   %u (%u calls)\n", result, calls);
    return 0;
}

Here's some sample input/output:

$ ./ackermann 4 1
Naive:     65533 (2862984010 calls)
Iterative: 65533 (1431459240 calls)
Formula:   65533 (2 calls)