Ваша задача - создать самую медленную растущую функцию из не более 100 байтов.
Ваша программа будет принимать в качестве входных данных неотрицательное целое число и выводить неотрицательное целое число. Давайте назовем вашу программу P.
Он должен соответствовать этим двум критериям:
- Его исходный код должен быть меньше или равен 100 байтам.
- Для каждого K существует N, такое что для каждого n> = N, P (n)> K. Другими словами, lim (n-> ∞) P (n) = ∞ . (Это то, что значит «расти».)
Ваша «оценка» - это скорость роста основной функции вашей программы.
Более конкретно, программа P растет медленнее, чем Q, если существует N, такое что для всех n> = N, P (n) <= Q (n), и существует по меньшей мере одно n> = N, такое что P (n). ) <Q (n). Если ни одна из программ не лучше, чем другая, они связаны. (По сути, какая программа медленнее, основана на значении lim (n-> ∞) P (n) -Q (n).)
Самая медленная функция роста определяется как функция, которая растет медленнее, чем любая другая функция, согласно определению в предыдущем абзаце.
Это скорость роста , поэтому выигрывает самая медленная программа роста!
Заметки:
- Чтобы помочь в оценке, постарайтесь указать, какую функцию рассчитывает ваша программа в ответе.
- Также добавьте некоторые (теоретические) входные и выходные данные, чтобы помочь людям понять, насколько медленно вы можете идти.
источник
<
следом за буквой является начало HTML-тега. Предварительно просмотрите свои вопросы, прежде чем публиковать их, пожалуйста: PОтветы:
Haskell, 98 байт, оценка = f ε 0 -1 ( n )
Как это работает
Это вычисляет инверсию очень быстро растущей функции, связанной с игрой червя Беклемишева . Скорость его роста сравнима с f ε 0 , где f α - быстрорастущая иерархия, а ε 0 - первое эпсилонное число .
Для сравнения с другими ответами обратите внимание, что
источник
Брахилог , 100 байт
Попробуйте онлайн!
Вероятно, это далеко не так медленно, как некоторые другие причудливые ответы, но я не мог поверить, что никто не пробовал этот простой и красивый подход.
Просто мы вычисляем длину входного числа, затем длину этого результата, затем длину этого другого результата ... в 100 раз.
Это растет так же быстро, как log (log (log ... log (x)), со 100 журналами base-10.
Если вы введете свой номер в виде строки , он будет работать очень быстро на любом входе, который вы можете попробовать, но не ожидайте, что когда-либо увидите результат выше 1: D
источник
JavaScript (ES6), обратная функция Аккермана *, 97 байт
* если я все сделал правильно
Функция
A
- это функция Аккермана . Функцияa
должна быть обратной функцией Аккермана . Если я реализовал это правильно, Википедия говорит, что это не ударит,5
пока не будетm
равных2^2^2^2^16
. Я получаюStackOverflow
вокруг1000
.Использование:
Пояснения:
Функция Аккермана
Обратная функция Аккермана
источник
Чистое Зло: Eval
Оператор внутри eval создает строку длиной 7 * 10 10 10 10 10 10 8.57, которая состоит из не более чем дополнительных вызовов лямбда-функции, каждый из которых будет создавать строку одинаковой длины, до тех пор, пока в конечном итоге не
y
станет 0. Якобы это имеет ту же сложность, что и метод Эшью, описанный ниже, но вместо того, чтобы полагаться на логику управления «если и / или», он просто объединяет гигантские строки (и в результате получается больше стеков… вероятно?).Наибольшее
y
значение, которое я могу предоставить и вычислить без Python, выдающего ошибку, равно 2, что уже достаточно, чтобы уменьшить ввод max-float для возврата 1.Строка длины 7,625,597,484,987 слишком велик:
OverflowError: cannot fit 'long' into an index-sized integer
.Я должен остановиться.
Eschew
Math.log
: Переходя к (10-му) корню (проблемы), Score: функция эффективно неотличима от y = 1.Импорт математической библиотеки ограничивает количество байтов. Давайте покончим с этим и заменим
log(x)
функцию чем-то примерно эквивалентным:x**.1
и которая стоит примерно столько же символов, но не требует импорта. Обе функции имеют сублинейный вывод относительно ввода, но x 0,1 растет еще медленнее . Однако нас это не сильно волнует, мы заботимся только о том, чтобы у него была одинаковая базовая схема роста по отношению к большим числам при одновременном потреблении сопоставимого количества символов (например,x**.9
такое же количество символов, но растет быстрее, поэтому это некоторая ценность, которая будет демонстрировать точно такой же рост).Теперь, что делать с 16 символами. Как насчет ... расширения нашей лямбда-функции, чтобы иметь свойства последовательности Аккермана? Этот ответ для большого числа вдохновил это решение.
В этой
z**z
части я не могу запускать эту функцию в местах, близких к нормальным входам дляy
иz
, наибольшие значения, которые я могу использовать, равны 9 и 3, для которых я получаю значение 1,0, даже для наибольшего числа с плавающей запятой, поддерживаемого Python (примечание: пока 1,0 численно больше, чем 6.77538853089e-05, повышенные уровни рекурсии перемещают выход этой функции ближе к 1, оставаясь больше 1, тогда как предыдущая функция перемещала значения ближе к 0, оставаясь больше 0, таким образом, даже умеренная рекурсия для этой функции приводит к такому количеству операций, что число с плавающей запятой теряет все значащие биты).Переконфигурирование исходного лямбда-вызова для получения значений рекурсии 0 и 2 ...
Если сравнение выполняется для «смещения от 0» вместо «смещения от 1», эта функция возвращает значение
7.1e-9
, которое определенно меньше, чем6.7e-05
.Реальная базовая рекурсия программы (значение z) имеет глубину 10 10 10 10 1,97 уровня, и как только y исчерпывает себя, она сбрасывается с 10 10 10 10 10 1,97 (именно поэтому начальное значение 9 достаточно), поэтому я не буду Я даже не знаю, как правильно рассчитать общее количество рекурсий, которые произошли: я достиг конца своих математических знаний. Точно так же я не знаю, улучшило бы число рекурсий перемещение одного
**n
возведения в степень от начального входа к вторичномуz**z
(или наоборот).Пойдем еще медленнее с еще большей рекурсией
n//1
- экономит 2 байтаint(n)
import math
,math.
сохраняет 1 байтfrom math import*
a(...)
более 8 байтовm(m,...)
(y>0)*x
сохраняет байт за кадромy>0and x
9**9**99
увеличивается количество байт на 4 и увеличивает глубину рекурсии примерно ,2.8 * 10^x
гдеx
старая глубина (или глубина приближается к гуголплексу в размере: 10 10 94 ).9**9**9e9
увеличивает количество байтов на 5 и увеличивает глубину рекурсии на ... безумное количество. Глубина рекурсии теперь 10 10 10 9,93 , для справки, googolplex - 10 10 10 2 .m(m(...))
наa(a(a(...)))
затраты 7 байтНовое выходное значение (на глубине 9 рекурсий):
Глубина рекурсии взорвалась до такой степени, что этот результат буквально не имеет смысла, за исключением сравнения с более ранними результатами, использующими те же входные значения:
log
25 разLambda Inception, оценка: ???
Я слышал, что вы любите лямбды, так что ...
Я даже не могу запустить это, я переполняю стек даже с 99 уровнями рекурсии.
Старый метод (ниже) возвращает (пропуская преобразование в целое число):
Новый метод возвращает, используя только 9 слоев вторжения (а не полный гугол из них):
Я думаю, что это имеет ту же сложность, что и последовательность Акермана, только маленькая, а не большая.
Также благодаря ETHproductions для 3-байтовой экономии в пространствах, которые я не знал, можно было удалить.
Старый ответ:
Целочисленное усечение функции log (i + 1) повторялось
2025 раз (Python), используя лямбда-лямбды.Ответ PyRulez можно сжать, введя вторую лямбду и сложив ее:
99100 символов используется.В результате получается итерация
2025 по сравнению с исходной 12. Кроме того, он сохраняет 2 символа, используяint()
вместоfloor()
которых допускается дополнительныйx()
стек.Если пробелы после лямбды можно убрать (я не могу проверить в данный момент), тоВозможный!y()
можно добавить пятую.Если есть способ пропустить
from math
импорт, используя полностью определенное имя (напримерx=lambda i: math.log(i+1))
), это позволило бы сохранить еще больше символов и позволить другой стек,x()
но я не знаю, поддерживает ли Python такие вещи (я подозреваю, что нет). Выполнено!По сути, это та же самая хитрость, которая использовалась в блоге XCKD для больших чисел , однако накладные расходы при объявлении лямбды исключают третий стек:
Это наименьшая возможная рекурсия с 3 лямбдами, которая превышает вычисленную высоту стека в 2 лямбды (сокращение любой лямбды до двух вызовов снижает высоту стека до 18, по сравнению с версией с 2 лямбдами), но, к сожалению, требует 110 символов.
источник
int
конвертации и подумал, что у меня есть запасные части.import
и пробел послеy<0
. Я не знаю много Python, хотя, поэтому я не уверенy<0and x or m(m,m(m,log(x+1),y-1),y-1)
чтобы сохранить еще один байт (при условии,x
что никогда не будет0
когдаy<0
)log(x)
растет медленнее ЛЮБОЙ положительной силыx
(для больших значенийx
), и это нетрудно показать, используя правило Л'Опитала. Я почти уверен, что ваша текущая версия работает(...(((x**.1)**.1)**.1)** ...)
целую кучу раз. Но эти силы просто умножаются, так что это эффективноx**(.1** (whole bunch))
, что является (очень маленькой) положительной силойx
. Это означает, что он на самом деле растет быстрее, чем ЕДИНСТВЕННАЯ итерация функции log (хотя, конечно, вам придется смотреть на ОЧЕНЬ большие значенияx
прежде чем вы заметите ... но это то, что мы подразумеваем под "уходом в бесконечность") ).Haskell , 100 байт
Попробуйте онлайн!
Это решение не принимает инверсию быстро растущей функции, вместо этого оно принимает довольно медленно растущую функцию, в этом случае
length.show
, и применяет ее несколько раз.Сначала мы определим функцию
f
.f
Это ублюдочная версия нотации Кнута, которая растет немного быстрее (немного преуменьшает, но числа, с которыми мы имеем дело, настолько велики, что в общем плане вещей ...). Мы определяем базовый случай,f 0 a b
чтобы бытьa^b
илиa
в силуb
. Затем мы определяем общий случай, который будет(f$c-1)
применяться кb+2
экземплярамa
. Если бы мы определяли нотацию Кнута со стрелкой вверх, как конструкцию, мы применили бы ее кb
экземплярамa
, ноb+2
на самом деле она более гольфистская и имеет преимущество в том, что она быстрее растет.Затем мы определим оператор
#
.a#b
определяется дляlength.show
применения коb
a
времени. Каждое применениеlength.show
примерно равно log 10 , что не очень быстро растущая функция.Затем мы приступаем к определению нашей функции,
g
которая принимает целое число и применяет егоlength.show
к целому ряду раз. Чтобы быть конкретным, это относитсяlength.show
к входуf(f 9 9 9)9 9
. Прежде чем мы перейдем к тому, насколько это большое, давайте посмотримf 9 9 9
.f 9 9 9
это больше , чем9↑↑↑↑↑↑↑↑↑9
(девять стрелок), массивный край. Я считаю, что это где-то между9↑↑↑↑↑↑↑↑↑9
(девять стрел) и9↑↑↑↑↑↑↑↑↑↑9
(десять стрел). Теперь это невообразимо большое число, которое может храниться на любом существующем компьютере (в двоичной записи). Затем мы берем это и ставим это в качестве первого аргумента нашего,f
что означает, что наша ценность больше, чем9↑↑↑↑↑↑...↑↑↑↑↑↑9
сf 9 9 9
стрелки между ними. Я не собираюсь описывать это число, потому что оно настолько велико, что я не думаю, что смогу сделать это справедливо.Каждый
length.show
примерно равен взятию логарифмической базы 10 целого числа. Это означает, что большинство чисел вернет 1, когдаf
применяется к ним. Наименьшее число, возвращающее что-то, отличное от 1, равно10↑↑(f(f 9 9 9)9 9)
2. Возвращается на минутку. Столь же отвратительно, как и то число, которое мы определили ранее, наименьшее число, которое возвращает 2, во много раз превосходит 10. То 1, за которым следуют10↑(f(f 9 9 9)9 9)
нули.Для общего случая
n
наименьшего входного вывода любой заданный n должен быть(10↑(n-1))↑↑(f(f 9 9 9)9 9)
.Обратите внимание, что эта программа требует огромного количества времени и памяти даже для небольшого n (больше, чем во вселенной много раз), если вы хотите проверить это, я предлагаю заменить
f(f 9 9 9)9 9
на гораздо меньшее число, попробуйте 1 или 2, если хотите когда-нибудь получить какой-либо вывод, кроме 1.источник
APL, Apply
log(n + 1)
,e^9^9...^9
времена, когда длина цепи равнаe^9^9...^9
длине цепи минус 1 раз, и так далее.источник
e^n^n...^n
части, поэтому я превратил ее в константу, но это может быть правдойMATL , 42 байта
Попробуйте онлайн!
Эта программа основана на серии гармоник с использованием постоянной Эйлера-Маскерони. Когда я читал документацию @LuisMendo на его языке MATL (заглавными буквами, так что это выглядит важно), я заметил эту константу. Выражение функции медленного роста выглядит следующим образом:
где εk ~ 1 / 2k
Я протестировал до 10000 итераций (в Matlab, поскольку он слишком велик для TIO), и его оценки ниже 10, поэтому он очень медленный.
Пояснения:
Эмпирическое доказательство: (ln k ) + 1 красным цветом всегда выше ln k + γ + εk синим цветом.
Программа для (ln k ) + 1 была сделана в
Matlab,
471814 байтовИнтересно отметить, что истекшее время для n = 100 составляет 0.208693 с на моем ноутбуке, но только 0.121945 с
d=rand(1,n);A=d*0;
и даже меньше, 0.112147 сA=zeros(1,n)
. Если нули - пустая трата пространства, это экономит скорость! Но я отклоняюсь от темы (вероятно, очень медленно).Редактировать: спасибо Стьюи за
помощь всокращении выражения Matlab до простого:источник
n=input('');A=log(1:n)+1
или как безымянная анонимную функция (14 байт):@(n)log(1:n)+1
. Я не уверен насчет MATLAB, ноA=log(1:input(''))+1
n=input('');A=log(1:n)+1
работает,@(n)log(1:n)+1
не работает (действительно допустимая функция с дескриптором в Matlab, но ввод не запрашивается),A=log(1:input(''))+1
работает и может быть сокращенаlog(1:input(''))+1
f=
не нужно рассчитывать, так как можно просто:@(n)log(1:n)+1
затемans(10)
получить первые 10 чисел.Python 3 , 100 байт
Этаж журнала функций (i + 1) повторяется 99999999999999999999999999999999999 раз.
Можно использовать показатели, чтобы сделать указанное число еще больше ...
Попробуйте онлайн!
источник
9**9**9**...**9**9e9
?Этаж функции log (i + 1) повторяется 14 раз (Python)
Я не ожидаю, что это будет очень хорошо, но я подумал, что это хорошее начало.
Примеры:
источник
int
вместоfloor
, вы можете вписаться в другойx(
e^e^e^e...^n
? Кроме того, почему после:
?x()
вызов?Ruby, 100 байт, оценка -1 = f ω ω + 1 (n 2 )
В основном заимствовано из моего самого большого номера для печати , вот моя программа:
Попробуйте онлайн
В основном вычисляет инверсию f ω ω + 1 (n 2 ) в быстро растущей иерархии. Первые несколько значений
А потом он продолжает выводить
2
очень долго. Дажеx[G] = 2
, где номерG
Грэма.источник
Mathematica, 99 байтов
(при условии, что ± занимает 1 байт)
Первые 3 команды определяют
x±y
для оценкиAckermann(y, x)
.Результатом функции является количество раз, которое
f(#)=#±#±#±#±#±#±#±#
необходимо применить к 1, прежде чем значение достигнет значения параметра. Посколькуf(#)=#±#±#±#±#±#±#±#
(то естьf(#)=Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[#, #], #], #], #], #], #], #]
) растет очень быстро, функция растет очень медленно.источник
Clojure, 91 байт
Вид вычисляет тот
sum 1/(n * log(n) * log(log(n)) * ...)
, который я нашел отсюда . Но функция закончилась длиной 101 байт, поэтому мне пришлось отбросить явное количество итераций, и вместо этого выполнять итерацию, пока число больше единицы. Пример выходов для входов10^i
:Я предполагаю, что этот модифицированный ряд все еще расходится, но теперь знаю, как это доказать.
источник
Javascript (ES6), 94 байта
Пояснение :
Id
относится кx => x
следующему.Давайте сначала посмотрим на:
p(Math.log)
примерно равноlog*(x)
.p(p(Math.log))
примерно равноlog**(x)
(количество раз, которое вы можете взять,log*
пока значение не будет больше 1).p(p(p(Math.log)))
примерно равноlog***(x)
.Обратная функция Аккермана
alpha(x)
приблизительно равна минимальному количеству раз, которое вам нужно сочинять,p
пока значение не станет максимум 1.Если мы тогда используем:
тогда мы можем написать
alpha = p(Id)(Math.log)
.Это довольно скучно, поэтому давайте увеличим количество уровней:
Это похоже на то, как мы строили
alpha(x)
, за исключением тогоlog**...**(x)
, что мы делаем сейчасalpha**...**(x)
.Зачем здесь останавливаться?
Если предыдущая функция есть
f(x)~alpha**...**(x)
, то эта сейчас~ f**...**(x)
. Мы делаем еще один уровень, чтобы получить наше окончательное решение.источник
p(p(x => x - 2))
msgstr " примерно равноlog**(x)
(сколько раз вы можете взять,log*
пока значение не станет больше 1)". Я не понимаю это утверждение. Мне кажется, что этоp(x => x - 2)
должно быть «количество раз, которое вы можете вычесть,2
пока значение не станет максимум 1». То есть p (x => x - 2) `должна быть функцией« деления на 2 ». Следовательно,p(p(x => x - 2))
должно быть «количество раз, которое вы можете разделить на 2, пока значение не станет максимум 1» ... то есть это должна бытьlog
функция, а неlog*
илиlog**
. Возможно, это можно уточнить?p = f => x => x < 2 ? 0 : 1 + p(p(f))(f(x))
, там, гдеp
передается,p(f)
как в других строках, нетf
.