Ackermann Termination: анализ первопричин

Question

Вероятно, не нужно много объяснений того, что это такое, и это даже работает именно так, как я хочу. Моя настоящая проблема - завершение программы. Я вывел трассированные мои возвращаемые значения и вложенные циклы for, которые я использую в своей основной функции для пошагового перемещения значений. Я не вижу причин для того, чтобы это произошло, но программе требуется около 10 дополнительных минут после последнего прохождения через мои циклы, чтобы фактически завершиться. Хотя индексы моего цикла увеличиваются (из-за предварительной проверки), моя функция Аккерманна, очевидно, не выполняет дополнительную итерацию (не то, чтобы я все равно этого хотел). С другой стороны, единственное логическое объяснение состоит в том, что цикл не прерывается, но если бы это было так, моя функция Акерманна должна вернуть новое значение b. Поэтому единственная другая причина, о которой я могу подумать, это то, что сборка мусора занимает слишком много времени, чтобы очистить мои структуры данных и очистить кучу памяти. Для тех, кто не знаком, идея состоит в том, чтобы реализовать то, что традиционно представляется как чрезвычайно громоздкая рекурсивная функция, как итеративную функцию. Рекурсивный:

Даны натуральные числа m и n: если m = 0, вернуть n + 1; Иначе, если n = 0, вернуть Аккерманна (m - 1, 1); Еще вернем Аккермана (m - 1, Аккермана (m, n - 1)). Итеративно, идея состоит в том, чтобы использовать стек для эмуляции рекурсивных вызовов функций, чтобы вы могли использовать память из кучи и не зависеть от размера стека вызовов, что ограничивает время выполнения. Боюсь, что я пропускаю что-то в своем потоке, что вызывает эти длительные задержки между окончанием вычислений и моментом, когда моя программа достигает точки, когда пользователь делает чистый выход.

Вот мой код:

 static void Main(string[] args)
    {
        ulong i, j;
        i = j = 0;
        for (i = 1; i <= 3; i++)
            for (j = 1; j <= 15; j++)
                Console.WriteLine("[{0}] Ackermann({1},{2}) = {3}", DateTime.Now, i, j, Ackermann(i, j));
        Console.WriteLine("Press any key to continue...");
        Console.ReadKey();
    }

    static ulong Ackermann(ulong a, ulong b)
    {
        Stack<ulong> ackStack = new Stack<ulong>();

        ackStack.Push(a);
        while (ackStack.Count > 0)
        {
            a = ackStack.Pop();
            if (a == 0)
                b++;
            else if (b == 0)
            {
                ackStack.Push(--a);
                b = 1;
            }
            else
            {
                ackStack.Push(--a);
                ackStack.Push(++a);
                b--;
            }
        }
        return b;
    }

Мысли? Заметьте, что это C#, но такое поведение также встречается в C++, скомпилированном с MinGW.

Answer 1

Большое спасибо Питеру Витвоэту! Оказывается, что порядок оценки в моем Writeline был всем, что было неправильно. Только после изменения стало ясно, сколько времени это добавляет к общему времени выполнения всего этого!