Ackermann function (Python)

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 Python. We use Python's long type for arbitrary-precision integer arithmetic, which allows us to handle more of the very large integer values generated by the Ackermann function (although due to its rapid growth we are still quickly limited by available memory).

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 assume that the inputs are non-negative.

<<ackermann implementations>>=
def naive_ackermann(m, n):
    global calls
    calls += 1
    if m == 0:
        return n + 1
    elif 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>>=
def iterative_ackermann(m, n):
    global calls
    calls += 1
    while m != 0:
        if n == 0:
            n = 1
        else:
            n = iterative_ackermann(m, n - 1)
        m -= 1
    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>>=
def formula_ackermann(m, n):
    global calls
    calls += 1
    while m >= 4:
        if n == 0:
            n = 1
        else:
            n = formula_ackermann(m, n - 1)
        m -= 1
    if m == 3:
        return (1 << n + 3) - 3
    elif m == 2:
        return (n << 1) + 3
    elif m == 1:
        return n + 2
    else: # m == 0
        return n + 1

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.py>>=
import sys # for argv
calls = 0
ackermann implementations
if __name__ == "__main__":
    m = long(sys.argv[1])
    n = long(sys.argv[2])
    calls = 0
    result = naive_ackermann(m, n)
    print "Naive:     %d (%d calls)" % (result, calls)
    calls = 0
    result = iterative_ackermann(m, n)
    print "Iterative: %d (%d calls)" % (result, calls)
    calls = 0
    result = formula_ackermann(m, n)
    print "Formula:   %d (%d calls)" % (result, calls)

Here's some sample input/output:

$ python ackermann.py 3 6
Naive:     509 (172233 calls)
Iterative: 509 (85866 calls)
Formula:   509 (1 calls)

If we comment out all except Formula, we can compute some impressively large values of the Ackermann function quite quickly, such as A(4,2), which has over 19000 digits (omitted here for space):

$ python ackermann.py 4 2
Formula:   200352993040684646497907235156025[...]905719156733 (3 calls)