Ackermann Function of (4,2)

Question

How efficient is this program? How could I make it more efficient?

package main;

import java.math.BigInteger;

public class Ackermann {

    public static void main(String[] args) {
        System.out.println(ack(BigInteger.valueOf(4),BigInteger.valueOf(2)));

    }

    public static BigInteger ack(BigInteger a, BigInteger b) {
        BigInteger ans;
        if (a.equals(BigInteger.ZERO)) ans = b.add(BigInteger.ONE);
        else if (b.equals(BigInteger.ZERO)) ans = ack(a.subtract(BigInteger.ONE),BigInteger.valueOf(1));
        else ans = ack(a.subtract(BigInteger.ONE), ack(a,b.subtract(BigInteger.ONE)));
        return (ans);
    }

}

Answer 1

The Ackermann function is not designed to be efficient... ;-) It is designed to be a counter-proof to a theoretical construct.

But, the reality is that the BigInteger is required. The conditions are required.

About the only things I can suggest are:

• use better names
• return-early logic
• the ans variable is unnecessary
• always use braces for conditional blocks.
• BigInteger.ONE is already defined, you have used it in some places already, no need for BigInteger.valueOf(1)
• call it ackermann not ack

I would have:

public static BigInteger ackermann(BigInteger a, BigInteger b) {
    if (a.equals(BigInteger.ZERO)) {
        return b.add(BigInteger.ONE);
    }
    if (b.equals(BigInteger.ZERO)) {
        return ackermann(a.subtract(BigInteger.ONE),BigInteger.ONE);
    }
    return ackermann(a.subtract(BigInteger.ONE), ackermann(a, b.subtract(BigInteger.ONE)));
}