# Ackermann Function of (4,2)

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

}

• 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. Commented Oct 10, 2015 at 19:33

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

• This question made me wonder if memoization might help out at all, and apparently the answer is no: stackoverflow.com/a/13088510/2388145 Commented Oct 11, 2015 at 1:10

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.

• This doesn't seem to be a review of the code in the question. Commented Sep 12, 2023 at 16:01
• 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. Commented Sep 14, 2023 at 12:57