Можно ли оптимизировать стандартный Ackermann?

Question

Стандартная формула Ackermann, как написано в Java:

public static int ack(int x, int y) { 

     if (x == 0) { 
      return y + 1; 
     } else if (y == 0) { 
      return ack(x-1, 1); 
     } else { 
      // perforce (x > 0) && (y > 0) 
      return ack(x-1, ack(x,y-1)); 
     } 
    } 

Я задавался вопросом - есть ли более быстрый вариант осуществить это? Я думаю, может быть, с помощью аккумулятора или цикла.

Answer 1

Да, например, "обман". Если m равен 5 или выше, ни один из результатов не может быть представлен int. Для m = 4 могут быть представлены только n < 2. Для m < 4 существуют простые закрытые формулы на основе n.

Все остальное будет переполняться в любом случае, поэтому давайте притворяться, что эти случаи даже не происходят (или вы можете выбросить ошибку или что-то еще).

Не тестировалось:

int Ackerman(int m, int n) { 
    switch (m) { 
    case 0: 
     return n + 1; 
    case 1: 
     return n + 2; 
    case 2: 
     return n * 2 + 3; 
    case 3: 
     return (int)((1L << (n + 3)) - 3); 
    case 4: 
     return n == 0 ? 13 : 65533; 
    } 
} 

Answer 2

Я могу сказать вам одну вещь ... int не будет достаточно для очень многих значений х и у

Если вы собираетесь вызвать функцию повторно, вы можете создать int[][] массив для хранения различных так что вы можете посмотреть их на второй + время и только один раз вычислить его. Но что касается ускорения одного выполнения ... не уверен.

Answer 3

Это изменение происходит быстрее:

public static int ack(int x, int y) { 
    while (x != 0) { 
     y = y == 0 ? 1 : ack(x, y - 1); 
     x--; 
    } 
    return y + 1; 
}