1

I am required to find an optimization for the Ackermann function and explain the problem with the Ackermann problem itself. However, I'm not really sure where I should start. I understand that Ackermann's function grows faster than any primitive recursive function. Maybe using a BigInteger to store the result could help? or maybe using memoization?

For example I was thinking of using something like a bottom-up fibonacci solution, if we know that at A(0,1) = 1+1, A(1,0) = A(0,1), A(1,1) = A(0,A(1,0)) and I can build from there depending on the 'n'.
Does that sound reasonable or is it unachievable? What is the actual problem that leads it to grow this fast even for small numbers?

class Ackermann
{
 
    static int ack(int m, int n)
    {
        if (m == 0)
        {
            return n + 1;
        }
        else if((m > 0) && (n == 0))
        {
            return ack(m - 1, 1);
        }
        else if((m > 0) && (n > 0))
        {
            return ack(m - 1, ack(m, n - 1));
        }else
        return n + 1;
    }

    public static void main(String args[])
    {
        System.out.println(ack(1, 2));
    }
}
April Crude
  • 117
  • 7
  • Only small m can give results small enough to not overflow an int, and you can just hard-code the computation for those values (see "Table of Values" on the wikipedia page about the function). Even if you use bignums, you can't get to Ackerman(5, 0) or Ackerman(4, 3). – Paul Hankin Jan 01 '22 at 07:09
  • See also [Theoretically can the Ackermann function be optimized?](https://stackoverflow.com/q/76559257/12597) – Ian Boyd Jul 04 '23 at 10:58

1 Answers1

1

From this post, you can find the following:

A real gain of execution time can only be achieved by not recalculating subresults over and over again. Memoization is an optimization technique where the results of function calls are cached and returned when the same inputs occur again. See for instance Ward (1993). Grossman & Zeitman (1988) published a cunning algorithm which computes A(i, n) within O(i x A(i,n)) time and within O(i) space.

OmG
  • 18,337
  • 10
  • 57
  • 90