Итерированный логарифм

Итерированный логарифм $\log ^{*}n$ в математике и информатике определяется как целочисленная функция, равная количеству итеративных логарифмирований аргумента, необходимых для того, чтобы результат стал меньше или равен 1. Эта функция определена для всех положительных чисел, но в приложениях аргумент, как правило, натуральное число. Более строго итерированный логарифм определяется рекурсивной формулой:

\log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leqslant 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}

Итерированный логарифм определён для оснований $b>e^{1/e}\approx 1{,}444667$ A073229. Если положительное $b<e^{1/e}$ , то определяющая его рекурсивная последовательность сходится к числу больше 1. В информатике обычно используют двоичный итерированный логарифм.

Эта функция возрастает неограниченно, но чрезвычайно медленно. Для всех мыслимых на практике аргументов её можно было бы заменить константой, но для формул, определённых на всей числовой оси, такая запись будет ошибочной. Значения двоичного итерированного логарифма для всех практически интересных аргументов не превосходят 5 и приведены ниже.

n	$\log _{2}^{*}n$
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 2⁶⁵⁵³⁶ (~10¹⁹⁷²⁹)]	5

Применение

Итерированный логарифм возникает при анализе некоторых алгоритмов в оценках их вычислительной сложности^[1]^[2]^[3]^[4]^[5] Наиболее известна оценка временной сложности алгоритма Фюрера для умножения целых чисел — $O(n\log n\cdot 2^{O(\log ^{*}n)})$ , и оценка для распределенного алгоритма 3-раскраски $n$ -цикла в графе — $O(\log ^{*}n)$ ^[6]

Примечания

↑ Olivier Devillers, «Randomization yields simple O(n log* n) algorithms for difficult ω(n) problems.». International Journal of Computational Geometry & Applications 2:01 (1992), pp. 971—11.
↑ Noga Alon and Yossi Azar, «Finding an Approximate Maximum». SIAM Journal of Computing 18:2 (1989), pp. 2582—67.
↑ On Separators, Segregators and Time versus Space (неопр.). Дата обращения: 31 августа 2015. Архивировано 25 июня 2012 года.
↑ Robert Sedgewick - Robert Sedgewick (неопр.). Дата обращения: 31 августа 2015. Архивировано 8 марта 2021 года.
↑ Schneider, J. (2008), "A log-star distributed maximal independent set algorithm for growth-bounded graphs" (PDF), Proceedings of the Symposium on Principles of Distributed Computing, Архивировано из оригинала (PDF) 30 июля 2013, Дата обращения: 31 августа 2015 Источник (неопр.). Дата обращения: 31 августа 2015. Архивировано из оригинала 30 июля 2013 года.
↑ Richard Cole and Uzi Vishkin: «Deterministic coin tossing with applications to optimal parallel list ranking», Information and Control 70:1(1986), pp. 325—3.

Похожие исследовательские статьи

Логари́фм числа $\text{[math]}$ по основанию $\text{[math]}$ определяется как показатель степени, в которую надо возвести основание $\text{[math]}$ , чтобы получить число $\text{[math]}$ . Обозначение: $\text{[math]}$ , произносится: «логарифм $\text{[math]}$ по основанию $\text{[math]}$ ».

Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике.

Алгори́тм Шо́ра — квантовый алгоритм факторизации, позволяющий разложить число $\text{[math]}$ за время $\text{[math]}$ , используя $\text{[math]}$ логических кубитов.

Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов $\text{[math]}$ массива.

«Разделяй и властвуй» в информатике — схема разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.

Дерево хешей — полное двоичное дерево, в листовые вершины которого помещены хеши от блоков данных, а внутренние вершины содержат хеши от сложения значений в дочерних вершинах. Корневой узел дерева содержит хеш от всего набора данных, то есть хеш-дерево является однонаправленной хеш-функцией. Применяется для эффективного хранения транзакций в блокчейне криптовалют. Оно позволяет получить «отпечаток» всех транзакций в блоке, а также эффективно верифицировать транзакции. Названо по имени Ральфа Меркла, предложившего в 1979 году соответствующую технику хеширования криптографических функций.

ρ-Метод Полларда для дискретного логарифмирования — алгоритм дискретного логарифмирования в кольце вычетов по простому модулю, имеющий экспоненциальную сложность. Предложен британским математиком Джоном Поллардом в 1978 году, основные идеи алгоритма очень похожи на идеи ро-алгоритма Полларда для факторизации чисел. Данный метод рассматривается для группы ненулевых вычетов по модулю $\text{[math]}$ , где $\text{[math]}$ — простое число, большее $\text{[math]}$ .

Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться также трудно обратимыми или необратимыми.

Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.

В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число $\text{[math]}$ , такое, что время работы алгоритма для всех входов длины $\text{[math]}$ не превосходит $\text{[math]}$ , то временную сложность данного алгоритма можно асимптотически оценить как $\text{[math]}$ .

В математике суперлогарифм — это одна из двух обратных функций тетрации.

Вычисли́мые фу́нкции — множество функций то есть отображения множества натуральных чисел во множество натуральных чисел, в математических обозначениях это $\text{[math]}$ которые могут быть реализованы некоторым, алгоритмом, описание которого конечно, например, описанием переходов некоторой машиной Тьюринга.

Умножение Карацубы — метод быстрого умножения, позволяющий перемножать два $\text{[math]}$ -значных числа с битовой вычислительной сложностью $\text{[math]}$ .

Задача Иосифа Флавия — задача, входящая в одну из ранних работ по занимательной математике Баше де Мезириака. Задача заключается в следующем: по кругу стоит 41 воин, начиная с первого воина они убивают каждого третьего. Спрашивается, в каком месте нужно встать, чтобы остаться последним выжившим. В более общей формулировке участвует n воинов, которые считаются по кругу, и убивают каждого m-го. Название задачи восходит к истории, случившейся с Иосифом Флавием во время Иудейской войны.

Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном. Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные.

Двоичный логарифм — логарифм по основанию 2. Другими словами, двоичный логарифм числа $\text{[math]}$ есть решение уравнения $\text{[math]}$

Алгоритм Фюрера — быстрый метод умножения больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его предшественник, алгоритм Шёнхаге — Штрассена, опубликованный в 1971 году. Задача быстрого умножения больших чисел представляет большой интерес в области криптографии с открытым ключом.

Алгоритм Харви — ван дер Хувена — алгоритм умножения двух $\text{[math]}$ -битных целых чисел с временной сложностью $\text{[math]}$ в модели многоленточной машины Тьюринга. Предложен математиками Дэвидом Харви из университета Нового Южного Уэльса и Йорисом ван дер Хувеном из Национального центра научных исследований Франции. По состоянию на 2023 год является самым быстрым известным алгоритмом умножения чисел в данной модели, при этом оценка в $\text{[math]}$ на временную сложность алгоритмов умножения, по всей видимости, является неулучшаемой.

В информатике префиксная сумма, кумулятивная сумма, инклюзивное сканирование или просто сканирование последовательности чисел x0, x1, x2, … называется последовательность чисел y0, y1, y2, …, являющаяся префиксной суммой от входной последовательности:

y₀ = x₀

y₁ = x₀ + x₁

y₂ = x₀ + x₁+ x₂

…

SM3 — криптографическая хэш-функция, являющаяся частью национального криптографического стандарта Китая. Она была опубликована Государственным управлением криптографии 17 декабря 2010 под названием «GM/T 0004-2012: криптографический хэш алгоритм SM3». SM3 в основном используется в электронных подписях, имитовставках и генераторах псевдослучайных чисел.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.