Вычисление больших значений функции Аккермана

Question

У меня есть код:

int CalculateAckermann(int x, int y)
{
    if(!x)
    {
        return y++;
    }
    if(!y)
    {
        return CalculateAckermann(x--,1);
    }
    else
    {
        return CalculateAckermann(x--, CalculateAckermann(x, y--));
    }
}

Предназначен для расчета функции Аккермана. Выше довольно малого числа x и y приложение вызывает переполнение стека, потому что оно повторяется слишком глубоко и приводит к довольно большим числам. Как бы я начал медленно вычислять решение?

Answer 1

В качестве примечания, если вы хотите просто использовать закрытую форму, то алгоритмы для m <4 просты. Если вы хотите перейти к тетратации, то я предлагаю вам написать алгоритм fastpower, возможно, с использованием бинарного метода, а затем с помощью этого метода вы можете написать функцию тетратации. Который будет выглядеть примерно так: </p>

int Tetration(int number, int tetrate)
{
    long int product=1;
    if(tetrate==0)
        return product;
    product=number;
    while(tetrate>1)
    {
        product=FastPower(number,product);
        tetrate--;
    }
    return product;
}

Тогда вы можете охватить случаи до n == 4, и после этого использовать рекурсивное определение и значения переполнения A (5, n) со смешной скоростью, так что это действительно не имеет значения. Хотя ваш учитель, вероятно, не будет удовлетворен таким алгоритмом, но он будет работать намного быстрее. В одном из моих отдельных классов, когда я попросил написать алгоритм для вычисления чисел Фибоначчи, а затем найти его O (n), я написал закрытую форму, а затем написал O (1) и получил полный кредит, некоторые профессора ценят умные ответы.

Что важно отметить в отношении функции Аккермана, так это то, что она по существу определяет иерархию аддитивных функций на целых числах, A (1, n) - сложение, A (2, n) - умножение, A (3, n) - Возведение в степень, A (4, n) является тетрацией, и после 5 функции растут слишком быстро, чтобы быть применимыми к очень многим.

Другой способ взглянуть на сложение, умножение и т. Д .:

Φ0 (x, y ) = y + 1
Φ1 (x, y ) = +(x, y )
Φ2 (x, y ) = ×(x, y )
Φ3 (x, y ) = ↑ (x, y )
Φ4 (x, y ) = ↑↑ (x, y )
           = Φ4 (x, 0) = 1 if y = 0
           = Φ4 (x, y + 1) = Φ3 (x, Φ4 (x, y )) for y > 0

(Используется префиксная нотация, т. Е. + (X, y) = x + y, (x, y) = x y.

Answer 2

IIRC, одно интересное свойство функции Аккермана состоит в том, что максимальная глубина стека, необходимая для его оценки (в уровнях вызовов), совпадает с ответом на функцию. Это означает, что будут существенные ограничения на фактические вычисления, которые могут быть сделаны, наложенные ограничениями виртуальной памяти вашего оборудования. Недостаточно иметь арифметический пакет с высокой точностью; вам быстро нужно больше битов для хранения логарифмов логарифмов чисел, чем в субатомных частицах во вселенной.

Опять же, IIRC, вы можете вывести относительно простые замкнутые формулы для A (1, N), A (2, N) и A (3, N), в соответствии со следующим (я, кажется, помню, как 3 в ответе, но детали, вероятно, неверны):

• A (1, N) = 3 + N
• A (2, N) = 3 * N
• A (3, N) = 3 ^ N

Формула для A (4, N) включает в себя некоторое махание рукой и суммирование показателей N-глубины. Формула для A (5, N) включает в себя суммирование формул для A (4, N) ... она становится чертовски странной и дорогой очень быстро.

По мере усложнения формул вычисления становятся совершенно неуправляемыми.

---

Статья в Википедии о функции Ackermann включает раздел «Таблица значений». Моя память ржавая (но это было 20 лет назад, когда я в последний раз смотрел на это во всех деталях), и она дает закрытые формулы:

• A (0, N) = N + 1
• A (1, N) = 2 + (N + 3) - 3
• A (2, N) = 2 * (N + 3) - 3
• A (3, N) = 2 ^ (N + 3) - 3

И A (4, N) = 2 ^ 2 ^ 2 ^ ... - 3 (где это 2 возводится в степень 2, N + 3 раза).

Answer 3

(Похоже на домашнее задание, но я все равно отвечу на него ...)

Прочтите еще немного о функции Аккермана. Например, в статье WikiPedia написано

«Его значение быстро растет, даже для небольших входных данных. Например, A (4,2) представляет собой целое число из 19 729 десятичных цифр».

Я подозреваю, что ваши 32-битные (или 64-битные, в зависимости от вашей архитектуры) переполнены, и вы попадаете в бесконечные циклы из-за этих проблем. Простая отладка в стиле printf покажет целочисленные переполнения. Если вы хотите на самом деле вычислить функцию Аккермана, вам нужно использовать библиотеку bignum с бесконечной точностью, например GNU MP .

Кроме того, прочитайте Tail Recursion и узнайте, как его оптимизировать.

Answer 4

Вам нужно предварительно уменьшить, а не после уменьшить, или вы просто передаете одинаковые значения x и y в функцию в каждой точке. Возможно, вы захотите также встроить некоторые средства безопасности, чтобы убедиться, что у вас нет отрицательных параметров, поскольку функция Аккермана не определена, если x или y отрицательны.

int CalculateAckermann(int x, int y)
{
    if (x < 0 || y < 0)
    {
        abort();
    }

    if(x == 0)
    {
        return y+1;
    }
    if(y == 0)
    {
        return CalculateAckermann( x-1,1);
    }
    else
    {
        return CalculateAckermann(x-1, CalculateAckermann(x, y-1));
    }
}