Пожалуйста, сначала прочитайте ответ JJ.Это свежо и привело к этому ответу, который фактически является его развитием.
TL; DR A(4,3) - это очень большое число, которое не может быть вычисленов этой вселенной.Но Ракудо попробует.При этом вы будете преодолевать разумные ограничения, связанные с распределением памяти и индексированием, если вы используете версию кэширования, и ограничения, связанные с числовыми вычислениями, если вы этого не сделаете.
Я пробую некоторые примеры изRosettacode и столкнуться с проблемой с предоставленный пример Ackermann
Цитирование описания задачи с некоторыми добавленным выделением :
Произвольная точность является предпочтительной (поскольку функция растет очень быстро )
Стандартный целочисленный тип P6 Int равен произвольная точность .Решение P6 использует их для вычисления наиболее продвинутого возможного ответа.Сбой происходит только тогда, когда вы пытаетесь сделать невозможное.
Когда он запускается "неизмененным" (я заменил имена переменных utf-8 на латино-1)
Замена имен переменных не является значительным изменением.
Но добавление строки A(4,3) сместило код с возможности вычислимости в реальность на не вычислимость в реальности.
Пример, который вы изменилиимеет только один пояснительный комментарий:
Вот кэширующая версия этого ... , чтобы сделать A (4,2) возможным
Обратите внимание, что решение A(4,2) имеет длину почти 20 000 цифр.
Если вы посмотрите на другие решения на этой странице, большинство из них даже не пытаются достичь A(4,2).Вот такие комментарии к версии Phix:
оптимизирован.до сих пор нет библиотеки bignum, так что ack (4,2), который является power (2,65536) -3, что, по-видимому, составляет 19729 цифр, и любые другие, выше (аппаратное обеспечение CPU / FPU) и этот [код].
Решение для A(4,2) является самым продвинутым из возможных.
A(4,3) на практике не вычисляется
Цитировать Academic Kids: функция Ackermann:
Даже для небольших входных данных (скажем, 4,3) значения функции Аккермана становятся настолько большими, что их невозможно реально вычислить, и фактически их десятичные разложения даже не могут быть сохраненыво всей физической вселенной.
Таким образом, вычисление A(4,3).say невозможно (в этой вселенной).
Это должно неизбежно привести к переполнению даже целочисленной арифметики произвольной точности.Вопрос только в том, когда и как.
Cannot unbox 65536 bit wide bigint into native integer
В первом сообщении об ошибке упоминается эта строка кода:
proto A(Int \m, Int \n) { (state @)[m][n] //= {*} }
* state @ является анонимная переменная массива состояний .
По умолчанию @ переменные используют конкретный тип по умолчанию для P6 абстрактный тип массива .Этот тип массива по умолчанию обеспечивает баланс между сложностью реализации и достойной производительностью.
При вычислении A(4,2) индексы (m и n) остаются достаточно малыми, чтобы вычисление завершалось без превышения предела индексации массива по умолчанию.
Этот предел является "собственным" целым числом (примечание: не a "натуральное" целое число ).«Собственное» целое число - это то, что P6 называет целыми числами фиксированной ширины, поддерживаемыми аппаратным обеспечением, на котором оно работает, обычно это long long , что, в свою очередь, обычно составляет 64 бита.
64-битный индексможет обрабатывать индексы до 9,223,372,036,854,775,807 .
Но при попытке вычислить A(4,3) алгоритм генерирует широкий целочисленный индекс размером 65536 бит (8192 байта).Такое целое число может быть таким большим, как 2 65536 , 20 032 десятичного числа .Но самый большой допустимый индекс - это 64-битное собственное целое число.Так что, если вы не закомментируете строку кэширования, которая использует массив, то для A(4,3) программа завершит работу, выдав исключение:
Невозможно распаковать bigint 65536 бит в собственное целое число
Ограничения для выделения и индексации типа массива по умолчанию
Как уже объяснялось, нет такого массива, который мог бы быть достаточно большим, чтобы помочь полностью вычислить A(4,3).Кроме того, 64-разрядное целое число - это уже довольно большой индекс (9,223,372,036,854,775,807).Тем не менее, P6 может вместить большие массивы, поэтому я кратко расскажу об этом ниже, потому что теоретические возможности могут представлять интерес для других проблем.
Но прежде чем обсуждать большие массивы , запустите приведенный ниже код на tio.run показывает практические ограничения для типа массива по умолчанию на этой платформе:
my @array;
@array[2**29]++; # works
@array[2**30]++; # could not allocate 8589967360 bytes
@array[2**60]++; # Unable to allocate ... 1152921504606846977 elements
@array[2**63]++; # Cannot unbox 64 bit wide bigint into native integer
(Закомментируйте строки ошибок, чтобы увидеть более поздние / большие ошибки.)
Ошибка «не удалось выделить 8589967360 байт» - это паника MoarVM.Это результат того, что tio.run отклонил запрос на выделение памяти.
Я думаю, что ошибка «Невозможно выделить ... элементы» - это исключение уровня P6, которое выдается в результате превышения некоторого внутреннего предела реализации Rakudo.
Последнее сообщение об ошибке показывает предел индексации для типа массива по умолчанию, даже если для программ были выделены огромные объемы памяти.
Что если кто-то захочет выполнить большую индексацию?
Можно создавать / использовать другие @ (does Positional) типы данных, которые поддерживают такие вещи, как разреженные массивы и т. Д.
И, используя этот механизм, возможно, что кто-то может написать реализацию массива, которая поддерживаетиндексирование целых чисел большего размера, чем поддерживается типом массива по умолчанию (предположительно, путем наложения логики поверх инструкций базовой платформы).
Если такая альтернатива была создана и называется BigArray, тогда строку кэша можно заменить на:
my @array is BigArray;
proto A(Int \?, Int \?) { @array[?][?] //= {*} }
Опять же, это все же не будет достаточноh для хранения промежуточных результатов для полного вычисления A(4,3), но я хотел показать использование пользовательских типов массивов.
Numeric overflow
Когда вы комментируете кэширование, вы получаете:
Числовое переполнение
P6 / Rakudo делает произвольную арифметику точности.Хотя это иногда называют бесконечной точностью, оно, очевидно, не является на самом деле бесконечным, а вместо этого является, ну, «произвольным», что в данном контексте также означает «вменяемый» для некоторого определения «вменяемый».
Это классически означает нехватку памяти для хранения числа.Но в случае с Ракудо я думаю, что есть попытка сохранить разумность, переключаясь с действительно огромного Int на Num (число с плавающей запятой) до полного исчерпания ОЗУ.Но затем вычисления A(4,3) в конечном итоге переполняют даже двойное число с плавающей запятой.
Таким образом, в то время как кэширование взорвется раньше, код все равно будет взорван позже, и тогда вы получите числовое переполнение, которое либо проявится, либокак ошибка нехватки памяти или ошибка числового переполнения, как в данном случае.