2
\$\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
  • 4
    \$\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\$ Commented Oct 10, 2015 at 19:33

2 Answers 2

12
\$\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)));
}
\$\endgroup\$
1
0
\$\begingroup\$

This guy Jon Hanna in the linked Stackeroverflow question uses a non-recursive but iterative strategy with some extra Ackermann specific optimizations. It is in c# but I hope it gives you some interesting insights.

https://stackoverflow.com/questions/12186672/how-can-i-prevent-my-ackerman-function-from-overflowing-the-stack/

He gets an answer for Ackerman(4,2) in a little over a second which I find impressive. My implementation will take a couple of lifecycles of the universe to complete.

\$\endgroup\$
2
  • \$\begingroup\$ This doesn't seem to be a review of the code in the question. \$\endgroup\$ Commented Sep 12, 2023 at 16:01
  • \$\begingroup\$ True. However it does provide some pointers in answering the question in the question: "How could I make it more efficient?" Since I am new to this platform I am open to removing my answer if it is not in line with expectations and habits. \$\endgroup\$ Commented Sep 14, 2023 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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