1
\$\begingroup\$

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);
    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ As far as I remember, ack(4,2) is 2^65533-3. Since the only way that ack() can return a specific value is to recurse that deep, there is no way that a machine will ever execute that algorithm. \$\endgroup\$ – Andreas Krey Oct 10 '15 at 19:33
11
\$\begingroup\$

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)));
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.