Re: Про F - Gnu , 01.12.2004 11:59 MSK | ||
: Мы тогда были молодыми, горячими студентами, : и при виде задачи первая мысль была: : "Как её решить?", а не "Нафига это делать?". : Один из нас притащил эту функцию, и сказал, : что по слухам она какая-то необычная. : Разумеется, никто не поверил - что за функция, : которая всего-то и может прибавлять единичку : к аргументу? Ну, ещё сама себя вызывает, : да пусть хоть обвызывается, на одних единицах : сильно не вырастешь. Тут же, на листе бумаги : было подсчитано F(1,1), и, после некоторого : геморроя - F(2,2). Начали было считать F(3,3), : но быстро надоело и за дело взялся компьютер. : Он блестяще подтвердил наши ручные расчёты, : после чего получил задание посчитать F(10,10). : Эх, знали бы мы тогда с чем связались! : Сначала был stack overflow, и счётчик глубины : рекурсии подтвердил, что функция "уходит в себя" : по самое нехочу. К слову, стандартный размер : стека тогда был 4K, а 20 мегов можно было найти : разве что на винчестере. Завели массив вроде : long[10][1000], как раз по размеру сегмента, : для хранения промежуточных результатов, : и немедленно повисли, так как индекс мгновенно : выскочил за границу. Прикрутили библиотеку : для работы с массивами неограниченной длины, : (кстати, один из моих первых опытов на C :), : и опять вылетели, на этот раз по out of memory, : так как неограниченной памяти у нас не было. : Не сдались, заменили вызовы F для тривиальных : случаев (вроде (1,n)) на аналитические выражения, : но тут выяснилось, что переменные переполняются, : после чего пришлось отступить. Стало ясно, : что компьютер здесь нам не помощник, это скорее мы : тщетно пытаемся ему помочь. Тогда, от безысходност, : были выведены формулы для F(3,n) и даже для F(4,n), : и мы поняли, наконец, КАКАЯ бездна разверзлась впереди. : Уже для записи F(4,n) пришлось использовать новоизобретенную : функцию P(n)=2^(n^(n...^n)) n раз. А от том, чтобы : сохранить все эти дурацкие тройки, пятёрки и семёрки : в качестве коэффицентов для F(5,n) и речи не было. : Даже если их все выбросить нафиг, и оставить лишь "ядро", : которое в основном определяет характер роста, воображения : хватало разве чтобы представить себе внешний вид F(5,n). : Это чем-то напоминало исходную двойку в центре : многомерного пространства, которое увеличивало свою размерность : на каждом шаге, со всех сторон окруженную символами n, : возводящими друг друга в степень - кошмар полный. : А как же тогда выглядит F(6,n), если тут уместно слово "выглядит"? : И что творится дальше? : Не скрою - я был потрясён. : Какая красота! Какая мощь! Какое коварство! : Если представить себе значения F(m,n) на плоскости : и объединить их в последовательности при фиксированном m, : то получится набор функций F1(n), F2(n) и т. д. : По идее - это всё сёстры, ведь формула одна на всех, : лишь параметр меняется, а какая разница! : F0 ведёт себя тише воды, ниже травы - просто натуральные числа. : F1 недалеко ушла - всего лишь на 2 больше соседки. : А вот F2 заметно резвее - скорость роста увеличилась вдвое. : И вдруг - бабах - F3 уже растёт экспоненциально. : Про F4 и говорить нечего, если с F3 ещё как-то можно работать, : то F4 переполнит любую переменную и любую память. : И ведь это только начало! : Функция F определена для любых положительных m и n, : следовательно, есть вполне конкретное натуральное число, : соответствующее, скажем, F(100,100). Я не могу выразить словами : тот ужас, который испытываешь, мысленно стоя в начале координат, : и глядя на эту громадину, непостижимую уму, уходящую, казалось бы : в самую бескнечность, и тем не менее имеющую вершину в любой точке. : Куда там этой импотентной гиперболе, которая вздыбилась лишь потому, : что не может пробиться через вертикальную стену при x=0. : Какое бессилие, какая тупость: уменьши x в 10 раз, и результат : увеличится тоже в 10 раз. А наша F растёт гордо, уверенно, : и любой эпитет, описывающий её непобедимую силу, становится ничем, : стоит лишь сделать один шаг по оси m. Нет, если кому и рассказать : об ужасах бесконечности, то конечно не гиперболе, которая разобьёт : себе лоб, прежде чем туда доберётся и не скучной параболе, : которая сдохнет по дороге, нет - спросите F, она знает! : И мне до сих пор не даёт покоя этот вопрос: пусть число F(5,5) : нельзя ни записать, ни представить, так скажите хоть, : на какую цифру оно кончается? :) Всё это круто, но последняя цифра в этом огроомном числе равна 1. :) | ||
|