Ackermann function (Java)

From LiteratePrograms
Jump to: navigation, search
Other implementations: C | Haskell | Java | OCaml | Prolog | Python

The Ackermann function or Ackermann-Péter function is defined recursively for non-negative integers m and n as follows:

 A(m, n) =
 \begin{cases}
 n+1 & \mbox{if } m = 0 \\
 A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\
 A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0.
 \end{cases}

In the theory of computation, the Ackermann function is a simple example of a recursive function that is not primitively recursive. Note that this function grows very quickly -- even A(4, 3) cannot be feasibly computed on ordinary computers.


This article explains a few different methods of computing the Ackermann function in Java. We use Java's <a href="">BigInteger</a> class 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). BigInteger is found in java.math:

<<imports>>=
import java.math.BigInteger;

Contents

[edit] 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, and we test for zero efficiently using the signum() method, which returns zero if and only if the number is zero.

<<ackermann implementations>>=
static BigInteger naiveAckermann(BigInteger m, BigInteger n) {
    calls = calls.add(BigInteger.ONE);
    if (m.signum() == 0)
        return n.add(BigInteger.ONE);
    else if (n.signum() == 0)
        return naiveAckermann(m.subtract(BigInteger.ONE), BigInteger.ONE);
    else
        return naiveAckermann(m.subtract(BigInteger.ONE),
                              naiveAckermann(m, n.subtract(BigInteger.ONE)));
}

[edit] Partially interative

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>>=
static BigInteger iterativeAckermann(BigInteger m, BigInteger n) {
    calls = calls.add(BigInteger.ONE);
    while (m.signum() != 0) {
        if (n.signum() == 0) {
            n = BigInteger.ONE;
        } else {
            n = iterativeAckermann(m, n.subtract(BigInteger.ONE));
        }
        m = m.subtract(BigInteger.ONE);
    }
    return n.add(BigInteger.ONE);
}

[edit] 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) = 2n + 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>>=
static BigInteger formulaAckermann(BigInteger m, BigInteger n) {
    calls = calls.add(BigInteger.ONE);
    BigInteger TWO = BigInteger.valueOf(2);
    BigInteger THREE = BigInteger.valueOf(3);
    BigInteger FOUR = BigInteger.valueOf(4);
    while(m.compareTo(FOUR) >= 0) {
        if (n.signum() == 0) {
            n = BigInteger.ONE;
        } else {
            n = formulaAckermann(m, n.subtract(BigInteger.ONE));
        }
        m = m.subtract(BigInteger.ONE);
    }
    switch(m.intValue()) {
        case 0:  return n.add(BigInteger.ONE);
        case 1:  return n.add(TWO);
        case 2:  return n.shiftLeft(1).add(THREE);
        default: return BigInteger.ONE.shiftLeft(n.intValue() + 3).subtract(THREE);
    }
}

[edit] 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.java>>=
imports

public class Ackermann {

    private static BigInteger calls;

    ackermann implementations

    public static void main(String[] args) {
        BigInteger m, n, result;
        m = new BigInteger(args[0]);
        n = new BigInteger(args[1]);
    
        calls = BigInteger.ZERO;
        result = naiveAckermann(m, n);
        System.out.println("Naive:     " + result + " (" + calls + " calls)");
    
        calls = BigInteger.ZERO;
        result = iterativeAckermann(m, n);
        System.out.println("Iterative: " + result + " (" + calls + " calls)");
    
        calls = BigInteger.ZERO;
        result = formulaAckermann(m, n);
        System.out.println("Formula:   " + result + " (" + calls + " calls)");
    }

}

Here's some sample input/output (note: on a 2.4 GhZ machine this takes many minutes to run):

$ java Ackermann 4 1
Naive:     65533 (2862984010 calls)
Iterative: 65533 (1431459240 calls)
Formula:   65533 (2 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):

$ java Ackermann 4 2
Formula:   200352993040684646497907235156025[...]905719156733 (3 calls)
Download code
hijacker
hijacker
hijacker
hijacker