Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 39
Если я правильно понял, float point (IEEE 754) в современных компьютерах это по сути реализация первой стрелочки Кнута. Интересно, следует ли ждать расширение формата хотя бы до второй стрелочки (на аппаратном уровне)?
Числа с плавающим разделителем — уж точно одной только степенью не выражаются. Так как это A*2^X, а также хитрые соглашения о +0, -0, NaN и Inf
Практической потребности в реализации чего-то большего, чем long double (80 бит с плавающей точкой) на данный момент нет — для инженерных задач с лихвой хватает возможностей double, а то и float.
Практика показывает, что такие задачи поддаются перемасштабированию, что позволяет втолкать их в рамки double.
Главная трудность в хранении огромных чисел — их размер.
Если делать размер плавающим, нужно перетряхивать всю вычислительную архитектуру (процессор сам себе выделяет память под результат — ничего себе, новости)
Если делать размер фиксированным, получим пустую трату памяти, слишком неэкономично, даже при нынешних терабайтах оперативки на кластерах.
Так что GMP — наше все.
Практической потребности в реализации чего-то большего, чем long double (80 бит с плавающей точкой) на данный момент нет — для инженерных задач с лихвой хватает возможностей double, а то и float.
Практика показывает, что такие задачи поддаются перемасштабированию, что позволяет втолкать их в рамки double.
Главная трудность в хранении огромных чисел — их размер.
Если делать размер плавающим, нужно перетряхивать всю вычислительную архитектуру (процессор сам себе выделяет память под результат — ничего себе, новости)
Если делать размер фиксированным, получим пустую трату памяти, слишком неэкономично, даже при нынешних терабайтах оперативки на кластерах.
Так что GMP — наше все.
Практической потребности в реализации чего-то большего, чем long double (80 бит с плавающей точкой) на данный момент нетНу как сказать, сегодня любой школьник первый раз открывший приложение калькулятор и решивший победить компьютер расчетом факториала, после третьей попытки скорее всего скажет «ха!!!» ну или «фи...» и пойдет пить пиво, а вот если была бы повсеместая поддержка второй стрелочки (в том числе и как стандарта отображения результата в программах, помимо т.н. «научного» или «экспоненциального»), то даже после 20 попытки шольник бы сказал «ооо» или «уууу» и пошел бы учить уроки.
Нет, не стоит. Арифметика с плавающей точкой построена на операциях переноса точки влево и вправо:
m x 2 ^ n = (2m) x 2 ^ (n-1) = (m/2) x 2 ^ (n+1)
Но для стрелочки второго порядка изменение показателя на 1 уже попросту не влезет в разрядную сетку:
2 ^^ (k+1) / 2 ^^ k = 2 ^ ( 2 ^^ k — 2 ^^ (k-1) )
Как следствие, при высоких k числа высших порядков будут просто поглощать числа низших порядков при попытках выполнения арифметических операций. Это так сильно упрощает все «алгоритмы» — что поддержка этих алгоритмов на уровне процессора становится просто ненужной.
m x 2 ^ n = (2m) x 2 ^ (n-1) = (m/2) x 2 ^ (n+1)
Но для стрелочки второго порядка изменение показателя на 1 уже попросту не влезет в разрядную сетку:
2 ^^ (k+1) / 2 ^^ k = 2 ^ ( 2 ^^ k — 2 ^^ (k-1) )
Как следствие, при высоких k числа высших порядков будут просто поглощать числа низших порядков при попытках выполнения арифметических операций. Это так сильно упрощает все «алгоритмы» — что поддержка этих алгоритмов на уровне процессора становится просто ненужной.
Учитывая, что количество планковских объемов в наблюдаемой Вселенной — всего-то порядка 10^185 и просуществует Вселенная до испарения последних черных дыр порядка 10^144 хрононов, то для решения вопросов современной физики, и любых нематематических проблем, достаточно реализации в компьютерах вычислений по первой стрелке Кнута.
Просто оставлю это здесь Число Грэма на пальцах
Это. Здесь. Уместно.
У числа Грэма есть смысл — верхняя граница решения какой-то там задачи про куб.
А в чём смысл этой МЕАМЕАМЕАЛОККАПУВАУМПы?
А в чём смысл этой МЕАМЕАМЕАЛОККАПУВАУМПы?
Жду вторую часть!
По поводу самой быстро-растущей функции. Почему бы вместо троек, десяток (в записях вроде "{3,3,3 / 3}" и "{{L100,10}10,10 & L,10}10,10") не брать самые большие числа, полученные на предыдущем шаге, обозначенные новыми символами?
Например, на первом шаге взяли произвольное достаточно большое число и дали определение оператору, которое позволяет с ним сделать что-то еще большее. На втором шаге берем полученное на первом в качестве операнда и придумываем новый оператор, позволяющий вырастить это число еще больше. Чтоб символы и скобочки не исчерпывались фантазией, пусть это будут какие-нибудь N1, N2,… — для создания новых символов для чисел и O1, O2,… — для создания новых символов для операторов.
Например, на первом шаге взяли произвольное достаточно большое число и дали определение оператору, которое позволяет с ним сделать что-то еще большее. На втором шаге берем полученное на первом в качестве операнда и придумываем новый оператор, позволяющий вырастить это число еще больше. Чтоб символы и скобочки не исчерпывались фантазией, пусть это будут какие-нибудь N1, N2,… — для создания новых символов для чисел и O1, O2,… — для создания новых символов для операторов.
… и получаем обычные рекурсивные функции. Ограничения которых упираются в длину используемого «алфавита». Поэтому математики придумали гораздо более быстрорастущие функции. Про это и будет вторая часть.
а так я и говорю, что ограничение в виде длины алфавита легко обходится, если использовать один символ и числовые индексы для создания неограниченного числа символов. А также однажды выбранную скобочку со своими индексами, чтоб не привязываться к ограничению на рисунок новх скобочек. Операторы на каждом этапе новые, максимально растущие по сравнению с предыдущими шагами — так что это не рекурсия.
Ну и, кстати, на «соревнованиях» по придумыванию самых больших чисел условие ставится, как правило такое — получить самое большое число, которое может быть записано не более чем N знаками.
Сбился на цепочках Конвея.
Можете подробнее объяснить, как от четырёхстрелочной операции перейти к рекурсивным трёхстрелочным?
Можете подробнее объяснить, как от четырёхстрелочной операции перейти к рекурсивным трёхстрелочным?
Общий механизм расчета цепочек Конвея таков (рассмотрим на примере цепочки из поста):
1. Одна стрелка — это возведение в степень (p → q = pq).
2. Единица после стрелки убирает остальную часть цепочки: (X → p → 1 = X → p, так же X → 1 → p = X, где в общем случае X — любая подцепочка).
3. Раскрытие цепочек производится с конца по следующей формуле: X → p → q = X → (X → (p-1) → q) → (q-1).
На примере из поста:
3 → 3 → 2 → 2, здесь X = 3 → 3, p = 2, q = 2, раскрываем цепочку по формуле:
3 → 3 → 2 → 2 = 3 → 3 → ( 3 → 3 → (2-1) → 2) → (2-1)
Части цепочек после единиц отсекаем: 3 → 3 → (3 → 3)
Поскольку 3 → 3 = 33 = 27, то получаем цепочку с 3 элементами: 3 → 3 → 27
1. Одна стрелка — это возведение в степень (p → q = pq).
2. Единица после стрелки убирает остальную часть цепочки: (X → p → 1 = X → p, так же X → 1 → p = X, где в общем случае X — любая подцепочка).
3. Раскрытие цепочек производится с конца по следующей формуле: X → p → q = X → (X → (p-1) → q) → (q-1).
На примере из поста:
3 → 3 → 2 → 2, здесь X = 3 → 3, p = 2, q = 2, раскрываем цепочку по формуле:
3 → 3 → 2 → 2 = 3 → 3 → ( 3 → 3 → (2-1) → 2) → (2-1)
Части цепочек после единиц отсекаем: 3 → 3 → (3 → 3)
Поскольку 3 → 3 = 33 = 27, то получаем цепочку с 3 элементами: 3 → 3 → 27
Интересно конечно ли число способов компактной записи чисел? Если оно конечно, то существует число, которое можно компактно записать только лишь использовав все частицы вселенной, следовательно это будет самое большие число, которое только можно сформулировать. Или такого числа не существует?
Видите ли, в чём дело… Каждый из указанных способов записи позволяет компактно описывать только определённый класс чисел. Числа ±1 — уже недоступны этому методу, придётся городить выражение.
Не вижу причины, почему было бы невозможно разработать форму записи, пригодную для компактной записи класса чисел, содержащего заданное сколь угодно большое число.
Не вижу причины, почему было бы невозможно разработать форму записи, пригодную для компактной записи класса чисел, содержащего заданное сколь угодно большое число.
Пусть у нас есть какая-то супер-пупер-нотация, неважно, как интерпретируемая.
Но смысл этой нотации — отображать строку текста (допустимую для языка нотации, разумеется) на конечное число.
Если у нас есть алфавит мощностью L и мы ограничены длиной строк N (оба значения, естественно, не превосходят количество частиц во вселенной), то получаем множество строк мощностью LN. Самое главное, что это множество конечное.
А теперь, внимание, фокус! Если каждой строке соответствует некоторое конечное число, то для конечного множества этих всех чисел мы можем найти максимум. И этот максимум тоже будет конечным.
Но смысл этой нотации — отображать строку текста (допустимую для языка нотации, разумеется) на конечное число.
Если у нас есть алфавит мощностью L и мы ограничены длиной строк N (оба значения, естественно, не превосходят количество частиц во вселенной), то получаем множество строк мощностью LN. Самое главное, что это множество конечное.
А теперь, внимание, фокус! Если каждой строке соответствует некоторое конечное число, то для конечного множества этих всех чисел мы можем найти максимум. И этот максимум тоже будет конечным.
Хитрость здесь в том, что мы вынесли за скобки описание нотации.
Если на неё мы тратим 0 символов (передаём её устно), — то мы всегда можем для любого наперёд заданного числа сказать, что «X» означает это число, «Y» означает X+1, а другие числа нас вообще не интересуют. У кого есть запасная вселенная, сможет на досуге родить десятичную запись числа Y.
Если же нам нужно рядом с компактной записью числа разместить компактную запись нотации (т.е. алгоритма вычисления — или порождения десятичной записи), то всё становится интереснее!
И тут мы упрёмся в проблему остановки.
Например, вот такая запись:
алгоритм: «прочитать десятичное значение n, выдать n-ное исключение из последовательности Коллаца (т.е. число, которое не сведётся к 1)»
даже для n=1 неизвестно, будет ли найдено такое число…
Если на неё мы тратим 0 символов (передаём её устно), — то мы всегда можем для любого наперёд заданного числа сказать, что «X» означает это число, «Y» означает X+1, а другие числа нас вообще не интересуют. У кого есть запасная вселенная, сможет на досуге родить десятичную запись числа Y.
Если же нам нужно рядом с компактной записью числа разместить компактную запись нотации (т.е. алгоритма вычисления — или порождения десятичной записи), то всё становится интереснее!
И тут мы упрёмся в проблему остановки.
Например, вот такая запись:
алгоритм: «прочитать десятичное значение n, выдать n-ное исключение из последовательности Коллаца (т.е. число, которое не сведётся к 1)»
даже для n=1 неизвестно, будет ли найдено такое число…
отсюда идея?
Ну так просто уперлось бы через некоторое время в количество памяти.
Вместо эксперимента можно было бы посмотреть его внутреннюю структуру. Это же массив целых чисел (разрядов) произвольного размера. А один массив на C# может хоть всю доступную память сожрать, независимо от количества доступной памяти.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
О действительно БОЛЬШИХ числах (часть 1)