Вопросы Теги

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

Цитируя первоначальное предложение :

T[N]

Начиная с N3485, unique_ptr не обеспечивает частичную специализацию для T[N]. Тем не менее, пользователи будут сильно склонны писать make_unique(). Это беспроигрышный сценарий. Возвращение unique_ptr выберет основной шаблон для отдельных объектов, что является странным. Возвращение unique_ptr было бы исключением из остального железного правила, которое make_unique() возвращает unique_ptr. Следовательно, это предложение делает T[N] плохо сформированным здесь, что позволяет реализациям создавать полезные static_assert сообщения.

Автор предложения, Стефан Т. Лававей, иллюстрирует эту ситуацию в этом видео на Core C ++ (любезно предоставлено chris ), начиная с минуты 1:01 : 10 (более или менее).

5
задан Elliot Hughes 6 June 2009 в 21:59
поделиться

4 ответа

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

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.

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.

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.

21
ответ дан 18 December 2019 в 05:27
поделиться

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

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

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

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

Также прочтите Tail Recursion и как его оптимизировать.

5
ответ дан 18 December 2019 в 05:27
поделиться

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) ... это становится чертовски странным и очень быстро дорогостоящим.

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

Статья в Википедии о функции Аккермана включает раздел «Таблица значений». Моя память ржавая (но 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 раза).

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

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

Статья в Википедии о функции Аккермана включает раздел «Таблица значений». Моя память ржавая (но 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 раза).

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

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

Статья в Википедии о функции Аккермана включает раздел «Таблица значений». Моя память ржавая (но 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 раза).

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

Статья в Википедии о функции Акермана включает раздел «Таблица значений». Моя память ржавая (но 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 раза).

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

Статья в Википедии о функции Акермана включает раздел «Таблица значений». Моя память ржавая (но 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 раза).

6
ответ дан 18 December 2019 в 05:27
поделиться

Вам нужно предварительно декрементировать, а не пост-декрементировать, или вы просто передаете в функцию одни и те же значения 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));
    }
}
4
ответ дан 18 December 2019 в 05:27
поделиться
Другие вопросы по тегам:

Похожие вопросы: